퀵 정렬 알고리즘(Quick Sort)

인프런 - 파이썬으로 배우는 알고리즘 기초 강의 이미지

✔ 퀵 정렬(Quick Sort)

퀵 정렬은 분할 정복(divide and conquer) 방법을 통해 정렬하는 알고리즘이다.

간단히 얘기하면, 하나의 원소를 기준으로 기준 앞은 작은 모든 원소들이 오고, 뒤에는 큰 모든 원소들이 오도록

리스트를 둘로 분할하여 정렬하는 방법이다.

 

정렬하려는 리스트 가운데서 하나의 원소를 고른다. 고른 원소를 Pivot(피벗)이라 부른다.

피벗 기준 앞에서 큰 값을 찾고, 기준 뒤에는 작은 값을 찾아 교환하면서

피벗 앞에는 작은 원소들이 오게 하고 뒤에는 큰 원소들이 오도록 정렬을 진행한다.

분할 정복(divide and conquer)
그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법

 

✔ 퀵 정렬 동작 과정

왼쪽 → 오른쪽 순으로 봐주시기 바랍니다.

 

 

 

1. 리스트의 중간 값을 Pivot(피벗)으로 선정하고 피벗 기준으로 왼쪽과 오른쪽으로 나뉜다
   피벗 기준 왼쪽은 피벗 값보다 작은 값, 오른쪽 피벗 값보다 큰 값이 오도록 진행한다
2. left는 첫 번째 원소부터 피벗 값보다 큰 값을 찾을 때까지 증가시켜주며 찾고,
   right는 마지막 원소부터 피벗 값보다 작은 값을 찾을 때까지 감소시켜주며 찾는다
   찾은 큰 값과 작은 값을 교환해준다
3. left, right가 교차하면 새로운 피벗을 선정하고 왼쪽과 오른쪽으로 나뉜다.
4. 2번부터 다시 반복하며 정렬을 반복

※ 피벗 값을 선정하는 기준은 첫 번째, 중간, 마지막 원소를 선택할 수 있다. 이 글에서는 중간 값으로 선택했다.

 

✔ 퀵 정렬 구현(C++)

#include <iostream>
using namespace std;

const int LEN = 7;
int arr[LEN] = {2, 9, 5, 6, 4, 1, 7};

void QuickSort(int *arr, int left, int right) {
    int i = left, j = right;
    int pivot = arr[(left+right) / 2];
    int temp;
    
    while(i <= j) {	// 엇갈릴 때까지 반복
        while(arr[i] < pivot) i++;	// 피벗보다 큰 값을 만날 때까지
        while(arr[j] > pivot) j--;	// 피벗보다 작은 값을 만날 때까지
        
        if(i <= j) {	// 큰 값이 작은 값보다 왼쪽에 있으면
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            
            i++;
            j--;
        }
    }
    // 재귀(recursion)
    if(left < j) QuickSort(arr, left, j);
    if(i < right) QuickSort(arr, i, right);
}

int main() {
    QuickSort(arr, 0, LEN-1);
    
    for(int i : arr)
        cout << i << " ";
    return 0;
}

 

✔ 퀵 정렬 시간 복잡도

퀵 정렬의 시간 복잡도는 아래와 같다.

$$ O(NlogN) $$

퀵 정렬의 최악 시간 복잡도는 아래와 같다.

$$ O(N^2) $$

 

최악의 경우는 정렬하고자 하는 배열이 오름차순, 내림차순으로 정렬된 상태라면 분할이 되지 않아

O(N^2) 시간 복잡도를 가지는데 이를 개선하는 방법으로 중위법을 이용해 분할하는 방법입니다.

 

위에서 피벗 값을 첫 번째, 중간, 마지막 원소를 선정한다고 했는데 중간을 선택하는 중위법을 이용하여 분할한다.

이 방법을 사용하면 중앙에서 분할될 가능성이 높아 전체적으로 정렬의 성능이 좋아진다.

하지만 반드시, 100%인 보장은 아니다.

시간 복잡도에 대한 좀 더 자세한 내용은 아래의 내용에서 확인하세요.
시간 복잡도

 

 

 

🔗 Reference

• 퀵 정렬
• 위키 백과(퀵 정렬)