[java] dual pivot quick sort/정렬

무작위로 삽입되어 있는 Data를 정렬할때에 jdk1.8이상이라면 stream을 이용하면 편하게 정렬할 수 있다.

int[] intArray = {5, 2, 7, 1, 0};
int[] result = Arrays.stream(intArray).sorted().toArray();

jdk1.8을 사용할 수 없다면 아래와 같이 dual pivot quick sort를 작성하여 호출하는 식으로 사용하면 된다.

    public static void intArraySwap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    public static void intArrayDualPivotQuickSort(int[] arr, int left, int right) {
        if(left <= right) {
            if (arr[left] > arr[right])
                intArraySwap(arr, left, right);

            int pivot1 = arr[left], pivot2 = arr[right];
            int l, k, g;

            l = k = left + 1;
            g = right - 1;

            while (k <= g) {
                if (arr[k] < pivot1) {
                    intArraySwap(arr, k, l);
                    l++;
                }
                else {
                    if(arr[k] > pivot2) {
                        while ( (arr[g] > pivot2) && (k < g)) g--;

                        intArraySwap(arr, k, g);
                        g--;

                        if (arr[k] < pivot1) {
                            intArraySwap(arr, k, l);
                            l++;
                        }
                    }
                }
                k++;
            } // end while

            l--; g++;

            intArraySwap(arr, left, l);
            intArraySwap(arr, right, g);

            intArrayDualPivotQuickSort(arr, left, l - 1);
            intArrayDualPivotQuickSort(arr, l + 1, g - 1);
            intArrayDualPivotQuickSort(arr, g + 1, right);
        }
    }

다만 위 내용은 각 배열의 타입에 맞도록 작성되어야 한다.