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

 

 

 

 

 

알고리즘 개요 및 소개

Quick Sort Animaiton

퀵 정렬은 찰스 앤터니 리처드 호어가 개발한 정렬 알고리즘이다. 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속하며 대표적인 분할 정복 알고리즘이며 평균 속도는 O(N*logN)이며 최악의 속도는 O(N^2)이다.

 

Quick Sort 알고리즘의 핵심은 Pivot이며 이 Pivot에 따라 처리 속도가 달라질 수 있으며 Piovt은 첫 번째, 중간, 마지막, 랜덤으로 정하는 방법이 있다.  보통 Pivot은 중간값 혹은 평균값으로 지정한다.

 

Quick Sort 실행 순서

1. 리스트 가운데서 하나의 원소를 고른다. 이 원소가 Pivot이다.

2. 오른쪽(Right)는 오른쪽에서부터 왼쪽으로 돌면서 Pivot보다 작은 값(큰 값)을 찾는다.

3. 왼쪽(Left)는 왼쪽에서부터 오른쪽으로 돌면서 Pivot보다 큰 값(작은 값)을 찾는다.

4. 찾은 두 값을 Swap한다.

5. 2, 3, 4번을 계속 반복한 뒤 더 이상 진행할 수 없으면 Pivot값을 바꾼다.

 

Pivot 기준으로 왼쪽에 큰 값을 둘 것인지 작은 값을 둘 것인지에 따라 오름차순, 내림차순 정렬이 결정된다.

 

시간 복잡도	최악 O(N^2), 평균 최선 O(N*logN)
장점	매 단계에서 적어도 1개의 원소가 자기 자리를 찾는다.
단점	원소들 중 같은 값이 있는 경우 정렬 이후 순서가 초기화 다를 수 있는 불안정 정렬에 속한다. 이미 정렬이 되어 있는 상태에서는 O(N^2)의 결과가 나온다.

소스코드

#include<iostream>
#include<chrono>
constexpr int MAX_LIST = 10;
 
void quickSort(int* list, int begin, int end) {
    static int Circle = 0;
    
    if (begin >= end) return;
    int pivot = begin; //우선 pivot은 처음으로 한다.
    int left = begin+1;
    int right = end;
    int temp = 0;
 
    //왼쪽값이 오른쪽값보다 클 때까지(index)
    while (left <= right) {
        //왼쪽은 pivot보다 큰 숫자를 찾는다.
        while (list[pivot] > list[left]) {
            ++left;
        }
 
        //오른쪽은 pivot보다 작은숫자를 찾는다.
        while (list[pivot] < list[right]) {
            --right;
        }
 
        //오른쪽보다 왼쪽이크다면 Piovt값 교체
        if (left > right) {
            temp = list[right];
            list[right] = list[pivot];
            list[pivot] = temp;
        }
        else {
            //각 요소를 Swap
            temp = list[left];
            list[left] = list[right];
            list[right] = temp;
        }
    }
    ++Circle;
    std::cout << "Circle[" << Circle << "] ";
    for (int i = 0; i < MAX_LIST; ++i)
        std::cout << list[i] << " ";
    std::cout << std::endl;
 
    quickSort(list, begin, right-1);
    quickSort(list, right + 1, end);
}
int main() {
    int list[MAX_LIST] = { 6,8,7,9,3,4,2,1,10,5 };
 
    quickSort(list, 0, MAX_LIST-1);
 
    std::cout << "Result of Sort: ";
    for (auto i : list)
        std::cout << i << " ";
    std::cout << std::endl;
 
}
 

 

후기

Quick Sort를 마지막으로 기초 정렬 알고리즘을 한번씩 구현해보았다. 처음 Quick Sort를 배웠을 때 보다 좀 더 장단점을 확실히 알 수 있었고 나중에 까먹어서 코드로 구현을 못한다고 해도 원리는 알고 있으니 큰 문제가 없을 거 같다.

 

 

 

 

출처 및 레퍼런스

WiKi: https://ko.wikipedia.org/wiki/퀵_정렬

 

 

20.04.05 

code를 Color Scripter로 변경

20.04.22
글자 폰트 및 색상 변경