여러가지 sort.

거품 정렬
바로 옆 원소끼리의 비교· 대입만 죽어라고 하는 무식한 노가다 알고리즘. 비교도 많고 대입도 많은 상당히 비효율적인 알고리즘이지요. 그나마 대입 여부를 플래그로 저장하면, 루프를 다 돌기 전에 정렬 작업을 끝낼 수는 있습니다. 이 알고리즘의 동작 모습을 그래픽 (x, y)->(x, 배열의 x째 원소)로 시연해 보면 대각선 부위에서 점들이 거품처럼 부글부글 움직이는 모습을 볼 수 있습니다.

선택 정렬
가장 큰 값부터 차례대로 리스트의 끝으로 옮겨서 정렬하는 방법으로, 실제 상황에서 가장 코딩하기 쉽고 직관적인 알고리즘입니다. 수행 시간이 데이터 상태의 영향을 잘 받지 않고, 데이터의 대입 횟수가 적은 게 특징입니다.

삽입 정렬
삽입 정렬과 거품 정렬을 비교해 보면, O(n^2)이라고 다 같은 O(n^2) 알고리즘은 아니라는 걸 알 수 있습니다. 평균적인 성능이 O(n^2) 알고리즘들 중에서 뛰어난 축에 들기 때문에, 이 정렬은 다른 정렬 알고리즘의 일부로도 자주 인용됩니다. 이 방법은 데이터의 상태, 데이터 한 개의 크기에 따라 성능 편차가 심한 편입니다.

쉘 정렬
삽입 정렬을 응용한 것 뿐인데 삽입 정렬과는 비교할 수 없을 정도로, O(n log n) 알고리즘에 버금가는 성능을 자랑하는 알고리즘입니다. 부가적인 메모리도 전혀 필요없죠. 비용 대 성능이 가장 뛰어난 알고리즘임이 틀림없습니다. 시간 복잡도도 O(n^2)나 O(n log n)처럼 정확하게 계산하기 힘든 신비로운(?) 알고리즘이기도 합니다.

퀵 정렬
가장 유명하고, 정렬 알고리즘의 표준이다시피 한 방법입니다. 이 알고리즘을 보면 정말 사기-_-라는 생각이 듭니다. 실제로 코딩을 해 보면, 퀵 정렬이 코드가 가장 긴데, 실행 시간은 퀵 정렬이 다른 알고리즘들보다 기막힐 정도로 짧습니다. 중간값이라는 뭔가 적당한(모호한-_-) 값을 선택해야 하고, 최악의 경우 시간 복잡도가 O(n^2)에 메모리 복잡도가 O(n)이 될 가능성까지 있는 알고리즘이 어쩜 이럴 수 있는지... 퀵 정렬만치 자료 상태에 민감한 알고리즘이 또 있을까 하는 생각이 듭니다.

하지만, 중간값을 기준으로 데이터를 반으로 갈라 놓고, 양측에 대해서 재귀적으로 정렬을 또 수행한다는 발상은 깔끔하고 멋집니다. 이런 걸 분할 정복법이라고 하지요. 이게 '퀵 정렬'이 아니었으면 '이분 검색'을 따라 '이분 정렬'이라는 이름이 붙었을 것입니다.

퀵 정렬은 본디 재귀적으로 정의되지만, 사용자 정의 스택을 구현해서 비재귀적으로 만들 수도 있습니다. 또한, 원소 개수가 한 자리 수로 떨어졌을 때는 또 재귀호출을 하는 게 아니라 삽입 정렬을 해서 능률을 극대화하기도 합니다.

병합 정렬
O(n log n)인 정렬 알고리즘 중에 가장 간단하고 쉽게 떠올릴 수 있는 방법입니다. 퀵 정렬이 큰 리스트를 반씩 쪼갠다면, 이 방법은 이미 정렬이 된 리스트를 하나 둘씩 합쳐서 작업을 수행합니다. 이 알고리즘은 소요 시간이 데이터 상태에 별 영향을 받지 않고, 시간 복잡도가 O(n log n)인 알고리즘 중에 유일하게 안정성이 있다는 데 의미를 둘 수 있습니다. O(n^2) 알고리즘들은 모두 안정성이 있지만.. 쿨럭~

