[Sorting] Quick Sort (퀵 정렬)

원리

---

• 퀵정렬은 Divide & Conquer algorithm중 하나로 "pivot"이라는 기준값을 지정하여 pivot을 기점으로 배열을 partitioning하여 정렬하는 알고리즘이다.
• 보통 pivot은 배열의 맨 앞 원소를 지정하는데 두번째 원소부터 오른쪽으로 pivot보다 큰값을 찾고, 맨 마지막 원소부터 왼쪽으로 pivot보다 작은 값을 찾아나간다.
• 만약 왼쪽으로 훑던 것이 오른쪽을 추월한다면 pivot과 오른쪽 기준을 swap하고 그렇지 않다면 왼쪽 오른쪽 값을 swap한다.

 

Complexity

---

모든 원소를 한번씩 훑기때문에 O(n), 배열을 반으로 계속 divide하기 때문에 O(log2n)으로 총 O(nlogn)이라는 빠른 속도를 가진다.

 

주의사항 - Worst Case !

---

배열이 이미 정렬된 상태라면 partitioning이 이루어지지않고 모든원소를 검사하는 것이 n-1번 이루어지기 때문에 nO(n)이나 O(n^2)로 버블정렬이나 삽입정렬과 같은 속도를 같게된다. (매우 안좋음!!)

 

코드 및 설명

---

void quick_sort(int *data, int start, int end) {
    if(start >= end) return; //원소가 한개인 경우 return

    int pivot = start; //맨 앞 원소 pivot설정
    int i = pivot + 1; //pivot 다음 원소부터 지정
    int j = end; //맨 뒤 원소 지정

    while(i <= j) {
        while(i <= end && data[i] <= data[pivot]) i++; //pivot보다 큰 값 찾을때까지 i증가
        while(j > start && data[j] >= data[pivot]) j--; //pivot보다 작은 값 찾을때까지 j감소

        if(i > j) { //i와 j가 엇갈린경우
            swap(data[pivot], data[j]); //pivot과 index j의 원소 swap
            k--;
        }else {
            swap(data[i],data[j]);
        } //그렇지 않은 경우 i<->j swap
    }
    
    // partitioning && 계속 정렬해나감
    quick_sort(data, start, j-1);
    quick_sort(data, j+1, end);
}

 

< Example Code >

#include <iostream>
using namespace std;
void print(int *data, int size) {
    for (int i = 0; i < size; i++) {
        cout << data[i] << "\n";
    }
}
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void quick_sort(int *data, int start, int end) {
    if(start >= end) return; //원소가 한개인 경우 return

    int pivot = start; //맨 앞 원소 pivot설정
    int i = pivot + 1; //pivot 다음 원소부터 지정
    int j = end; //맨 뒤 원소 지정

    while(i <= j) {
        while(i <= end && data[i] <= data[pivot]) i++; //pivot보다 큰 값 찾을때까지 i증가
        while(j > start && data[j] >= data[pivot]) j--; //pivot보다 작은 값 찾을때까지 j감소

        if(i > j) { //i와 j가 엇갈린경우
            swap(data[pivot], data[j]); //pivot과 index j의 원소 swap
            k--;
        }else {
            swap(data[i],data[j]);
        } //그렇지 않은 경우 i<->j swap
    }
    
    // partitioning && 계속 정렬해나감
    quick_sort(data, start, j-1);
    quick_sort(data, j+1, end);
}

int main() {
    int arr[] = {8,1,5,10,4,3,50,13,2,7};
    quick_sort(arr, 0, size);
    print(arr, size);
    return 0;
}