Java Quick Sort

Quick Sort

빠른 정렬 (꼬리 재귀 + Hoare 파티션 + 삽입 정렬) in 자바

 

1. 소개

파이썬 Quick Sort 최적화에 따른 속도: choiseokwon.tistory.com/233

Python QuickSort 최적화에 따른 속도

우선, 이 글에서 작성한 Quick Sort는 파이썬에서 결과가 가장 빠르게 나온,

Tail recursive + Hoare partition scheme + Insertion Sort 버전이다.

 

2. 보조 함수

우선 Generic을 이용하기 위해 보조 함수들을 만든다.

(한 함수로 여러가지 타입 처리하기)

1. less (a < b?)

private static <T extends Comparable<T>> boolean less(T v, T w) {
    return v.compareTo(w) < 0;
}

2. greater (a > b?)

private static <T extends Comparable<T>> boolean greater(T v, T w) {
    return v.compareTo(w) > 0;
}

3. swap (array[i], array[j] = array[j], array[i])

private static <T> void swap(T[] array, int idx, int idy) {
    T swap = array[idx];
    array[idx] = array[idy];
    array[idy] = swap;
}

4. isSorted (array == array.sorted())

private static <T extends Comparable<T>> boolean isSorted(T[] array) {
    for (int i = 0; i < array.length - 1; i++) {
        if (greater(array[i], array[i + 1])) {
                return false;
        }
    }
    return true;
}

 

3. 구현

1. Insertion Sort (삽입 정렬)

private static <T extends Comparable<T>> T[] insertSort(T[] array, int low, int high) {
    for (int i = low; i < high; i++) {
        int j = i;
        while (j > 0 && less(array[j], array[j - 1])) {
            swap(array, j, j - 1);
            j--;
        }
    }

    return array;
}

2. Hoare 파티션 기법 (중간 값이 피봇)

(모든 케이스(정렬, 랜덤, 내림차순...)에서 가운데 값 선택이 평균적으로 제일 빨랐음.)

private static <T extends Comparable<T>> int partition(T[] array, int low, int high) {
    T pivot = array[(low + high) / 2];
    int i = low - 1;
    int j = high + 1;
    while (true) {
        i++;
        while (less(array[i], pivot)) {
            i++;
        }
        j--;
        while (greater(array[j], pivot)) {
            j--;
        }

        if (i >= j) {
            return j;
        }

        swap(array, i, j);
    }

}

3. quickSort 함수

private static <T extends Comparable<T>> T[] quickSort(T[] array, int low, int high) {
    while (high - low > 16) {  # while high > low
        int p = partition(array, low, high);
        quickSort(array, low, p);
        low = p + 1;
    }

    # return array
    return insertSort(array, low + 1, high + 1);
}

 

4. 테스트

1. 500,000개 랜덤 정수 배열: ~0.14초

(파이썬에서 ~0.14초)

public static void main(String[] args) {
    Random rd = new Random();
    
    Integer[] test = new Integer[500_000];
    for (int i = 0; i < test.length; i++) {
        test[i] = rd.nextInt();
    }
    
    long startTime = System.nanoTime();
    Integer[] result = quickSort(test, 0, test.length - 1);
    long stopTime = System.nanoTime();
    
    double elapsedTimeInSecond = (double) (stopTime - startTime) / 1_000_000_000;
    System.out.println("걸린 시간: " + elapsedTimeInSecond + "s");

    // System.out.println(Arrays.toString(result));
    boolean sorted = isSorted(result);
    System.out.println("정렬 결과: " + sorted);
}

/* 결과
걸린 시간: 0.1421483s

정렬 결과: true
*/

 

2. 500,000개 랜덤 실수 배열: ~0.18초

public static void main(String[] args) {
    Random rd = new Random();
    
    Double[] test = new Double[500_000];
    for (int i = 0; i < test.length; i++) {
        test[i] = rd.nextDouble();
    }
    
    long startTime = System.nanoTime();
    Double[] result = quickSort(test, 0, test.length - 1);
    long stopTime = System.nanoTime();
    
    double elapsedTimeInSecond = (double) (stopTime - startTime) / 1_000_000_000;
    System.out.println("걸린 시간: " + elapsedTimeInSecond + "s");

    // System.out.println(Arrays.toString(result));
    boolean sorted = isSorted(result);
    System.out.println("정렬 결과: " + sorted);
}

/* 결과
걸린 시간: 0.1778896s

정렬 결과: true
*/

 

풀 소스 확인