[알고리즘] 정렬 알고리즘 - QuickSort(퀵 정렬)

책 [파이썬으로 쉽게 풀어쓴 자료구조; 최영규, 천인국 지음]을 참고하여 작성하였습니다. 

 

QuickSort; 퀵 정렬

• 평균적으로 매우 빠른 수행 속도
• 병합 정렬과 같이 분할-정복법 사용
• 하지만 병합 정렬과는 다르게 균등 분할할 필요 없다
• 리스트 안의 한 요소를 피벗(pivot), 즉 기준점으로 삼고 이 값을 기준으로 작은 숫자는 왼쪽으로, 큰 숫자는 오른쪽으로 옮긴다
  (오름차순일 경우)
• 그런 다음 순환 호출하여 부분 리스트들을 정렬한다
• 불안정정렬, 별도의 메모리 공간 필요하지 않는다
  cf. 안정성: 입력 데이터에 동일한 킷값을 갖는 레코드가 여러 개 존재할 경우 정렬 후에도 이들의 상대적인 위치가 바뀌지 않는 것

https://www.youtube.com/watch?v=ClG4xjwQ0BM

- 시간 복잡도

• 최선의 경우: 리스트 분할이 가운데에서 이루어져 k번(log_2 n)의 분할 * 평균 n번의 비교로 O(nlog_2 n)
• 최악의 경우: 리스트가 불균형하게 나누어진 경우(이미 정렬된 상황) 배열의 크기만큼의 n번의 패스 * 한 패스당 n번의 비교로 O(n^2)
• 평균적으로는 O(nlog_2 n)로 다른 O(nlog_2 n) 알고리즘과 비교했을 때 가장 빠른 것
  ∵ 불필요한 데이터 이동 줄이고 먼 거리의 데이터 교환, 한번 결정된 피벗은 연산에서 제외
• 불균형 분할을 완화하기 위해 피벗을 리스트의 중앙값에 가깝도록 선택, 예를 들어 리스트의 왼쪽, 오른쪽, 중간 3개 중 중간 값 선택

- 자세한 구현 방법

 

피벗은 중간 값으로 설정하는 것이 이미 정렬된 배열에 대해서 성능 저하를 완화해 주지만 이 책에서는 가장 왼쪽의 수로 설정하였다.

 

- 리스트 시작 인덱스를 left, 리스트 가장 끝 위치를 right라고 할 때 탐색해 나갈 인덱스를 설정: low(왼->오), high(오->왼)

- low는 피벗보다 큰 수를 찾는 인덱스, high는 피벗보다 작은 수를 찾는 인덱스

- 수를 찾을 때까지 계속 이동(low++, high--)

- 각각 수를 찾으면 low 위치의 수와 high 위치의 수를 교환
- low와 high가 역전되면 이동을 멈추고, 수가 구분되었으니 high 위치의 수와 피벗을 교환

책 [파이썬으로 쉽게 풀어쓴 자료구조; 최영규, 천인국 지음] p.445

https://jjunsu.tistory.com/187

[알고리즘] 퀵 정렬(Quick Sort) - pivot(피벗)을 중앙으로 잡았을 때

   static void quick_sort(int[] arr, int l, int r) {
        int left = l;
        int right = r;
        int mid = (l + r) / 2;
        int pivot = arr[mid];
        while (left <= right) {
            while (arr[left] < pivot) left++;
            while (arr[right] > pivot) right--;
            if (left <= right) {
                swap(arr, left, right);
                left++;
                right--;
            }
        }

        if(l <= right) quick_sort(arr, l, right); // while 문을 빠져 나왔을 땐 left == right
        if(r >= left) quick_sort(arr, left, r);
    }

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

https://st-lab.tistory.com/250

완전 자세한 설명 🔥

자바 [JAVA] - 퀵 정렬 (Quick Sort)

    private static void quick_sort(int[] arr, int left, int right) {
        if (left >= right) { // 요소 1개 이하이므로 정렬하지 않고 return
            return;
        }

        int p = partition(arr, left, right);
        quick_sort(arr, left, p);
        quick_sort(arr, p + 1, right);
    }

    private static int partition(int[] arr, int left, int right) {

        int low = left - 1;
        int high = right + 1;
        int pivot = arr[(left + right) / 2];

        while(true) {
            do {
                low++;
            } while(arr[low] < pivot);

            do {
                high--;
            } while(arr[high] > pivot && low <= high);


            if(low >= high) {
                return high;
            }

            swap(arr, low, high);
        }
    }


    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

 

