230703 Today I Learned

연구소로 첫 출근을 하고 오자마자 블로그부터 켰다. 기존의 TIL보다 분량은 적어져도 하루도 안빼먹고 달릴 계획이다. 게을러지지 않기 위해 바로 달리자!! 오늘은 퀵정렬을 저번보다 좀 더 개선해보고자 한다.

퀵정렬 개선

Median of Three + 이진삽입정렬

n의 크기가 적으면 삽입정렬, 크면 퀵정렬을 사용해서 서로의 장단점을 보완하는 방법

• 하이브리드 퀵정렬이라고도 한다.

• 퀵정렬은 size가 큰 대규모 데이터에서 효율성이 크다.

• 반면 삽입정렬은 size가 큰 대규모 데이터에서 효율성은 부족하지만 size가 작은 데이터셋에서는 효율적이다.

• 삽입정렬이 버블, 선택정렬보다 효율적이다. 최선의 경우 시간복잡도가 O(n)이고, 탐색 횟수가 적다.

• size가 얼마일 때를 기준으로 삼아야 할 지에 대한 최적 크기는 각 상황에 따라 다르지만 일반적(경험적)으로는 10~20정도로 알려져 있다.

Java로 구현

20을 기준으로 array의 size가 20이하면 이진삽입정렬, 20초과면 Median of Three 퀵정렬을 사용한다.

public class A_HybridQuickSort {

  public static void HybridQuickSort(int[] array) {
    int size = array.length;

    if (size < 2) {
      return;
    } else if (size <= 20) {
      System.out.println("size가 20이하기 때문에 삽입정렬을 사용합니다.");
      binaryInsertionSort(array);
    } else {
      System.out.println("size가 20초과이기 때문에 퀵정렬을 사용합니다.");
      MOTQuickSort(array, 0, array.length-1);
    }
  }

  private static void binaryInsertionSort(int[] array){
    for (int i = 1; i < array.length; i++) {
      int key = array[i];
//      이진탐색으로 앞의 배열 탐색. 최종 위치는 low가 된다.
      int low = 0;
      int high = i-1;
      while(low <= high){
        int mid = (low+high)/2;
        if (key < array[mid]){
          high = mid - 1;
        } else {
          low = mid + 1;
        }
      }
//      i-1부터 최종 위치까지 원소를 한칸 씩 뒤로 민다
      for (int j = i-1; j >= low; j--){
        array[j+1] = array[j];
      }
//      최종 위치에 key값을 삽입
      array[low] = key;
    }
  }

  private static void MOTQuickSort(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);

    MOTQuickSort(array, low, pivot-1);
    MOTQuickSort(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[20];
    int[] array2 = new int[30];
    for (int i = 0; i < array.length; i++) {
      array[i] = random.nextInt(100); // 0~99까지 정수 랜덤
    }
    for (int i = 0; i < array2.length; i++) {
      array2[i] = random.nextInt(100); // 0~99까지 정수 랜덤
    }

    System.out.print("정렬 전 배열1 : ");
    System.out.println(Arrays.toString(array));
    System.out.println("-----------------------------------------");
    HybridQuickSort(array);
    System.out.print("Hybrid 퀵정렬 후 배열1 : ");
    System.out.println(Arrays.toString(array));
    System.out.println("-----------------------------------------");
    System.out.print("정렬 전 배열2 : ");
    System.out.println(Arrays.toString(array2));
    System.out.println("-----------------------------------------");
    HybridQuickSort(array2);
    System.out.print("Hybrid 퀵정렬 후 배열2 : ");
    System.out.println(Arrays.toString(array2));
    System.out.println("-----------------------------------------");
  }