병합 정렬의 큰 결점은 데이터 전체 크기만한 메모리가 더 필요하다는 점입니다. 아주 현학적인 방법으로 한 배열 안에서 병합을 구현하는 방법도 있긴 하지만, 밀고 당기고 하는 과정으로 인해 속도가 크게 떨어지기 때문에, 메모리를 아끼려면 차라리 아래에 나오는 힙 정렬을 쓰는 게 더 낫습니다.

무조건 2의 배수씩 리스트를 합치는 게 병합 정렬의 기본 원리지만, 리스트에서 오름차순인 부분만 골라내서 지능적으로 병합을 하는 방법도 생각할 수 있습니다. 또한 퀵 정렬과 비슷한 원리로 재귀판을 만들 수도 있지요.

힙 정렬
이진 완전 나무를 배열에다 접목시킨 절묘한 알고리즘입니다. 이 알고리즘을 뜯어 보면 절로 감탄이 나옵니다. 처음에는 나무 아래에서 위(뿌리)로 각 원소들을 최대값 힙 조건에 맞게 정리한 뒤, 나무 뿌리에 있는 자료를 차례차례 나무 뒤로 옮기면서 힙을 정렬된 배열로 바꿉니다. 뿌리에는 힙 나무 맨 뒤에 있던 원소가 왔다가, 다시 힙 조건에 맞는 위치로 내려가지요.

시간 복잡도가 O(n log n)인 정렬 알고리즘 중에서는 부가적인 메모리가 전혀 필요없다는 게 힙 정렬의 큰 장점이지만, 하지만 수행 속도가 동급 O(n log n) 알고리즘들에 비해서는 약간(아주...) 낮은 편입니다.

기수 정렬
기발함 그 자체입니다. 네 자리 수가 있으면, 백 자리, 십 자리, 일 자리 순으로 차례차례 정렬을 한다는 게 기본 전략입니다. 저는 이 알고리즘을 이해하고 나서도, "그렇게 해서 어떻게 실제로 정렬이 되는데?" 이걸 이해하는 데 한참 시간이 걸려야 했습니다.

이 정렬법은 비교 연산을 하지 않으며, 무엇보다도 시간 복잡도가 O(n)입니다. 물론 데이터 전체 크기에 기수 테이블의 크기만한 메모리가 더 필요하지요. 기수 정렬은 정렬 방법의 특수성 때문에 부동소숫점처럼 특수한 비교 연산이 필요한 데이터에는 적용할 수 없지만, 매우 특이하고 멋진 알고리즘임은 틀림없습니다.

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <string.h>

class CTimeRecorder {
time_t& m_rWriteTo, m_dwBegin;
public:
CTimeRecorder(time_t& rTo): m_rWriteTo(rTo), m_dwBegin(clock())
{ }
~CTimeRecorder()
{ m_rWriteTo=clock()-m_dwBegin; }
};

template<typename T> void Swap(T& a, T& b)
{ T c; c=a; a=b; b=c; }

template<typename T>
class CSortCollection {
T *m_pData; int m_nCount; time_t m_dwElapsed;
public:
//Construction
CSortCollection(T *pArr, int nCnt): m_pData(pArr), m_nCount(nCnt)
{ }
void Init(T *pArr, int nCnt)
{ m_pData=pArr, m_nCount=nCnt; }

//Operation
void BubbleSort();
void SelectionSort();
void InsertionSort();
void ShellSort();
void QuickSort();
void MergeSort();
void HeapSort();
void RadixSort();

//Elapsed time
time_t GetElapsedTime() const { return m_dwElapsed; }
int Verify();
};

template<typename T>
int CSortCollection<T>::Verify()
{
int i;
for(i=0;i<m_nCount-1;i++) if(m_pData[i]>m_pData[i+1]) return i;
return -1;
}

