230701 Today I Learned

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

퀵정렬 개선

Median of Three

세 값중 중간값으로 피벗을 선정해 최악(min,max)의 경우를 피하는 방법

• 최악의 방법은 피할 수 있지만 차악의 방법이 될수는 있다.

• 하지만 일반적인 상황에서는 매우 효과적이다.

• low, mid, high 값 중 중간값을 뽑아서 피벗으로 삼고 제일 오른쪽 값(high)와 바꿔서 알고리즘을 진행한다.

• 피벗을 고르는 방법을 제외하고는 위의 퀵정렬과 거의 비슷하다.

public class A_MOTQuickSort {

  public static void MOTQuickSort(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 pivotIndex = findMedianIndex(array, low, high);
    swap(array, pivotIndex, high); // 피벗을 high(맨 오른쪽)으로 이동

    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 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 int findMedianIndex(int[] array, int low, int high) {
    int mid = (low + high) / 2;

    // low, mid, high인덱스의 값을 크기순으로 정렬해 중간값의 index 반환
    if (array[low] > array[mid]) swap(array,low,mid);
    if (array[low] > array[high]) swap(array,low,high);
    if (array[mid] > array[high]) swap(array,mid,high);

    return mid;
  }

  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("-----------------------------------------");
    MOTQuickSort(array);
    System.out.print("Median of Three 퀵정렬 후 배열 : ");
    System.out.println(Arrays.toString(array));
    System.out.println("-----------------------------------------");

  }