Arrays.sort()가 내부적으로 사용하는 3개의 Sorting

  • Insertion Sort
  • Merge Sort
  • QuickSort


  1. Insertion Sort와 Merge Sort를 섞은것은 Tim Sort
    • primitive 원소 정렬
    • 최선 O(N)
    • 최악 O(N^2)
    • 평균 O(NlogN)
  2. Insertion Sort와 Quick Sort를 섞은 것은 Dual Quick Sort
    • Object 원소 정렬
    • 최선 O(N)
    • 최악 O(NlogN)
    • 평균 O(NlogN)


Dual pivot quick sort

2011년 Java7이 나온 이래로, 전통적인 quick sort 알고리즘에서 DualPivotQuickSort 알고리즘이 사용되었다.

Insertion Sort는 정렬할 요소의 수가 적을 때 더 빠른 실행 시간을 가지며 요소의 수가 47개 이하 일 때 Insertion Sort를 수행합니다.

이름에서 알 수 있듯이 DualPivotQuickSort 알고리즘은 2개의 피벗을 선택합니다. 배열을 2개의 피벗을 중심으로 세 부분으로 분할합니다.


LP : 왼쪽 피벗, RP : 오른쪽 피벗

LP보다 낮은 1그룹, LP~RP 사이의 그룹(LP, RP는 제외), RP 보다 큰 그룹

LP < RP 성립


// Java program to implement
// dual pivot QuickSort
class GFG{
  
static void swap(int[] arr, int i, int j)
{
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
  
static void dualPivotQuickSort(int[] arr, 
                               int low, int high)
{
    if (low < high)
    {
          
        // piv[] stores left pivot and right pivot.
        // piv[0] means left pivot and
        // piv[1] means right pivot
        int[] piv;
        piv = partition(arr, low, high);
          
        dualPivotQuickSort(arr, low, piv[0] - 1);
        dualPivotQuickSort(arr, piv[0] + 1, piv[1] - 1);
        dualPivotQuickSort(arr, piv[1] + 1, high);
    }
}
  
static int[] partition(int[] arr, int low, int high)
{
    if (arr[low] > arr[high])
        swap(arr, low, high);
          
    // p is the left pivot, and q 
    // is the right pivot.
    int j = low + 1;
    int g = high - 1, k = low + 1,
        p = arr[low], q = arr[high];
          
    while (k <= g) 
    {
          
        // If elements are less than the left pivot
        if (arr[k] < p)
        {
            swap(arr, k, j);
            j++;
        }
          
        // If elements are greater than or equal
        // to the right pivot
        else if (arr[k] >= q) 
        {
            while (arr[g] > q && k < g)
                g--;
                  
            swap(arr, k, g);
            g--;
              
            if (arr[k] < p)
            {
                swap(arr, k, j);
                j++;
            }
        }
        k++;
    }
    j--;
    g++;
      
    // Bring pivots to their appropriate positions.
    swap(arr, low, j);
    swap(arr, high, g);
  
    // Returning the indices of the pivots
    // because we cannot return two elements
    // from a function, we do that using an array.
    return new int[] { j, g };
}
  
// Driver code
public static void main(String[] args)
{
    int[] arr = { 24, 8, 42, 75, 29, 77, 38, 57 };
      
    dualPivotQuickSort(arr, 0, 7);
      
    System.out.print("Sorted array: ");
    for (int i = 0; i < 8; i++)
        System.out.print(arr[i] + " ");
          
    System.out.println();
}
}
  
// This code is contributed by Gourish Sadhu


tim sort

참조 지역성 원리 - CPU가 미래에 원하는 데이터를 예측하여 속도가 빠른 장치인 캐시 메모리에 담아 놓는데 이때의 예측률을 높이기 위하여 사용하는 원리.

Heap sort - 참조 지역성이 좋지 않은 정렬, 한 위치에 있는 요소를 해당 요소의 인덱스 두 배 또는 절반인 요소와 반복적으로 비교, 캐시 메모리에서 예측하기 어려움.

Merge sort - 참조 지역성의 원리를 잘 만족하나 입력 배열 크기만큼의 메모리 추가 사용 단점.

Quick sort - 참조 지역성이 좋으며 메모리를 추가로 사용하지 않지만 최악의 경우 O(n^2)이 될 수 있다는 단점.

Tim sort의 등장

2002년 Software Engineer Tim Peters에 의하여 등장. Insertion sort와 Merge sort를 결합하여 만든 정렬.

Insertion sort는 참조 지역성 원리를 잘 만족하고 작은 덩어리로 잘라 각각의 덩어리를 Insertion sort로 정렬한 뒤 병합하면 좀 더 빠르지 않을까? (기본 아이디어)

Binary Insertion sort

Tim sort에서 사용하는 Insertion sort는 Binary Insertion sort이다. 삽입해야 할 위치를 찾을 떄까지 비교하는 대신, 앞의 원소들은 모두 정렬되어 있다는 전제를 기반으로 이분 탐색을 진행하여 위치를 찾는다. 한 원소를 삽입할 때 O(n)번의 비교를 진행하는 대시 O(logn)번의 비교를 진행하기에 작은 n에 대하여 좀 더 시간을 절약할 수 있다.

Merge

배열을 맨 앞 원소부터 풅으며 run의 크기가 minrun보다 작을 경우 Binary Insertion sort를 진행하고 증가하는 run인지, 감소하는 run인지에 따라 조건에 맞게 최대한 run의 크기를 키우고, 감소하는 run의 경우 뒤집어서 하나의 증가하는 run을 생성했다. 이제 효율 적인 방법으로 run들을 병합할 차례이다.

비슷한 크기의 덩어리와 병합하여 효율성을 증대시킨 것을 알 수 있다. 스택에 피라미드 형태로 크기 순서로 run을 담는다.

2 Run Merge

Merge sort의 가장 큰 단점이었던 추가 메모리를 n 사용한다는 점 또한 극복해야할 문제이다. 두개의 run중 하나를 복사하여 포인터 두개를 사용하여 비교하며 순서대로 채운다. 그럼 메모리 사용을 줄이고 최적화를 통해 병합을 수행할 필요가 없는 구간을 먼저 계산한다

Galloping

하나의 원소를 갖고 One pair at a time mode로 3번 연속 병합이 진행될 때 Galloping mode로 전환되고 1,2,4,8과 같이 2^k로 뛰어 넘으며 대소 비교를 진행하고 run이 연속적으로 병합되지 않을 경우 One pair at a time mode로 돌아가 다시 하나씩 비교를 진행한다.

마무리 - 완전히 무작위인 데이터에 대해서는 속도가 빠른 편은 아니지만 일정한 패턴이 있는 일반적인 데이터에 대해서는 빠른 성능을 보여주고 안정적이며 최악의 사간 복잡도가 O(nlogn)이기에 많은 언어에서 표준 정렬 알고리즘으로 채택하여 사용하고 있다.


출처

https://defacto-standard.tistory.com/38 https://awdesh.medium.com/dual-pivot-quick-sort-javas-default-sorting-algorithm-for-primitive-types-77342e1df5e5 https://www.geeksforgeeks.org/dual-pivot-quicksort/ https://d2.naver.com/helloworld/0315536