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

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

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

 

[qsort]

 

#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]

 

 

#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]); } }