#include <stdio.h>
#define MAX_LEN 10
void swap(int*a, int* b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
int partition(int d[], int l, int r) //l is left, r is right.
{
int first = l;
int pivot = d[first];
++l; //shift.
while (l < r)
{
while (d[l] <= pivot)
++l;
while (d[r] > pivot)
--r;
if (l < r)
swap(&d[r], &d[l]);
else
break;
}
swap(&d[first], &d[r]);
return r;
}
int partition2(int d[], int l, int r) // p is pivot index.
{
int last = d[r];
int sortIdx = l;
for (int i = l; i <= r-1; i++)
{
if (d[i] <= last)
{
swap(&d[i], &d[sortIdx]);
sortIdx++;
}
}
swap(&d[sortIdx], &d[r]);
return sortIdx;
}
void qsort(int d[], int l, int r)
{
printf("l=%d, r=%d\n", l, r);
if (r > l){
//int idx = partition(d, l, r);
int idx = partition2(d, l, r);
qsort(d, l, idx - 1);
qsort(d, idx + 1, r);
}
}
int main()
{
int i = 1;
int j = 2;
int data[MAX_LEN] = { 3, 7, 8, 5, 2, 1, 9, 5, 4, 6};
qsort(data, 0, MAX_LEN-1);
for (int k = 0; k < MAX_LEN; k++)
{
printf("%d,", data[k]);
}
printf("\n%d\n", i);
}
분할 정복 알고리즘의 대표적인 소팅 알고리즘 partition 값을 구하는 방법은 전통적인 알고리즘 버젼과 MIT에서 제안한 방법 2가지 모두 구현해 보았다.
