정렬 알고리즘 소스모음

각각의 정렬 알고리즘에 대한 원리를 이해하고 실제로 직접 구현해본 코드를 남겨둔다.

먼저 예로 사용되는 data의 정의는 다음과 같다.

const size_t cntData = 20;
int data[cntData];

첫번째, Selection Sort

void selectionSort(int data[], size_t cntData) {
    for(size_t beginIdx=0; beginIdx<cntData-1; beginIdx++) {
        int minData = data[beginIdx];
        size_t minDataIdx = beginIdx;
        for(size_t i=beginIdx+1; i<cntData; i++) {
            if(minData>data[i]) {
                minData = data[i];
                minDataIdx = i;
            }
        }
		
        data[minDataIdx] = data[beginIdx];
        data[beginIdx] = minData;
    }
}

두번째, Insertion Sort

void insertionSort(int data[], size_t cntData) {
    int t;
    size_t j;

    for(size_t i=1; i<cntData; i++) {
        t = data[i];
        j = i;
		
        while(data[j-1]>t && j>0) {
            data[j] = data[j-1];
            j--;
        }

        data[j] = t;
    }
}

세번째, 최악의 Bubble Sort

void bubbleSort(int data[], size_t cntData) {
    for(size_t i=cntData-1; i>0; i--) {
        for(size_t j=0; j<i; j++) {
            if(data[j]>data[j+1]) {
                int tmpData = data[j];
                data[j] = data[j+1];
                data[j+1] = tmpData;
            }
        }
    }
}

네번째, Insertion Sort를 응용한 Shell Sort

void ShellSort(int data[], size_t cntData) {
    size_t h;
    for(h=1; h<cntData; h=3*h+1);

    for(h/=3; h>0; h/=3) {
        for(size_t i=0; i<h; i++) {
            for(size_t j=i+h; j<cntData; j+=h) {
                int v = data[j];
                size_t k = j;
                while(data[k-h]>v && k>(h-1)) {
                    data[k] = data[k-h];
                    k -= h;
                }
                data[k] = v;
            }
        }
    }
}

다섯번째, 응용에 제한적인 Distribution Counting Sort

void distributionCounting(int data[], size_t cntData, 
                          int startValue, int endValue) {
    const size_t cntType = endValue-startValue+1;
    int *count = new int[cntType];
    
    for(size_t i=0; i<cntType; i++) {
        count[i] = 0;
    }

    for(size_t i=0; i<cntData; i++) {
        count[data[i]]++;
    }

    for(size_t i=1; i<cntType; i++) {
        count[i] += count[i-1];
    }

    int *tmp = new int[cntData];
	
    for(int i=cntData-1; i>=0; i--) {
        tmp[--count[data[i]]] = data[i];
    }

    for(size_t i=0; i<cntData; i++) {
        data[i] = tmp[i];
    }

    delete [] tmp;
    delete [] count;
}

여섯번째, Quick Sort

void quickSort(int data[], size_t cntData) {
    int pivot, tmp;
    int i, j;

    if(cntData > 1) {
        pivot = data[cntData-1];
        i = -1;
        j = cntData - 1;

        while(true) {
            while(data[++i] < pivot);
            while(data[--j] > pivot);

            if(i >= j) break;
            tmp = data[i];
            data[i] = data[j];
            data[j] = tmp;
        }

        data[cntData-1] = data[i];
        data[i] = pivot;

        quickSort(data, i);
        quickSort(data+i+1, cntData-i-1);
    }
}

일곱번째, 기수정렬(Radix Sort)
기수정렬 중, 기수교환정렬(Radix Exchange Sort)

unsigned long bit(unsigned data, int b) {
    return data & (1 << b);
}

void radixExchangeSort(int data[], size_t cntData, int b) {
    int t, i, j;
    if(cntData>1 && b>=0) {
        i = 0;
        j = cntData - 1;

        while(true) {
            while(bit(data[i], b)==0 && i<j) i++;
            while(bit(data[j], b)!=0 && i<j) j--;

            if(i>=j) break;
			
            t = data[i];
            data[i] = data[j];
            data[j] = t;
        }

        if(bit(data[cntData-1], b) == 0) j++;

        radixExchangeSort(data, j, b-1);
        radixExchangeSort(data+j, cntData-j, b-1);
    }
}

기수교환정렬 중, 직접기수정렬(Straight Radix Sort)

unsigned bits(unsigned data, int startBitIndex, int count) {
    return (data >> count) & ~(~0 << startBitIndex);
}

void straightRadixSort(int data[], size_t cntData) {
    int i, j;
    int *tempData, *count;

    const size_t sizeBitData = sizeof(data[0]) * 8;
    const size_t bitCount = 4;
    const size_t cntCountArray = (1<<bitCount);

    tempData = (int *)malloc(sizeof(int)*cntData);
    count = (int *)malloc(sizeof(int)*cntCountArray);

    for(i=0; i<sizeBitData/bitCount; i++) {		
        for(j=0; j<cntCountArray; j++)
            count[j] = 0;

            for(j=0; j<cntData; j++)
                count[bits(data[j], i*bitCount, bitCount)]++;

            for(j=1; j<cntCountArray; j++)
                count[j] += count[j-1];

            for(j=cntData-1; j>=0; j--)
                tempData[--count[bits(data[j], i*bitCount, bitCount)]] = 
                    data[j];

            for(j=0; j<cntData; j++)
                data[j] = tempData[j];
    }

    free(count);
    free(tempData);
}

끝으로 위의 코드에 대한 최적화는 전혀 되어 있지 않다. 하나의 예로 정렬 알고리즘 중 가장 많이 사용하는 Quick Sort의 경우에 재귀호출을 사용하는데, 많은 개수의 데이터를 정렬하는 실제 상황에서는 비재귀 형태로 수정되어야 한다. 또한  학습한 책에는 나와 있으나, 이해만 하고 구현해보지 못한 정렬 알고리즘으로 Heap Sort와 Merge Sort가 있다.

출처 : Tong - freewing1983님의 C#통