template<typename T>
void CSortCollection<T>::BubbleSort()
{
int i,j, flag=1; CTimeRecorder rec(m_dwElapsed);
for(i=0;i<m_nCount && flag;i++)
for(j=flag=0;j<m_nCount-i-1;j++)
if(m_pData[j]>m_pData[j+1]) { flag=1; Swap(m_pData[j], m_pData[j+1]); }
}

template<typename T>
void CSortCollection<T>::SelectionSort()
{
int i,j,k; CTimeRecorder rec(m_dwElapsed);
for(i=0;i<m_nCount-1;i++) {
k=i;
for(j=i+1;j<m_nCount;j++) if(m_pData[k]>m_pData[j]) k=j;
Swap(m_pData[k], m_pData[i]);
}
}

template<typename T>
void CSortCollection<T>::InsertionSort()
{
int i,j; T r; CTimeRecorder rec(m_dwElapsed);
for(i=1;i<m_nCount;i++) {
for(j=i-1, r=m_pData[i];j>=0 && m_pData[j]>r;j--) m_pData[j+1]=m_pData[j];
m_pData[j+1]=r;
}
}

template<typename T>
void CSortCollection<T>::ShellSort()
{
int i,j,k,l; T r; CTimeRecorder rec(m_dwElapsed);
for(i=1;i<m_nCount;k=i, i=i*3+1);

do {
for(l=0;l<k;l++)
for(i=l+k;i<m_nCount;i+=k) {
for(j=i-k, r=m_pData[i];j>=l && m_pData[j]>r;j-=k)
m_pData[j+k]=m_pData[j];
m_pData[j+k]=r;
}
k=(k-1)/3;
}
while(k>=1);
}

template<typename T>
void CSortCollection<T>::QuickSort()
{
CTimeRecorder rec(m_dwElapsed);
//sorting boundary, pivot index, and traveling pointers for partition step
int lo, hi, mid, loguy, higuy;

//stack for saving sub-array to be processed
int lostk[40], histk[40], stkptr=0;
lo=0; hi=m_nCount-1; //initialize limits

while(1) {
mid=lo+( ((hi-lo)+1) /2); //find middle element
Swap(m_pData[mid], m_pData[lo]); //swap it to beginning of array

/* Would it be better to use insertion sort, when hi-lo is very small?
for(loguy=lo+1; loguy<=hi; loguy++) {
for(higuy=loguy-1, r=m_pData[loguy]; higuy>=lo && m_pData[higuy]>r;
higuy--) m_pData[higuy+1]=m_pData[higuy];
m_pData[higuy+1]=r;
}
*/
loguy=lo; higuy=hi+1;
while(1) {
do loguy++; while (loguy<=hi && m_pData[loguy]<=m_pData[lo]);
do higuy--; while (higuy>lo && m_pData[higuy]>=m_pData[lo]);

if(higuy<loguy) break;
Swap(m_pData[loguy], m_pData[higuy]);
}
Swap(m_pData[lo], m_pData[higuy]); //put partition element in place

if( higuy-1-lo >= hi-loguy ) {
if(lo+1<higuy) { //save big recursion for later
lostk[stkptr]=lo; histk[stkptr]=higuy-1;
++stkptr;
}
if(loguy<hi) { lo=loguy; continue; } //do small recursion
}
else {
if(loguy<hi) { //save big recursion for later
lostk[stkptr]=loguy; histk[stkptr]=hi; ++stkptr;
}
if(lo+1<higuy) { hi=higuy-1; continue; } //do small recursion
}

--stkptr; //pop subarray from stack
if(stkptr>=0) { lo=lostk[stkptr]; hi=histk[stkptr]; }
else break; //all subarrays done--sorting finished.
}
}

