Sort/정렬 - Quick Sort/퀵 정렬

퀵 정렬은 일반적으로 사용되고 있는 아주 빠른 정렬 알고리즘임

 

알고리즘

먼저 배열을 두 그룹으로 나눕니다 그룹을 나누는 순서는 임의의 피벗을 선택한후 피벗을 기준으로 피벗보다

큰 값은 피벗 뒤, 피벗보다 작은 값은 피벗 앞에 원소를 넣어준다. 

글을 읽는 것 보단 코드를 보는게 이해가 빠를것이다.

void swap(int *x, int *y){int tmp = *x; *x = *y; *y = tmp;}

void partition(int arr[], int left, int right){
    int pl = left;
    int pr = right;
    int pivot = arr[(pl + pr) / 2];
    do{
        while(arr[pl] < pivot) pl++;
        while(arr[pr] > pivot) pr--;
        if(pl <= pr){
            swap(arr[pl],arr[pr]);
            pl++;
            pr--;
        }
    }while(pl <= pr);
}

코드를 보면 알 수 있듯이 pl변수에 배열의 시작 인덱스 pr변수에 배열의 끝 인덱스를 대입해준다음

arr[pl]의 값이 피벗 보다 작을때 pl++을 해주고 arr[pr]의 값이 피벗 보다 클 때 pr--를 해준다
이렇게 했을때 pl은 피벗보다 큰 값을 가지고 있는 인덱스에서 멈추고 pr은 피벗보다 작은 값을 가지고 있는

인덱스에서 멈춘다 그리고 이때 pl <= pr 을 만족해주면 값을 swap해준다. 이것을 pl <= pr 일 때 즉 커서가 교차되기

전까지 반복해준다. 이 작업을 완료하면 피벗을 기준으로 큰 값은 뒤에 작은 값은 앞에 위치하게 된다.
여기서 조금만더 하면 퀵 정렬 알고리즘인데 여기서 배열을 두 그룹으로 나누는 알고리즘을 나누어진 그룹에대해

재귀적으로 반복 해주면 퀵 정렬 알고리즘이 된다.

이때 요소의 개수가 1개인 그룹은 더 이상 그룹을 나눌 필요가 없으니 요소의 개수가 2개 이상인 그룹만 나누면 된다.
따라서 이렇게 나누면 된다,

1. pr이 left보다 오른쪽에 있으면 left < pr 왼쪽 그룹을 나누고

2. pl이 right보다 왼쪽에 있으면 pl < right 오른쪽 그룹을 나눈다.

 

코드

void swap(int *x, int *y){int tmp = *x; *x = *y; *y = tmp;}

void Quick_Sort(int arr[], int left, int right){
    int pl = left;
    int pr = right;
    int pivot = arr[(pl + pr) / 2];
    do{
        while(arr[pl] < pivot) pl++;
        while(arr[pr] > pivot) pr--;
        if(pl <= pr){
            swap(arr[pl],arr[pr]);
            pl++;
            pr--;
        }
    }while(pl <= pr);
    if(left < pr) Quick_Sort(arr,left,pr);
    if(pl < right) Quick_Sort(arr,pl,right);
}

퀵소트의 시간복잡도는 보통 O(n log n)이지만 정렬할 배열의 초기 값이나 피벗의 값에 따라 변할수도 있다.
예를 들어서 매번 단 하나의 요소와 나머지 요소로 나누어 지면(피벗이 원소의 최대값이나 최소값)
n번의 분할이 필요하다. 따라서 최악의 시간 복잡도는 O(n^2)이다.

그래서 이것을 보완 할 수 있는 방법이 있는데 많은 방법이 있지만,

여기서 설명할것은 중간 값 퀵 소트(Median_Quick_Sort)이다. 

중간 값 퀵 소트는 배열의 시작, 중간, 끝 인덱스의 값을 정렬한 다음

가운데 값을 피벗으로 정한 후 가운데 값과 끝에서 두 번째 요소를 교환한 후 퀵 소트를 실행하는 것이다.

그러면 원소 처음 중간 끝 원소 3개는 정렬이 끝났으니

pl, pr 의 스캔은 pl은 left + 1(left는 피벗 이하), pr은 right - 2(피벗이 right - 1, 피벗이상이 right)부터 시작 할 수 있다.

이렇게 하면 스캔할 요소를 3개식 줄일 수 있고, 그냥 퀵 소트를 사용했을때 보다 조금 더 빠른속도를 기대할수 있다.

 

