quick sort

quick-sort.c

void quick_sort(int a[], int n) {
  // 종료 조건
  if (n < 2) {
    return;
  }
 
  // pivot 기준으로 좌우 이동
  int pivot = a[n-1]; // 마지막 요소를 pivot으로 설정
  int left = -1;
  int right = n-1;
  while (1) {
    // 좌우 값 검색
    while (a[++left] < pivot);  // 좌측에서 pivot보다 큰 값 검색
    while (a[--right] > pivot); // 우측에서 pivot보다 작은 값 검색
    if (left >= right) { // 종료 조건
      break;
    }
    else { // 좌우 값 교환 
      int temp = a[left];
      a[left] = a[right];
      a[right] = temp;
    }
  }
 
  // pivot 위치 확정
  a[n-1] = a[left];
  a[left] = pivot;

  // 정렬되지 않은 좌우 배열 정렬
  quick_sort(a, left);
  quick_sort(a+left+1, n-left-1);
}