[algorithm] 정렬 2. 퀵 정렬

https://kghworks.tistory.com/175

[알고리즘] 정렬 1. 병합 정렬

이어지는 포스팅이다.

 

목차

• 퀵 정렬
• 퀵 정렬 성능 특성
• 퀵 정렬 알고리즘 개선

---

퀵 정렬

 퀵 정렬은 가장 널리 사용되는 정렬 알고리즘이다. 구현이 쉽고, 다양한 형태의 input이 가능하다. 응용상황에서 다른 정렬 알고리즘들보다 (병합, 선택, 삽입 정렬) 빠르고, 추가적인 메모리 사용을 하지 않는 in-place sorting인 장점이 있다. 그러나 부주의한 구현으로 인해서 기대성능을 내지 못할 수 있기 때문에 주의해야 한다. (잘못 구현하면 N^2) 크기 N인 정렬은 평균 NlogN 성능을 낸다. 

 

기본 알고리즘

퀵 정렬 기본 알고리즘

 

 분할 정복 알고리즘이다. 배열을 분할 (partitioning)하고 각 분할된 배열을 독립적으로 정렬한다. 병합 정렬은 부분 배열을 정렬 후 다시 병합할 때 정렬작업이 추가 적으로 필요하지만, 퀵 정렬은 부분배열만 정렬하면, 전체 배열이 정렬되는 장점이 있다.

 

import org.algorithm.lib.StdRandom;

public class Quick {

    public static void sort(Comparable[] a) {
        StdRandom.shuffle(a); // 입력 배열을 섞는다.
        sort(a, 0, a.length - 1);
    }

    private static void sort(Comparable[] a, int lo, int hi) {
        if (hi <= lo) return; // 배열의 크기가 1 이하면 종료

        int j = partition(a, lo, hi); // 분할

        sort(a, lo, j - 1); // 왼쪽 부분 배열을 정렬
        sort(a, j + 1, hi); // 오른쪽 부분 배열을 정렬
    }
}

 

parition() : 분할, 재배열

퀵 정렬의 parition()

partition()은 한번의 분할 작업을 의미하는 메서드로, partition()이 한번 실행되면 배열의 항목 하나의 최종 위치가 확정된다. 

• a[j]의 j는 전체 배열 a의 최종 정렬 위치
• a[lo]~a[j-1]은 a[j]보다 작거나 같음
• a[j+1]~a[hi]는 a[j]보다 큼

partition()의 알고리즘 순서는 아래와 같다.

1. 배열에서 임의의 항목 a[lo]를 분할 기준으로 선택
2. a[lo]를 배열의 정렬 최종 위치로 이동시키기 위해 parition() 시작
3. 배열의 왼쪽 끝부터 a[lo]보다 크거나 같은 원소를 찾을 때까지 오른쪽으로 스캔
4. 배열의 오른쪽 끝부터 a[lo]보다 작거나 같은 원소를 찾을 때까지 왼쪽으로 스캔
5. 두 원소 교환
6. 3~4 반복
7. 두 스캔의 위치가 엇갈리면 (크로스) a[lo]와 a[j]를 교환
8. 최종 위치 j 반환

/*
 * Copyright © 2000–2019, Robert Sedgewick and Kevin Wayne.
 * Last updated: Thu Aug 11 09:06:38 EDT 2022.
 */

/**
 * The {@code Quick} class provides static methods for sorting an
 * array and selecting the ith smallest element in an array using quicksort.
 * <p>
 * For additional documentation, see
 * <a href="https://algs4.cs.princeton.edu/23quicksort">Section 2.3</a>
 * of <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
 *
 * @author Robert Sedgewick
 * @author Kevin Wayne
 */
public class Quick {

    // This class should not be instantiated.
    private Quick() {
    }

    /**
     * Rearranges the array in ascending order, using the natural order.
     *
     * @param a the array to be sorted
     */
    public static void sort(Comparable[] a) {
        StdRandom.shuffle(a);
        sort(a, 0, a.length - 1);
        assert isSorted(a);
    }

    // quicksort the subarray from a[lo] to a[hi]
    private static void sort(Comparable[] a, int lo, int hi) {
        if (hi <= lo) return;
        int j = partition(a, lo, hi);
        sort(a, lo, j - 1);
        sort(a, j + 1, hi);
        assert isSorted(a, lo, hi);
    }