코드

void swap(int *x, int *y){int tmp = *x; *x = *y; *y = tmp;}

void Median_Set(int arr[], int pl, int mid, int pr){
    if(arr[pl] > arr[mid]) swap(arr[pl],arr[mid]);
    if(arr[mid] > arr[pr]) swap(arr[mid],arr[pr]);
    if(arr[pl] > arr[mid]) swap(arr[pl],arr[mid]);
}

void Median_Quick_Sort(int arr[], int left, int right){ 중앙값 퀵 소트
    int pl = left + 1, pr = right - 2, mid = (left + right) / 2;
    Median_Set(arr,left,mid,right);
    if(right - left + 1 <= 3) return; // 만약 원속의 개수가 3개이거나 3개 이하면 3개의 숫자를 정렬하는것 만으로 정렬이 끝남.
    int pivot = arr[mid];
    swap(arr[mid],arr[right - 1]);
    do{
        while(arr[pl] < pivot) pl++;
        while(arr[pr] > pivot) pr--;
        if(pl <= pr){
            swap(arr[pl],arr[pr]);
            pl++;
            pr--;
        }
    }while(pl <= pr);
    if(left < pr) Median_Quick_Sort(arr,left,pr);
    if(pl < right) Median_Quick_Sort(arr,pl,right);
}

 

전체코드

#include <iostream>
using namespace std;

void swap(int *x, int *y){int tmp = *x; *x = *y; *y = tmp;}

void Quick_Sort(int arr[], int left, int right){ // 보통 퀵 정렬
    int pl = left;
    int pr = right;
    int pivot = arr[(pl + pr) / 2];
    // 퀵 정렬의 분할 과정 출력
    /*printf("arr[%d] ~ arr[%d] : {", left, right);
    for(int i = left; i < right; i++){
        printf("%d, ",arr[i]);
    }
    printf("%d}\n",arr[right]);*/
    do{
        while(arr[pl] < pivot) pl++;
        while(arr[pr] > pivot) pr--;
        if(pl <= pr){
            swap(arr[pl],arr[pr]);
            pl++;
            pr--;
        }
    }while(pl <= pr);
    if(left < pr) Quick_Sort(arr,left,pr);
    if(pl < right) Quick_Sort(arr,pl,right);
}

void Median_Set(int arr[], int pl, int mid, int pr){ // 중앙 값 퀵 소트 전 3개 원소 정렬
    if(arr[pl] > arr[mid]) swap(arr[pl],arr[mid]);
    if(arr[mid] > arr[pr]) swap(arr[mid],arr[pr]);
    if(arr[pl] > arr[mid]) swap(arr[pl],arr[mid]);
}

void Median_Quick_Sort(int arr[], int left, int right){ // 중앙 값 퀵 소트
    int pl = left, pr = right, mid = (pl + pr) / 2;
    Median_Set(arr,left,mid,right);
    if(right - left + 1 <= 3) return; // 만약 원속의 개수가 3개이거나 3개 이하면 3개의 숫자를 정렬하는것 만으로 정렬이 끝남.
    int pivot = arr[mid];
    do{
        while(arr[pl] < pivot) pl++;
        while(arr[pr] > pivot) pr--;
        if(pl <= pr){
            swap(arr[pl],arr[pr]);
            pl++;
            pr--;
        }
    }while(pl <= pr);
    if(left < pr) Median_Quick_Sort(arr,left,pr);
    if(pl < right) Median_Quick_Sort(arr,pl,right);
}

int main(){ // 실행 함수
    int arr[] = {32,12,54,99,76,87,23,98,16,50}; // size = 10
    cout << "Before sorting : ";
    for(auto i : arr){
        cout << i << ' ';
    }
    cout << '\n';
    cout << "Sorting process.\n";
    Median_Quick_Sort(arr,0,9); // 원소가 10개 들어있으니 0~9 인덱스까지 원소가 있음 
    cout << "After  sorting : ";
    for(auto i : arr){
        cout << i << ' ';
    }
    return 0;
}

퀵 소트는 외우기도 크게 어렵지 않고 이론 정도는 알고 있으면 좋으니 추천하는 정렬 알고리즘 중 하나이다.

참고로 C++ STL에 들어 있는 sort 함수의 기본 틀이 퀵 소트이고 거기에서 이것저것 최적화를 더해 구현했다.