이론을 이해했어도 그걸 코드화해서 생각하기는 쉽지 않는 것 같다. 위의 것도 조건문의 등호 유무까지 정확히 이해하는 게... 참 어렵다....!

https://www.acmicpc.net/problem/11004

여느 때와 다름 없이 입력 값들을 하나의 배열에 넣고 Arrays.sort()를 했더니 당연히 잘 돌아갔다. 그러고 다른 사람들의 코드를 보던 중 어떤 사람이 퀵 소트를 썼길래 '이때 알고리즘 활용해야지~'란 생각으로 퀵 소트(피벗은 단순하게 맨 처음 값으로 설정)만 똑같이 써 봤다. 근데 시간초과가 나는 것이다...! 분명히 복습하면서 본 퀵 소트는 평균적으로 매우 빠른 속도를 자랑한대서 시간 초과가 날 줄은 생각도 못했다. 그래서 두 가지 궁금한 점이 생겼다. 

 

-1. 피벗 설정을 중간 값으로 해 보면 될까? - (성공!)

-2. 평소에 쓰던 Arrays.sort()도 잘 됐는데 이건 알고리즘이 어떻게 되어 있을까?

Arrays.sort() - 이중 피벗 퀵 소트 알고리즘 사용

 

알고보니 Arrays.sort()는 이중피벗 퀵 소트로 돌아가고 있었다..! 

이중피벗 퀵 소트는 일반적인 퀵 소트를 보완하여 2개의 피벗을 사용하는 알고리즘이다. 리스트의 양쪽 끝에서 두 피벗을 선택하고, 항상 오른쪽 피벗이 왼쪽 피벗보다 크도록 설정한다. 그런 다음 이들을 중심으로 3개의 그룹으로 나눈다.

 

1. 왼쪽 피벗보다 작은 그룹

2. 오른쪽 피벗보다 큰 그룹

3. 그 사이 그룹

책 [파이썬으로 쉽게 풀어쓴 자료구조; 최영규, 천인국 지음] p.448

책 [파이썬으로 쉽게 풀어쓴 자료구조; 최영규, 천인국 지음] p.449

def dp_quick_sort(A, low, high):
    if low < high:
        lp, rp = partitionDP(A, low, high)
        dp_quick_sort(A, low, lp-1)
        dp_quick_sort(A, lp+1, rp-1)
        dp_quick_sort(A, rp+1, high)


def partitionDP(A, low, high):
    if A[low] > A[high]:  # 오른쪽 피벗이 왼쪽보다 작지 않아야 함
        A[low], A[high] = A[high], A[low]

    j = low + 1     # 왼쪽 피벗보다 작지 않은 최대 인덱스
    g = high - 1    # 오른쪽 피벗보다 크지 않은 최소 인덱스
    k = low + 1     # low+1부터 하나씩 증가
    lpVal = A[low]
    rpVal = A[high]
    while k <= g:
        if A[k] < lpVal:
            A[k], A[lpVal] = A[lpVal], A[k]
            j += 1

        elif A[k] >= rpVal:
            while A[g] > rpVal and k < g:
                g -= 1
            A[k], A[g] = A[g], A[k]

        if A[k] < lpVal:
            A[k], A[j] = A[j], A[k]
            j += 1
        k += 1

    j -= 1
    g += 1
    A[low], A[j] = A[j], A[low]
    A[high], A[g] = A[g], A[high]

    return j, g

 

이중피벗 퀵 소트의 이론적인 시간 복잡도는 일반적인 퀵 소트와 차이가 없다고 하지만, 일반적인 경우에 퀵 소트보다 성능이 우수하다고 한다. 결론: Arrays.sort()는 대단한 것이었다..^^!

 

cf. https://gobae.tistory.com/127

퀵 정렬(Quick Sort) 이란