[자료구조] 퀵 정렬(Quick Sort)

퀵 정렬(Quick Sort)

퀵 정렬(Quick Sort)는 이름처럼 엄청난 속도를 자랑하는 매우 빠른 정렬 알고리즘이다. 퀵 정렬은 분할 정복(Divide and Conquer) 알고리즘 중의 하나로, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속하는 알고리즘이다.

 

정렬 과정

 

---

 

정렬 과정

1. 리스트 안의 임의의 요소 하나를 선택한다. 이를 피봇(pivot)이라 한다.
2. left는 왼쪽에서 오른쪽으로 가면서 피봇보다 큰 수를 찾는다
3. right는 오른쪽에서 왼쪽으로 가면서 피봇보다 작은 수를 찾는다.
4. 찾은 지점에서 left와 right를 교환한다.
5. 위의 2,3,4과정 left와 right가 교차할 때 까지 반복한다.
6. left와 right가 교차하면 피봇(pivot)과 right를 교환한다.
7. 이렇게 되면 피봇의 왼쪽에는 피봇보다 작은수가, 피봇의 오른쪽에는 피봇보다 큰 수가 위치한다.
8. 피봇을 기준으로 왼쪽과 오른쪽 리스트 두개로 나눠 위의 과정을 반복 수행한다.
9. 이렇게 순환 과정을 통해 분할된 리스트의 크기가 0이나 1이 되면 수행을 종료한다

 

---

 

Java 코드

public static void quickSort(int[] arr, int left, int right) {
        if (left < right) {
            int pivot_index = partition(arr, left, right);

            quickSort(arr, left, pivot_index - 1);
            quickSort(arr, pivot_index + 1, right);
        }
    }

    public static int partition(int[] arr, int left, int right) {
        int low = left + 1;
        int high = right;
        int pivot = arr[left];

        while (low <= high) {
            while (low <= right && arr[low] < pivot) {
                low++;
            }
            while (high >= left && arr[high] > pivot) {
                high--;
            }
            if (low < high) {
                swap(arr, low, high);
            }
        }
        swap(arr, left, high);
        return high;
    }

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

 

---

 

퀵 정렬의 장점 

• 속도가 빠르다 퀵 정렬은 평균 속도가 O(NlongN)이며 O(NlogN)의 속도를 가지는 다른 정렬 알고리즘과 비교했을 때도 가장 빠르다.
• 퀵 정렬은 O(logN)만큼의 메모리를 필요로 하기 때문에 추가 메모리 공간이 필요하지 않다.

 

퀵 정렬의 단점

• 정렬된 리스트에 대해서는 퀵 정렬의 불균형 분할에 의해 오히려 수행 시간이 더 많이 걸린다. 최악의 경우 O(n^2)의 시간 복잡도를 가진다. 퀵 정렬의 불균형 분할을 방지하기 위하여 피벗을 선택할 때 더욱 리스트를 균등하게 분할할 수 있는 데이터를 선택한다.

퀵 정렬의 불균형 분할을 방지하기 위하여 피벗을 선택할 때 더욱 리스트를 균등하게 분할할 수 있는 데이터를 선택한다. 

 

---

 

퀵 정렬 시간복잡도

 

N = 2^k개의 원소를 정렬한다고 가정할때,
최선의 경우, 배열이 균등하게 이등분 되어 순환 호출의 깊이는 k가 된다.
각각의 단계에서 pivot을 올바르게 위치시키기 위한 비교 연산 횟수는 평균적으로 N번
이루어지므로 총 연산횟수는 O(kN)이다. 이때, k = logN이므로 O(kN) = O(nlogn)이다.

배열이 이미 정렬되어 있는 경우 혹은 매번 선택한 pivot이 항상 제일 작거나 제일 클 때 최악의 시간복잡도를 가진다. 배열에서 원소가 한개씩만 분리되어 순환 호출의 깊이가 N이 된다. 각각의 단계에서 비교 연산이 평균적으로 N번 이루어지므로 총 연산횟수는 O(N^2)이다.