[C++ 알고리즘] 퀵정렬

퀵정렬은 숫자 하나(pivot)를 골라서 올바른 자리에 넣어가며 정렬을 진행한다. 이때 배열을 쪼개가며 재귀적으로 정렬을 하기 때문에 최종적인 시간 복잡도는 O(nlogn)이다. 

동작 과정

이론적인 내용에 들어가기 앞서 어떤식으로 동작하는지 확인해보도록 하자. 아래와 같이 {5, 4, 1, 7, 6, 2} 배열이 있다고 했을 때 맨 왼쪽을 피봇으로 잡고 left와 right를 아래와 같이 각각 지정한다.

여기서의 left는 pivot보다 작아야하고, right는 pivot보다 커야한다. 이제 left를 하나씩 옮기며 5보다 큰 수가 처음으로 나오는 지점을 찾으면 아래와 같은 상태가 된다.

right는 pivot보다 커야한다고 했는데 이미 pivot보다 작다. 그러니 여기서 멈춰준다.

이제 left와 right가 역전되지 않았다면(left<right) 두 수를 바꿔준다.

이제 계속 위와 같이 left와 right를 움직여준다. left는 5보다 큰 수를 찾을 때 까지, right는 5보다 작거나 같은 수를 찾을 때 까지 움직인다.

left와 right가 역전되었으니 두 수를 바꾸지 않는다. 두 수가 역전된 지금 순간을 잘 관찰하면 right부터 왼쪽은 5보다 작은 수, left부터 오른쪽은 5보다 큰 수라는 것을 알 수 있다. 즉 5의 올바른 위치는 right와 left사이이다. 

이제 right와 pivot을 바꿔주면 5는 올바른 위치에 들어갔다고 보장할 수 있다.

이후 재귀적으로 5의 왼쪽 배열과 오른쪽 배열에 대해 정렬을 진행한다. 이렇게 하나하나 올바른 위치에 배치해나가는 것이 바로 퀵정렬이다.

코드

코드는 다음과 같다. pivot은 가장 왼쪽 원소를 선택하도록 했다.

#include <iostream>
#include <vector>
using namespace std;

void swap(vector<int>& arr, int st, int en) {
    int tmp = arr[st];
    arr[st] = arr[en];
    arr[en] = tmp;
}

int parti(vector<int>& arr, int st, int en) {
    int pivot = arr[st];
    int left = st + 1;
    int right = en;

    while (left <= right) {
        while (left <= en && arr[left] <= pivot)left++;
        while (right > st && arr[right] > pivot)right--;

        if (left < right)swap(arr, left, right); //앞서 2, 7을 바꾼 코드
    }
    swap(arr, right, st); //앞서 5와 2를 바꾼 코드
    return right; //정렬이 완료된 5의 위치 리턴
}

void quickSort(vector<int>& arr, int st, int en) {
    if (st >= en)return;

    int partition = parti(arr, st, en);
    quickSort(arr, st, partition - 1); //정렬이 완료된 5의 왼쪽 부분 정렬
    quickSort(arr, partition + 1, en); //정렬이 완료된 5의 오른쪽 부분 정렬
}
int main() {
    vector<int> arr = { 5,4,1,7,6,2 };
    quickSort(arr, 0, arr.size() - 1);
    
    for (auto k : arr) {
        cout << k << " ";
    }
}

 

 특징

퀵 정렬의 시간복잡도는 O(nlogn)이다. 그런데 같은 O(nlogn)인 다른 정렬보다도 빠르다. 왜냐하면 앞서 봤듯이 pivot의 올바른 위치를 탐색하며 배열을 조금씩 정렬하고(2, 7 스왑), 5와 같이 위치가 확정된 원소들은 이후 정렬에서 제외되기 때문이다.

하지만 pivot을 기준으로 쪼개나가기 때문에 pivot이 계속해서 배열 내 가장 작은 값으로 선정된다면 O(n^2)의 시간복잡도를 가지게 된다. 

 실습

직접 짠 퀵정렬 코드는 아래 문제를 통해 테스트할 수 있다.

https://school.programmers.co.kr/learn/courses/30/lessons/42748

프로그래머스

 

함께보면 좋은 글

퀵소트가 빠른 이유: Locality의 관점에서
https://sdcodebase.tistory.com/34

Locality의 관점에서 Quick sort가 Merge sort보다 빠른이유

https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

[알고리즘] 퀵 정렬(quick sort)이란 - Heee's Development Blog