[자료구조] qsort, quick sort 구현하기

*stdlib.h에 있는 qsort는 compare 함수만 구현하면 손쉽게 사용할 수 있다. 

compare에 넘기는 void* 포인터는 상수 포인터이므로 변경이 불가능하다. 

 

[qsort]

 

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

#include <stdio.h> #include <stdlib.h>   int compare(const void *a, const void *b) {     int n1 = *(int *)a;     int n2 = *(int *)b; // void 포인터를 int 포인터로 변환한 뒤 역참조하여 값을 가져옴       if (n1 < n2) return -1;     else if (n1 == n2) return 0;     else return 1;   } int main() {     int num[10];     for (int i = 0; i <10; i++) {         num[i] = (rand() % 100) + 1;     }       qsort(num, sizeof(num)/sizeof(int),sizeof(int), compare);       for (int i = 0; i < 10; i++) {         printf("%d ", num[i]);     } }

 

[quick sort]

 

 

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

#include <stdio.h> #include <stdlib.h>   void quickSort(int *data, int l, int r) {     int left = l, right = r;     int pivot = data[(l+r)/2];       while(left <= right) {         while(data[left] < pivot) left++;         while(data[right] > pivot) right--;           if (left <=right) {             int tmp = data[left];             data[left] = data[right];             data[right] = tmp;             left++;             right--;         }     }     if (l < right) quickSort(data, l, right);     if (r > left) quickSort(data, left, r); } int main() {     int num[10];     for (int i = 0;i < 10; i++) {         num[i] = (rand() % 100)+1;     }       quickSort(num, 0, 9);       for (int i = 0; i < 10; i++) {         printf("%d ", num[i]);     } }