C언어 Quick Soft 예제

int data[7] = { 3,5,1,2,6,9,7 };

void swapInt(int &a, int &b)
{
int tmp = a;
a = b;
b = tmp;
}

void printArr(int arr[]) {
printf("arr=");
for (int i = 0; i < 7; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}

void quickSort(int arr[], int left, int right)
{
printf("left=%d right=%d\n", left, right);

int i = left;
int j = right;
printArr(arr);

int pivotIndex = (left + right) / 2;
int pivot = arr[pivotIndex];
printf("pivotIndex=%d pivot=%d\n", pivotIndex, pivot);

while (i <= j) {
// 피봇을 기준으로 left의 값이 pivot의 값보다 큰 것을 찾는다.(잘못 놓여진 것을 찾음)
while (arr[i] < pivot) {
printf("arr[%d]=%d i++\n", i, arr[i]);
i++;
}
// 피봇을 기준으로 right의 값이 pivot의 값보다 작은 것을 찾는다.(잘못 놓여진 것을 찾음)
while (arr[j] > pivot) {
printf("arr[%d]=%d j--\n", j, arr[j]);
j--;
}

// 인덱스가 정상적인 상황일때 스왑한다.
if (i <= j) {
printf("swap begin %d %d\n", i, j);
swapInt(arr[i], arr[j]);
printArr(arr);
i++;
j--;
printf("swap end %d %d\n", i, j);
}
}

// 나머지 좌우에 대해서 다시 퀵소트 한다.
if (left < j) {
quickSort(arr, left, j);
}

if (i < right) {
quickSort(arr, i, right);
}
}


int main()
{
quickSort(data, 0, 6);
printf("data=");
for (int i = 0; i < 7; i++) {
printf("%d ", data[i]);
}
printf("\n");
return 0;
}