    // partition the subarray a[lo..hi] so that a[lo..j-1] <= a[j] <= a[j+1..hi]
    // and return the index j.
    private static int partition(Comparable[] a, int lo, int hi) {
        int i = lo;
        int j = hi + 1;
        Comparable v = a[lo];
        while (true) {

            // find item on lo to swap
            while (less(a[++i], v)) {
                if (i == hi) break;
            }

            // find item on hi to swap
            while (less(v, a[--j])) {
                if (j == lo) break;      // redundant since a[lo] acts as sentinel
            }

            // check if pointers cross
            if (i >= j) break;

            exch(a, i, j);
        }

        // put partitioning item v at a[j]
        exch(a, lo, j);

        // now, a[lo .. j-1] <= a[j] <= a[j+1 .. hi]
        return j;
    }

    /**
     * Rearranges the array so that {@code a[k]} contains the kth smallest key;
     * {@code a[0]} through {@code a[k-1]} are less than (or equal to) {@code a[k]}; and
     * {@code a[k+1]} through {@code a[n-1]} are greater than (or equal to) {@code a[k]}.
     *
     * @param a the array
     * @param k the rank of the key
     * @return the key of rank {@code k}
     * @throws IllegalArgumentException unless {@code 0 <= k < a.length}
     */
    public static Comparable select(Comparable[] a, int k) {
        if (k < 0 || k >= a.length) {
            throw new IllegalArgumentException("index is not between 0 and " + a.length + ": " + k);
        }
        StdRandom.shuffle(a);
        int lo = 0, hi = a.length - 1;
        while (hi > lo) {
            int i = partition(a, lo, hi);
            if (i > k) hi = i - 1;
            else if (i < k) lo = i + 1;
            else return a[i];
        }
        return a[lo];
    }


    /***************************************************************************
     *  Helper sorting functions.
     ***************************************************************************/

    // is v < w ?
    private static boolean less(Comparable v, Comparable w) {
        if (v == w) return false;   // optimization when reference equals
        return v.compareTo(w) < 0;
    }

    // exchange a[i] and a[j]
    private static void exch(Object[] a, int i, int j) {
        Object swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }


    /***************************************************************************
     *  Check if array is sorted - useful for debugging.
     ***************************************************************************/
    private static boolean isSorted(Comparable[] a) {
        return isSorted(a, 0, a.length - 1);
    }

    private static boolean isSorted(Comparable[] a, int lo, int hi) {
        for (int i = lo + 1; i <= hi; i++)
            if (less(a[i], a[i - 1])) return false;
        return true;
    }


    // print array to standard output
    private static void show(Comparable[] a) {
        for (int i = 0; i < a.length; i++) {
            StdOut.println(a[i]);
        }
    }

    /**
     * Reads in a sequence of strings from standard input; quicksorts them;
     * and prints them to standard output in ascending order.
     * Shuffles the array and then prints the strings again to
     * standard output, but this time, using the select method.
     *
     * @param args the command-line arguments
     */
    public static void main(String[] args) {
        String[] a = StdIn.readAllStrings();
        Quick.sort(a);
        show(a);
        assert isSorted(a);

        // shuffle
        StdRandom.shuffle(a);

        // display results again using select
        StdOut.println();
        for (int i = 0; i < a.length; i++) {
            String ith = (String) Quick.select(a, i);
            StdOut.println(ith);
        }
    }

}

 

parition(a, 0, 15) 실행 결과

 

 추가적인 작업용 배열을 사용하면 구현이 쉬워지나, 메모리 공간 오버헤드가 있고, 분할마다 새로운 배열을 생성하는 시간 비용도 든다. 따라서 퀵 정렬은 in-place sorting으로 구현한다. 

partition()을 본격 시작하기 전에 입력배열을 섞는 것을 추천한다. 섞지 않을 거면 입력배열에서 기준값 v를 랜덤하게 선택할 수 있게 하는 방법도 있다.

 

주의사항 1. 경계선 넘지 않기

partition()의 a[lo]가 최대(최소) 값이라면, 배열의 크기를 넘어가지 않을 수 있는 조건을 넣는 것이 필요하다. 경계검시 j == lo 조건은 불필요하다. 왼쪽으로 스캔하다 a[lo]가 가장 좌측일 때, 경계에 도달하면 어차피 자기 자신보다 작을 수없기 때문에 반복문을 빠져나올 수 있다.

