[Algorithm] 퀵 정렬(Quick Sort)

퀵 정렬이란?

정렬해야하는 요소들을 분할시켜서 정렬하는 방법. 특정한 값을 기준으로, 큰 수와 작은 수를 반으로 나눠(두 집합으로) 정렬하는 방법이다.

퀵 정렬은 pivot(기준 값) 을 사용한다.(보통 가장 앞의 값을 pivot 값 으로 설정한다)

pivot값을 기준으로, pivot 값 왼편은 pivot 값 보다 작은 집합. 오른편은 pivot 값 보다 큰 집합으로 나눈다.(pivot값을 기준 값으로 제외시켜놓고, 왼쪽에서 오른쪽으로 탐색(pivot 값 보다 큰 값 찾음)하고 맨 오른쪽에서 왼쪽으로 탐색(pivot 값 보다 작은 값 탐색)하여, 서로의 위치를 바꿔준다.

만약 큰 값의 index와 작은 값의 index가 엇갈리게 되면(작은 값의 index가 큰 값의 index보다 작게되면), pivot과 엇갈린 작은 값을 바꿔주면, pivot을 기준으로 2 집단으로 나뉘게 된다.)

나눠진 2개의 집합에서 각각 pivot 값을 잡고, 각각 또 2개의 집합으로 분할한다.(pivot 값 왼편은 pivot 값 보다 작은 집합. 오른편은 pivot 값 보다 큰 집합)

#include <stdio.h>
#include <iostream>
using namespace std;

int number = 10;
int arr[] = {1,6,9,8,2,4,10,3,7,5}; // 정렬할 배열

void quickSort(int *data, int start, int end){ // start는 집합의 시작 부분, end는 끝 부분
    // 원소가 한 개인 경우
    if(start >= end){
        return;
    }

    int key = start; // pivot 값 설정(첫 번째 원소)
    int i = start + 1; // pivot을 제외하고, 왼쪽부터 오른쪽으로 탐색하기 위한 index
    int j = end; // 맨 오른쪽에서 왼쪽으로 탐색하기 위한 index

    int temp; // 두 수를 교환하기 위한 임시 변수

    // 엇갈릴 때 까지 반복 
    while(i <= j){
        // pivot 값 보다 작다면, 오른쪽으로 이동(왼쪽에서 오른쪽으로 탐색하는 경우)
        // pivot 값 보다 큰 값을 만날 때 까지 반복
        while(i <= end && data[i] <= data[key]){
            i++;
        }
        // pivot 값 보다 크다면, 왼쪽으로 이동(오른쪽에서 왼쪽으로 탐색하는 경우)
        // pivot 값 보다 작은 값을 만날 때 까지 반복
        // 범위를 넘어가지 않도록 j는 최대 start까지만
        while(j > start && data[j] >= data[key]){
            j--;
        }
        // 엇갈린 상태면 키 값과 교체
        if(i>j){
            temp = data[j];
            data[j] = data[key];
            data[key] = temp;
        } else{ // 엇갈리지 않은 상태라면, 둘의 값을 바꿔줌 
            temp = data[i];
            data[i] = data[j];
            data[j] = temp;
        }
    }
    // 엇갈려서 while문을 빠져나왔으면, pivot 값을 기준으로 왼쪽 집합, 오른쪽 집합 각각 quick sort
    quickSort(data, start, j-1);
    quickSort(data, j+1, end);

}
int main(void){

    quickSort(arr, 0, number-1);
    for(int i=0;i<number;i++){
        cout<<arr[i]<<endl; 
    }
    return 0;
}

시간복잡도

퀵 정렬은 계속 해서 반으로 분할시키면서 정렬하기 때문에 매우 효율적이다.(ex. 10 10 = 100 이 걸리지만, 이것을 전부 하나만 남도록 나누어주면, 1 1을 10번 한 것과 같으므로, 10 밖에 걸리지 않는다.)

따라서 시간 복잡도는 데이터의 개수가 N이라고 하면, N(데이터의 개수) logN(반 씩 나눠져 들어가기 때문에) 즉, O(N logN)이다.(지수의 밑은 2)

그러나 pivot값 설정에 따라 최악의 경우(이미 정렬이 된 경우)에는 O(N^2)이 될 수도 있다. 그렇지만 일반적으로는 가장 빠른 정렬이다.

reference: https://www.youtube.com/watch?v=O-O-90zX-U4&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=5