[알고리즘]퀵 정렬(Quick Sort)

퀵정렬이란?

퀵정렬은 이름그대로 빠른정렬, 즉 다른 정렬알고리즘에 비해 빠르다고 할 수 있습니다.

다른원소와의 비교를 통해 정렬이 이루어지므로 비교정렬에 속하고,

같은 수가 있는 경우 같은 수의 순서가 달라질 수 있어서 불안정 정렬에 속합니다.

ex) 5(1), 5(2), 3, 2, 1 -> 1, 2, 3, 5(2), 51(1)

 

시간복잡도

최악의 경우 O(n^2)

평균 O(n log n)

 

알고리즘

1. 임의의 수(pivot)를 고른다.
2. 피벗을 기준으로 두 수를 비교하여 왼쪽에는 pivot보다 작은 수, 오른쪽에는 pivot보다 큰 수가 오도록 분할한다.
3. 분할된 리스트 가운데에 피벗을 위치 시키고, 양쪽 리스트에 대해 재귀적으로 수행한다.

예제

• 가장 오른쪽에 있는 4를 pivot으로 정함.
• pivot을 제외하고 가장 왼쪽의 5와 오른쪽의 1을 비교합니다.
• 왼쪽은 피봇보다 작은 수, 오른쪽은 피봇보다 큰수여야 하므로 5,1을 교환합니다.

• 왼쪽 수는 오른쪽으로, 오른쪽 수는 왼쪽으로 이동하여 두 수를 비교한다.
• 왼쪽 수, 오른쪽 수 둘다 피봇보다 작으므로 교환하지 않는다.
• 왼쪽 포인팅을 오른쪽으로 한칸 옮기고, 오른쪽은 그대로 가리키며 비교한다.
  (왼쪽은 정상적으로 피봇보다 작은 위치에 있고, 오른쪽은 피봇보다 작기때문에 왼쪽으로 이동해야하기 때문)
• 7,2를 비교했을때 7는 피봇보다 크고, 2는 피봇보다 작으므로 교환한다.

• 왼쪽위치가 오른쪽 위치보다 커지면 왼쪽위치의 값과 피벗값을 교환한다
• 피봇을 기준으로 왼쪽은 피봇보다 작은 수의 리스트, 오른쪽은 피봇보다 큰 수의 리스트가 됨

• 피봇을 제외한 나머지 리스트에 대해 재귀적으로 위와같은 과정을 반복해주면 정렬 완료

소스코드(c++)

#include <iostream>

using namespace std;

int arr[] = {5,3,7,6,2,1,4};

void QuickSort(int arr[], int left, int right){
    if(left>=right){
        return;
    }

    int pivot = right; //마지막 원소를 pivot으로 설정
    int i = left;
    int j = pivot-1;

    while(i<=j){
        if(arr[i]>arr[pivot] && arr[j]<arr[pivot]){ //왼쪽이 pivot보다 크고, 오른쪽이 pivot보다 작으면 교환
            swap(arr[i], arr[j]);
            i++;j--;
        }
        else if(arr[i]>arr[pivot] && arr[j]>arr[pivot]){ //둘다 pivot보다 크면 오른쪽 포인터만 이동
            j--;
        }
        else if(arr[i]<arr[pivot] && arr[j]<arr[pivot]){  //둘다 pivot보다 작으면 왼쪽 포인터만 이동
            i++;
        }
        else{  //교환이 필요하지 않은 경우 넘어
            i++;j--;
        }
    }
    swap(arr[i],arr[pivot]);  //pivot과 i위치 교환
    QuickSort(arr, left, j);
    QuickSort(arr, j+2, right);

}

int main(){
    int len = sizeof(arr)/sizeof(int);

    QuickSort(arr, 0, len-1);

    for(int i = 0; i<len; i++){
        cout<<arr[i];
    }
}

코드에서는 임의로 가장 오른쪽 수를 pivot이라고 했지만, 가능하다면 최적의 pivot값을 찾은 뒤 pivot을 가장 오른쪽으로 보내어 진행하는 것이 가장 좋은 방법입니다.