[이취코] ch06-3. 퀵 정렬

퀵 정렬은 매우 많이 사용되는 알고리즘으로 속도가 매우 빠르다

퀵 정렬과 합병(병합) 정렬은 프로그래밍 언어에서 정렬 라이브러리의 근간이 되는 알고리즘이기도하다

 

퀵정렬?

기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식이다

 

퀵정렬은 분할정복 알고리즘으로 분류되고, 합병정렬과 다른점은 각 부분 문제의 크기가 일정하지 않다는 것이다

(합병정렬은 일정 분할이다)

 

퀵 정렬에서는 피벗(pivot)이 사용된다

피벗은 큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 '기준'이다

퀵 정렬을 수행하기전에는 피벗을 어떻게 설정할것인지 반드시 명시해야한다

 

피벗을 설정하는 방식에는 여러가지가 있지만 우선 대표적인 호어 분할(Hoare Partition)방식을 기준으로 이해해보자

 

호어분할방식

- 리스트에서 첫 번째 데이터를 피벗으로 정한다

 

피벗을 설정한 후 

왼쪽에서부터는 피벗보다 큰 데이터를 찾고, 오른쪽에서부터는 피벗보다 작은 데이터를 찾는다

그리고 왼쪽의 큰 데이터와 오른쪽의 작은 데이터 위치를 교환해준다

 

그림으로 살펴보자

 

초기 데이터가 있다. 여기서 피벗은 맨 앞 데이터인 5가 된다

 

 

(1)

왼쪽에서는 5(피벗)보다 큰 데이터, 오른쪽에서는 5보다 작은 데이터를 찾는다

 

왼쪽에서는 5보다 큰 7, 오른쪽에서는 5보다 작은 4를 선택하고 (8은 5보다 크니까 패스) 두 위치를 바꿔준다

 

(2)

계속해서 왼쪽은 5보다 큰 수 , 오른쪽은 5보다 작은수를 찾는다

 

왼쪽에서는 9, 오른쪽에서는 2의 위치를 바꿔준다

→ 5 4 2 0 3 5 6 9 7 8

 

이렇게 반복하다보면

 

오른쪽과 왼쪽에서 찾는 값이 엇갈린 경우가 나온다

이 경우 작은 데이터와 피벗의 위치를 서로 변경한다

 

그럼 이제 피벗을 기준으로 왼쪽은 피벗보다 작은 데이터 / 오른쪽은 피벗보다 큰 데이터가 위치하게 된다

(피벗의 오른쪽에는 피벗보다 큰 데이터가 위치하도록 하는 작업을 분할 Divide 또는 파티션 Partition 이라고 한다)

 

피벗을 기준으로 나뉜 왼쪽, 오른쪽을 이제 다시 각각 피벗을 새로 설정해 방금 한것같이 정렬을 한다

(왼쪽 피벗 :1 / 오른쪽 피벗: 6)

그럼 또 새로운 피벗을 기준으로 왼쪽(작은데이터) 오른쪽(큰데이터)가 나뉠것이고 다시 피벗을 설정해 또 정렬해주면 된다.

계속해서 분할하고 정렬을 하다보면 최종적으로 오름차순 정렬이 된다

 

 

 

퀵 정렬을 코드로 구현하면 (cpp)

#include <iostream>

using namespace std;

int n = 10;
int arr[10] = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};

void quickSort(int* arr, int start, int end) {
    if (start >= end) return; // 원소가 1개인 경우 종료
    int pivot = start; // 피벗은 첫 번째 원소
    int left = start + 1;
    int right = end;
    while (left <= right) {
        // 피벗보다 큰 데이터를 찾을 때까지 반복
        while (left <= end && arr[left] <= arr[pivot]) left++;
        // 피벗보다 작은 데이터를 찾을 때까지 반복
        while (right > start && arr[right] >= arr[pivot]) right--;
        // 엇갈렸다면 작은 데이터와 피벗을 교체
        if (left > right) swap(arr[pivot], arr[right]);
        // 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
        else swap(arr[left], arr[right]);
    }
    // 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
    quickSort(arr, start, right - 1);
    quickSort(arr, right + 1, end);
}

int main(void) {
    quickSort(arr, 0, n - 1);
    for (int i = 0; i < n; i++) {
        cout << arr[i] << ' ';
    }
}

 

퀵 정렬의 시간복잡도

 

퀵 정렬의 시간복잡도는 O(nlogn)이다 

* 컴퓨터과학에서 log는 밑이 2인 로그를 의미한다

하지만 최악의 경우 O(n^2)가 될 수도 있다

 

데이터가 무작위일 경우 빠르게 작동할 수 있지만 이미 정렬되어있는 데이터인 경우 느리게 작동한다