듀얼 피벗 퀵 정렬 (Dual Pivot Quick Sort)

원하는 기준으로 배열을 다시 나열하는 정렬 알고리즘

 

 

 

듀얼 피벗 퀵 정렬 (Dual Pivot Quick Sort)

듀얼 피벗 퀵 정렬은 Java의 Arrays.sort() 정렬 메소드에 사용되며 원시 타입(primitive type, int[], long[]) 배열을 정렬할 때 사용합니다. 퀵 정렬 보다 더 효율적이며, 두 개의 피벗을 사용하여 배열을 세 부분으로 나누어 정렬합니다. 

 

시간 복잡도 : O(n log n) 최악의 경우 O(n^2) 

 

듀얼 피벗 퀵소트는 원시 타입의 배열을 정렬할 때 사용합니다. 객체 타입일 때는 팀소트를 사용합니다.

 

 

원시 타입 배열 특징

• 원시 타입은 메모리 크기가 작아서 값 복사나 이동이 빠릅니다. 이로 인해 값의 비교가 빠릅니다.
• 원시 타입 배열들은 메모리에 연속적으로 저장하여 메모리에 빠르게 접근할 수 있습니다. 

 

듀얼 피벗 퀵 정렬 특징

• 듀얼 피벗 퀵 정렬은 퀵 정렬과 달리 2개의 피벗을 사용하여 세 부분으로 나눕니다. (퀵 정렬 보다 빠름)
• 세 부분으로 나누기 위해 값의 비교와 이동이 자주 일어납니다. 

 

듀얼 피벗 퀵 정렬은 값을 비교하고 이동하여 정렬을 하므로 원시 타입 배열의 비교가 쉽고 이동이 빠르다는 특징과 맞물려 효율적으로 정렬할 수 있습니다. 이로 인해 Java의 원시 타입 배열에 듀얼 피벗 퀵 정렬을 사용합니다. 

 

 

 

 

동작 과정

듀얼 피벗 퀵 정렬은 피벗 선택으로 배열을 세 부분으로 나누고 나누어진 세 부분을 또 두 개의 피벗을 선택하고 세 부분으로 나눕니다. 이렇게 재귀적으로 동작하여 정렬을 완성합니다. 

 

 

1. 피벗 선택 

두 개의 피벗 p1, p2를 선택합니다. p1 < p2 조건을 만족하도록 합니다. 일반적으로 배열의 첫 번째 요소와 마지막 요소를 사용합니다. 

 

2. 분할 

두 개의 피벗 p1, p2를 기준으로 3개로 분할 합니다. 

 

3. 재귀

분할된 3부분에서도 피벗 2개를 선택하여 3개로 나눕니다. 이 과정을 가장 작은 영역까지 거쳐 정렬된 전체 배열을 얻습니다. 

 

 

예시

예시 배열 : [3, 1, 5, 9, 4, 8, 7]

 

1. 피벗 선택 : 

두 개의 피벗을 선택합니다. 일반적으로 배열의 첫 번째 요소와 마지막 요소를 사용합니다. 

[3, 1, 5, 9, 4, 8, 7]

 

2. 분할 

두 개의 피벗을 기준으로 3개로 분할합니다. 피벗을 p1, p2로 p1 < p2 를 만족하도록 합니다. 

왼쪽 부분 : p1 보다 작은 요소

가운데 부분 : p1과 p2 사이의 요소 

오른쪽 부분 : p2 보다 큰 요소 

 

[1] 3 [5, 4] 7 [9, 8]

 

3. 재귀 

나누어진 부분도 위의 과정을 거쳐 정렬을 완성합니다. 

[1, 3, 4, 5, 7, 8, 9]

 

 

 

Java 코드 구현

/*
듀얼 피봇 퀵소트 Dual Pivot Quick Sort

시간 복잡도
평균        - O(n log n)
최악의 경우  - O(n^2)

Java의 sort 메소드에서 프리미티브 타입의 배열을 정려할 때 사용
두 개의 피벗을 선택하여 3개의 영역으로 나눈 후 정렬을 진행한다.
퀵소트보다 효율적이다.
 */
public class DualPivotQuickSort {

  public static void main(String[] args) {
    int[] array = {3,1,5,9,4,8,7};
    printArray(array);
    dualPivotQuickSort(array);
    printArray(array);
  }

  // 메소드 시작
  public static void dualPivotQuickSort(int[] array) {
    dualPivotQuickSort(array, 0, array.length-1);
  }

  // 듀얼 피벗 퀵소트 정렬 시작
  // 피벗 2개를 설정하여 영역을 정렬
  public static void dualPivotQuickSort(int[] array, int low, int high) {

    if(low < high) {

      // high 큰 값, low 작은 값으로 설정
      if(array[low] > array[high]) {
        swap(array, low, high);
      }

      int pivot1 = array[low];
      int pivot2 = array[high];
      int lt = low + 1; // 피벗1보다 작은 요소들의 경계
      int gt = high - 1; // 피벗2보다 큰 요소들의 경계
      int i = low + 1; // 현재 검사 중인 요소

      // p1 시작점, p2 끝점
      // p1과 p2 사이를 탐색하면서 p1보다 작으면 왼쪽으로 보내고 p2보다 크면 오른쪽으로 보낸다.
      // 이 과정에서 lt++, gt-- 과정이 이루어진다.
      // 탐색을 마치면 p1, p2를 위치를 재조정한다.
      // 같은 과정을 반복한다.
      while(i <= gt) {
        if(array[i] < pivot1) {
          swap(array, i++, lt++);
        }
        else if(array[i] > pivot2) {
          swap(array, i, gt--);
        }
        else {
          i++;
        }
      }

      swap(array, low, --lt);
      swap(array, high, ++gt);

      // 재귀적으로 정렬
      dualPivotQuickSort(array, low, lt-1);
      dualPivotQuickSort(array, lt+1, gt-1);
      dualPivotQuickSort(array, gt+1, high);
    }
  }


  // 위치 교환 메소드
  public static void swap(int[] array, int index1, int index2) {
    int temp = array[index1];
    array[index1] = array[index2];
    array[index2] = temp;
  }


  public static void printArray(int[] array) {
    for(int number : array) {
      System.out.print(number + " ");
    }
    System.out.println();
  }

}

 

 

 

 

마무리

이번에는 Arrays.sort()에서 원시 타입 배열에 사용하는 듀얼 피벗 퀵 정렬을 정리했습니다.

다음에는 객체 배열에 사용하는 팀 정렬(TimSort)에 대해 정리하겠습니다.

감사합니다.