230630 Today I Learned

어제 구현했던 퀵정렬을 좀 더 개선해보고자 한다.

퀵정렬 개선

pivot 선택

• 어제 정리했듯이, 퀵정렬에서 어떤 값을 pivot으로 삼아야 하는 지 중요하다.

• 만약 pivot이 정렬 해야될 배열 상에서 가장 작은 값이나 가장 큰 값이 되면 위의 그림처럼 불균등하게 분할되어 순환호출의 깊이가 n이 되고 퀵정렬의 시간복잡도는 O(n^2)에 수렴한다.

• 어제 했던 퀵정렬에서는 위의 상황을 피하기 위해 가장 왼쪽 or 오른쪽 값이 아닌 중앙의 값을 pivot으로 선택했지만 이 경우에도 완벽하게 피할 수는 없다.

• 그래서 위와 같은 최악의 상황을 방지하기 위해 pivot을 다르게 고르는 방법들이 존재한다.

Random Pivot Quick Sort

피벗을 random한 값으로 선택해 최악의 시나리오를 피하려는 방법

• pivot을 low~high 범위에서 랜덤한 값을 뽑기위해 아래와 같이 작성한다. 랜덤한 값으로 피벗을 설정하고 가장 오른쪽 값과 교환한다.

• while 대신 for 루프 사용
  while에서는 low와 high의 투포인터로 피벗을 중간으로 설정하고 low와 high를 교환했다. 이번 for문 코드에서는 배열을 한번만 스캔해 피벗을 기준으로 나눈다.

• i는 피벗보다 작거나 같은 원소의 구역, j는 현재 검사하고있는 원소의 인덱스다. array[j]가 피벗보다 작거나 같으면 array[i],[j]를 교환하고 i를 1씩 증가시킨다.

• 이렇게하면 피벗보다 작거나 같은 원소들이 피벗의 왼쪽에, 오른쪽에는 큰 원소들이 위치하게된다.
  그리고 마지막에 피벗을 high 오른쪽 끝으로 이동시켜 고정시킨다.

public class RandomPivotQuickSort {

  private static Random random = new Random();

  public static void randomQuickSort(int[] array) {
    if (array.length >= 2){
      sort(array, 0, array.length-1);
    }
  }
  private static void sort(int[] array, int low, int high) {
    if (low >= high) return;

    int pivot = partition(array, low, high);

    sort(array, low, pivot-1);
    sort(array, pivot+1, high); // 피벗은 이미 정렬되어있으므로 pivot+1에서 시작한다.

  }

  private static int partition(int[] array, int low, int high) {
    int pivotIndex = random.nextInt(high-low+1) + low;
    swap(array, pivotIndex, high);
    int pivot = array[high];

    int i = low;
    for (int j = low; j<high; j++){
      if (array[j] <= pivot){
        swap(array, i, j);
        i++;
      }
    }
    swap(array, i, high);
    return i;
  }

  private static void swap(int[] array, int i, int j){
    int tmp = array[i];
    array[i] = array[j];
    array[j] = tmp;
  }
  
    public static void main(String[] args) {
    Random random = new Random();
    int[] array = new int[10];
    for (int i = 0; i < array.length; i++) {
      array[i] = random.nextInt(100); // 0~99까지 정수 랜덤
    }

    System.out.print("정렬 전 배열 : ");
    System.out.println(Arrays.toString(array));
    System.out.println("-----------------------------------------");
    randomQuickSort(array);
    System.out.print("랜덤피벗 퀵정렬 후 배열 : ");
    System.out.println(Arrays.toString(array));
    System.out.println("-----------------------------------------");
  }