정렬 알고리즘 - 퀵 정렬(Quick Sort)

퀵 정렬

• 정렬 알고리즘 중 가장 빠른 알고라즘 중의 하나
• 찰스 앤터니 리처드 호어(C.A.R Hoare)가 명명
• 각 그룹에 피벗(pivot) 설정과 그룹 나눔을 반복하며 모든 그룹이 1명이 되면 정렬을 마침
• 피벗(pivot): 그룹을 나누는 기준을 말하며, 피벗은 마음대로 선택할 수 있고, 왼쪽 그룹과 온쪽 그룹 어디에 들어가도 상관없음
• 분할 정복 알고리즘이므로 재귀 호출을 사용하여 구현
• 분할 정복 알고리즘: 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다.
• 불안정 정렬에 속한다.

 

과정

1. 리스트 안에 있는 한 요소를 선택한다. (요소 = pivot)
2. 피벗을 기준으로 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮겨지고 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 옮겨진다. (피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰 요소들)
3. 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다.
   • 분할된 부분 리스트에 대해 순환 호출을 이용하여 정렬을 반복한다.
   • 부분 리스트레서도 다시 피벗을 정하고 피벗을 기준으로 2개의 부분 리스트로 나누는 과정을 반복한다.
4. 부분 리스트들이 더 이상 분할이 불가능할 때까지 반복한다.
   • 리스트의 크기가 0이나 1이 될 때까지 반복한다.

 

퀵 정렬 알고리즘 예제

퀵 정렬 알고리즘 장단점

장점

• 속도가 빠르다
  • 시간 복잡도가 $O(nlog_{2}n)$를 가지는 다른 정렬 알고리즘과 비교했을 때도 가장 빠르다.
• 추가 메모리 공간을 필요로 하지 않는다.
  • 퀵 정렬은 $O(\log n)$만큼의 메모리를 필요로 한다.

단점

• 정렬된 리스트에 대해 퀵 정렬의 불균형 분할에 의해 오히려 수행시간이 더 많이 걸릴 수 있다.

 

정렬 알고리즘 시간 복잡도 비교

 

Python Code

def quicksort(x):
    if len(x) <= 1:
        return x

    pivot = x[len(x) // 2]
    less = []
    more = []
    equal = []
    for a in x:
        if a < pivot:
            less.append(a)
        elif a > pivot:
            more.append(a)
        else:
            equal.append(a)

    return quicksort(less) + equal + quicksort(more)

 

Java Code

public void quickSort(int[] arr, int left, int right) {
    int i, j, pivot, tmp;
    if (left < right) {
        i = left;   j = right;
        pivot = arr[(left+right)/2];
        //분할 과정
        while (i < j) {
            while (arr[j] > pivot) j--;
            // 이 부분에서 arr[j-1]에 접근해서 익셉션 발생가능함.
            while (i < j && arr[i] < pivot) i++;

            tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
        //정렬 과정
        quickSort(arr, left, i - 1);
        quickSort(arr, i + 1, right);
    }
}