quick sort

참고 : http://blog.naver.com/kmediart/220552769535

#include <stdio.h> using namespace std; #define SWAP(a, b) {int t=a;a=b;b=t;} // 다른분이 구현한것 int quick_sort(int a[], int left, int right) { int i, j; int pivot_value; int tmp;              // 치환을 위한 임시 변수 if (left >= right) { // 정렬 수행 하지 않음, 즉 정렬할 항목이 하나임. return 0; } i = left + 1; j = right; pivot_value = a[left];   // 왼편 끝단의 항목의 값을 Pivot 값으로 선정 while (1) { // Pivot 값보다 큰 값 (이상) 일때 까지 i 증가 while ((i <= right) && (a[i] <= pivot_value)) { i++; } // Pivot 값보다 작은 값 (미만) 일때 까지 j 감소         while ((j >= left) && (a[j] > pivot_value)) { j--; } if (i < j)   // i와 j가 아직 충돌조건이 아니라면 i와 j 항목을 서로 교환 { tmp = a[i]; a[i] = a[j]; a[j] = tmp; } else    // 충돌조건이면, j항목과 pivot 항목을 서로 교환하고 정렬 정지 { tmp = a[j]; a[j] = pivot_value; a[left] = tmp; break; } } // 재귀적으로 교환된 pivot 값의 위치 j 를 기준으로 왼쪽과 오른쪽 데이터를 정렬 quick_sort(a, left, j - 1); quick_sort(a, j + 1, right); return 0; } // 내가 구현한것 void quick_sort2(int* d, int left, int right) { int p, l, r; if (left >= right) return; p = d[left]; l = left + 1; r = right; while (1) { while ((l < right) && (d[l] <= p)) { l++; } while ((r > left) && (d[r] >= p)){ r--; } if (l < r) { SWAP(d[l], d[r]); } else { SWAP(d[left], d[r]); break; } } quick_sort2(d, left, r - 1); quick_sort2(d, r + 1, right); } int g_arr[10] = { 10, 9, 2, 3, 7, 6, 5, 4, 8, 1 }; void print_all() { for (int i = 0; i < 10; i++) printf("%d, ", g_arr[i]); printf("\n"); } int main() { quick_sort2(g_arr, 0, 9); print_all(); return 0; }