쾌조의 기이한 점

만약 in-place가 quick sort를 한다면 pivot의 위치를 선택하면 코드의 세부 사항에 영향을 줄 수 있습니다.
같은 실현 방식으로 첫 번째 원소가 pivot일 때 pivot 위치를 회복하면hi를 기준으로 한다.

public class TestQuickSort {
  public static void main(String[] args) {
    int[] arr = { 1, 4, 2, 3, 6, 5, 0 };
    quickSort(arr, 0, arr.length - 1);
    for (int i : arr) System.out.println(i);
  }
  
  public static void quickSort(int[] arr, int left, int right) {
    if (left >= right) return;
    int pivot = arr[left];
    int lo = left;
    int hi = right + 1;
    while (true) {
      while (arr[++lo] < pivot) { if (lo == right) break; }
      while (arr[--hi] > pivot) { }
      if (lo >= hi) break;
      swap(arr, lo, hi);
    }
    swap(arr, left, hi);
    quickSort(arr, left, hi - 1);
    quickSort(arr, hi + 1, right);
  }
  
  public static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
}

반대로 마지막 원소를 pivot로 할 때 pivot를 회복하면 로를 기준으로 한다.

public class TestQuickSort {
  public static void main(String[] args) {
    int[] arr = { 1, 4, 2, 3, 6, 5, 0 };
    quickSort(arr, 0, arr.length - 1);
    for (int i : arr) System.out.println(i);
  }
  
  public static void quickSort(int[] arr, int left, int right) {
    if (left >= right) return;
    int pivot = arr[right];
    int lo = left - 1;
    int hi = right;
    while (true) {
      while (arr[++lo] < pivot) { }
      while (arr[--hi] > pivot) { if (hi == left) break; }
      if (lo >= hi) break;
      swap(arr, lo, hi);
    }
    swap(arr, right, lo);
    quickSort(arr, left, lo - 1);
    quickSort(arr, lo + 1, right);
  }
  
  public static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
}

이러한 실현 방식에서 pivot를 복구하는 하위 표시를 선택할 때'안전한'것, 즉 pivot가 있는 위치를 영원히 초과하지 않는 것을 선택해야 하기 때문이다.
중간의 원소를 pivot로 선택하면 pivot를 회복할 필요가 없고, 로나hi를 기준으로 계속 빠르게 배열할 수 있습니다. 순환의 끝 조건을 충족시킬 때 반드시 같기 때문입니다.

public class TestQuickSort {
  public static void main(String[] args) {
    int[] arr = { 1, 4, 2, 3, 6, 5, 0 };
    quickSort(arr, 0, arr.length - 1);
    for (int i : arr) System.out.println(i);
  }
  
  public static void quickSort(int[] arr, int left, int right) {
    if (left >= right) return;
    int pivot = arr[(left + right) / 2];
    int lo = left - 1;
    int hi = right + 1;
    while (true) {
      while (arr[++lo] < pivot) { }
      while (arr[--hi] > pivot) { }
      if (lo >= hi) break;
      swap(arr, i, j);
    }
    quickSort(arr, left, lo - 1);
    quickSort(arr, lo + 1, right);
  }
  
  public static void swap(int[] arr, int i, int j) {
    System.out.println("swap " + i + " with " + j);
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
}