template<typename T>
void CSortCollection<T>::HeapSort()
{
CTimeRecorder rec(m_dwElapsed);
int i,j; T *dt=m_pData-1, root; //dt is a 1-based index for m_pData
//construct the heap.
for(i=m_nCount/2;i>=1;i--) {
root=dt[i];
for(j=2*i;j<=m_nCount;j<<=1) {
if(j<m_nCount && dt[j]<dt[j+1]) j++;
if(root>=dt[j]) break; dt[j/2]=dt[j];
}
dt[j/2]=root;
}

//Perform sorting wow~
for(i=m_nCount;i>0;) {
Swap(dt[1], dt[i]); i--; root=dt[1];
for(j=2;j<=i;j<<=1) {
if(j<i && dt[j]<dt[j+1]) j++;
if(root>=dt[j]) break; dt[j/2]=dt[j];
}
dt[j/2]=root;
}
}

template<typename T>
void CSortCollection<T>::MergeSort()
{
int i,j,a,b,c,d; CTimeRecorder rec(m_dwElapsed);
T *pTmp=new T[m_nCount], *orig=m_pData, *dest=pTmp;

for(i=1;i<m_nCount;i<<=1) {
for(j=0;j<m_nCount;j+=(i<<1)) { //for each fragment,
d=j+(i<<1); if(d>m_nCount) d=m_nCount;
if(j+i>=m_nCount) { //Copy the remaining elems
for(a=j;a<m_nCount;a++) dest[a]=orig[a]; break;
}

for(a=c=j,b=j+i; c<d; c++)
if((orig[a]<=orig[b] && a<j+i) || b==d) dest[c]=orig[a], a++;
else dest[c]=orig[b], b++;
}
Swap(orig, dest);
}
if(orig!=m_pData) memcpy(m_pData, orig, sizeof(T)*m_nCount);
delete []pTmp;
}

#define BITOF(i,b) ((unsigned char *)orig)[i*sizeof(T)+b]
//#define BITOF(i,b) ((orig[i])>>(b*8))&0xff
template<typename T>
void CSortCollection<T>::RadixSort()
{
CTimeRecorder rec(m_dwElapsed); int b,i, count[256], index[256];
T *pTmp=new T[m_nCount], *orig=m_pData, *dest=pTmp;
for(b=0;b<sizeof(T);b++) {
memset(count, 0, sizeof(count));
for(i=0;i<m_nCount;i++) count[ BITOF(i,b) ]++;
index[0]=0;
for(i=1;i<256;i++) index[i]=index[i-1]+count[i-1];
for(i=0;i<m_nCount;i++)
dest[index[BITOF(i,b)]++]=orig[i];
Swap(orig, dest);
}

if(orig!=m_pData) memcpy(m_pData, orig, sizeof(T)*m_nCount);
delete []pTmp;
}
#undef BITOF

#define N 1000000
int main(int argc, char* argv[])
{
srand(time(0));
int *arr=new int[N], *ar2=new int[N], i,j;
for(i=0;i<N;i++) arr[i]= rand()|(rand()<<16);
CSortCollection<int> sor(ar2, N);

for(i=3;i<8;i++) {
memcpy(ar2, arr, sizeof(int)*N);
for(j=0;j<10;j++) printf("%d ", ar2[j]); puts("");
switch(i) {
case 0: sor.BubbleSort(); printf("BubbleSort: "); break;
case 1: sor.SelectionSort(); printf("SelectionSort: "); break;
case 2: sor.InsertionSort(); printf("InsertionSort: "); break;
case 3: sor.HeapSort(); printf("HeapSort: "); break;
case 4: sor.QuickSort(); printf("QuickSort: "); break;
case 5: sor.MergeSort(); printf("MergeSort: "); break;
case 6: sor.ShellSort(); printf("ShellSort: "); break;
case 7: sor.RadixSort(); printf("RadixSort: "); break;
}
j=sor.Verify(); if(j!=-1) printf("Error: %d %d\n", j, arr[j]);
printf("%.3g sec\n",sor.GetElapsedTime()/(double)CLOCKS_PER_SEC);
for(j=0;j<10;j++) printf("%d ", ar2[j]); puts("\n");
}

delete []arr; delete []ar2;
return 0;
}