마찬가지로 오른쪽으로 스캔할 때의 종료 조건도 생략이 가능하다.

 

주의사항 2. 루프의 종료

루프의 종료 조건을 반드시 정해주어야한다. 스캔이 엇갈리면 루프가 종료되도록 했다. 스캔이 엇갈렸는지 검사할 때,  분할 기준항목 v와 값이 같은 원소가 있을 수 있다는 것도 고려해야 한다.

 가장 좋은 방법은 좌측부터는 크거나 같은 항목을 찾을 때까지 스캔하고, 우측부터는 작거나 같은 항목을 찾을 때까지 스캔하는 것이다. 이는 v와 동일한 값을 가지는 항목과도 교환할 수 있는 경우가 발생하지만, 특정 환경에서 N^2 시간이 발생하는 것을 방지할 수 있다. 즉 위에서 less()를 작거나 같은 조건을 만족하는지 검사하도록 수정하면 된다.

 

주의사항 3. 재귀호출의 종료

 알고리즘에서 재귀호출에는 반드시 종료 조건을 가져야 한다. 퀵정렬에서 가장 많이 하는 실수가 무한루프에 빠지는 것이다. 매 루프마다 반드시 항목하나가 정위치에 가야 하고, 만일 정위치에 가는 로직이 잘못되면, 무한 루프에 빠지게 된다.

---

퀵 정렬 성능 특성

 병합정렬, 셸 정렬은 내부 루프에서 데이터를 이동하는 연산이 들어가기 때문에 퀵 정렬보다 느리다. 퀵 정렬은 내부 루프 (partition())에서 단순하게 v와 값의 크기 비교만 하기 때문에 더 빠르다.

 

@State(Scope.Thread)
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MICROSECONDS)
public class CompareSortingQuickMerge {

    private Double[] generateRandomArray(int i) {
        Double[] arr = new Double[i];
        for (int j = 0; j < i; j++) {
            arr[j] = Math.random();
        }
        return arr;
    }

    @Benchmark
    public void sorting_merge() {
        Double[] arr = generateRandomArray(1000);
        Merge.sort(arr);
    }

    @Benchmark
    public void sorting_quick() {
        Double[] arr = generateRandomArray(1000);
        Quick.sort(arr);
    }

}

 

Benchmark                               Mode  Cnt    Score   Error  Units
CompareSortingQuickMerge.sorting_merge  avgt    5  109.097 ± 1.204  us/op
CompareSortingQuickMerge.sorting_quick  avgt    5   83.490 ± 1.173  us/op

 

퀵 정렬이 병합 정렬보다 빠르다.

 

 배열을 얼마나 잘 분할하는지에 따라 비교 연산 수를 줄이 수 있다. 즉 어떤 항목을 분할 항목 v로 채택하는지에 달려있다. 분할이 균형적으로 이루어지지 않으면, 극단적으로 비효율적으로 변한다. 예를 들어 첫 번째 부분배열의 v가 해당 부분 배열의 가장 작은 원소이고, 두 번째 부분배열의 v가 해당 부분배열의 가장 작은 원소이고,.... 이렇게 반복된다면 partition() 마다 최대 1개의 항목만이 제자리에 정렬된다. 따라서 입력배열을 최초에 무작위로 한번 섞는 작업이 성능에 중요한 영향을 미칠 수 있다. 

 가장 이상적인 경우는 parition()마다 배열이 매번 1/2로 분할되는 경우이다.

 

---

퀵 정렬 알고리즘 개선

퀵 정렬은 1960년대 C.A.R Hoare에 의해 개발된 이후 많이 연구되고 개선되었다. 이제는 더 빠른 알고리즘을 찾는 것은 희망 없는 파랑새 찾기와 다를 바 없다고 한다. 개선을 위해 고려해 볼 만한 사항을 나열해 보자면 아래와 같다.

 

삽입 정렬과 결합

 작은 부분배열에서는 삽입 정렬이 퀵 정렬보다 빠르다. 그러나 위 구현에서는 작은 부분배열에 대해서도 재귀적으로 Quick.sort()를 호출하고 있다. 따라서 작은 부분배열일 경우 삽입정렬을 수행하도록 알고리즘을 수정해 볼 수 있다.  일반적으로 부분배열의 크기가 5 ~ 15일 때 작은 부분배열로 정의할 수 있다. 

 

