오늘 최홍만이 K1에서 K.O. 를 당했다. 상대가 자주 큰 스윙훅을 휘두르는데, 저거 한대 맞겠다 싶던 찰라에 한대 맞고 링 바닦에 누워버렸다... 너무 아쉽다. 하지만 오히려 최홍만에게는 약이 될것같다.
각설하고... 어제와 오늘, 조용히 정렬 알고리즘에 대해 살펴보았다. 전에 내가 알고 있는 정렬 알고리즘은 Bubble Sort와 Quick Sort 뿐이였는데, 이 외에도 다양한 정렬 알고리즘이 있다는 것을 알았다. 각각의 알고리즘에 대한 원리를 이해하고 실제로 직접 구현해본 코드를 남겨둔다.
먼저 예로 사용되는 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가 있다.
|