private static void sort(Comparable[] a, int lo, int hi) {
    // if (hi <= lo) return; // 배열의 크기가 1 이하면 종료
    if (hi <= lo + M) { 
        Insertion.sort(a, lo, hi); 
        return; 
    } // 삽입 정렬로 전환

    int j = partition(a, lo, hi); // 분할
    
    sort(a, lo, j - 1); // 왼쪽 부분 배열을 정렬
    sort(a, j + 1, hi); // 오른쪽 부분 배열을 정렬
}

 

3-중앙값 분할

v를 부분배열의 중앙값을 대략적으로 계산하여 선정하는 방법이다. 랜덤 항목 3개를 선택해 중앙값을 구한다. 

3-중앙값 분할 퀵 정렬 시각화

 

 

엔트로피 최적 정렬

배열의 데이터가 대부분 중복이라면 어떨까. 만일 부분 배열의 데이터가 모두 같다면, 굳이 정렬을 진행할 이유가 없다. partition()을 세 부분으로 분할할 수 있게 개선한다. v보다 작은 부분배열, v와 같은 부분배열, v보다 큰 부분배열이다. 

 

세부분으로 parition()한 결과

• 왼쪽에서 오른쪽으로 배열 스캔
• a[lo..lt-1] : v보다 작은 원소들
• a[lt..i-1] : v와 같은 원소들
• a[gt+1..hi] : v보다 큰 원소들
• i를 lo부터 시작해서 아래 세 가지 조건 검사, 실행
• a[i]가 v보다 작으면, a[lt]와 a[i]를 교환하고, lt와 i 증가
• a[i]가 v보다 크면, a[gt]와 a[i]를 교환하고 gt를 감소
• a[i]가 v와 같으면, i를 증가

/*
 * Copyright © 2000–2019, Robert Sedgewick and Kevin Wayne.
 * Last updated: Thu Aug 11 09:06:38 EDT 2022.
 */
 
/**
 * The {@code Quick3way} class provides static methods for sorting an
 * array using quicksort with 3-way partitioning.
 * <p>
 * For additional documentation, see
 * <a href="https://algs4.cs.princeton.edu/23quicksort">Section 2.3</a>
 * of <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
 *
 * @author Robert Sedgewick
 * @author Kevin Wayne
 */
public class Quick3way {

    // This class should not be instantiated.
    private Quick3way() {
    }

    /**
     * Rearranges the array in ascending order, using the natural order.
     *
     * @param a the array to be sorted
     */
    public static void sort(Comparable[] a) {
        StdRandom.shuffle(a);
        sort(a, 0, a.length - 1);
        assert isSorted(a);
    }

    // quicksort the subarray a[lo .. hi] using 3-way partitioning
    private static void sort(Comparable[] a, int lo, int hi) {
        if (hi <= lo) return;
        int lt = lo, gt = hi;
        Comparable v = a[lo];
        int i = lo + 1;
        while (i <= gt) {
            int cmp = a[i].compareTo(v);
            if (cmp < 0) exch(a, lt++, i++);
            else if (cmp > 0) exch(a, i, gt--);
            else i++;
        }

        // a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi].
        sort(a, lo, lt - 1);
        sort(a, gt + 1, hi);
        assert isSorted(a, lo, hi);
    }


    /***************************************************************************
     *  Helper sorting functions.
     ***************************************************************************/

    // is v < w ?
    private static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }

    // exchange a[i] and a[j]
    private static void exch(Object[] a, int i, int j) {
        Object swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }


    /***************************************************************************
     *  Check if array is sorted - useful for debugging.
     ***************************************************************************/
    private static boolean isSorted(Comparable[] a) {
        return isSorted(a, 0, a.length - 1);
    }

    private static boolean isSorted(Comparable[] a, int lo, int hi) {
        for (int i = lo + 1; i <= hi; i++)
            if (less(a[i], a[i - 1])) return false;
        return true;
    }


    // print array to standard output
    private static void show(Comparable[] a) {
        for (int i = 0; i < a.length; i++) {
            StdOut.println(a[i]);
        }
    }

    /**
     * Reads in a sequence of strings from standard input; 3-way
     * quicksorts them; and prints them to standard output in ascending order.
     *
     * @param args the command-line arguments
     */
    public static void main(String[] args) {
        String[] a = StdIn.readAllStrings();
        Quick3way.sort(a);
        show(a);
    }

}

엔트로피 최적 정렬 시각화