Quick sort (퀵소트)

1. Quick sort 란 ?

 

분할정복을 이용한 정렬 알고리즘입니다.

정렬 알고리즘 중 O(NlogN) 으로 빠른편에 속하는 알고리즘입니다.

 

2. Quick Sort 의 자세한 설명

https://www.techiedelight.com/quicksort/ 참조

1) Pivot을 Array의 가장 마지막 원소로 선정합니다.

2) [ Pivot 보다 작은 원소들 - Pivot - Pivot 보다 큰 원소들 ] 의 형태가 되도록 배열을 분할합니다.

3) 이 과정을 Pivot 기준 왼쪽배열, 오른쪽 배열을 나누어 반복합니다. (배열을 더이상 나눌 수 없을 때 까지)

 

3. Code

 

#include <iostream>

using namespace std;

// This is quick sort algorithm.

// a Array 를 출력해주는 함수입니다.
void printArray(int a[], int arraySize) {
    for (int i = 0; i < arraySize; i++)
    {
        cout << a[i] << ' ';
    }
    cout << endl;
}

// a와 b의 값을 바꾸어주는 함수입니다.
void swap(int *a, int *b){
    int t;
    t = *a;
    *a = *b;
    *b = t;
}

// Array를 [ Pivot보다 작은값 - Pivot - Pivot보다 큰값 ] 의 형태로 분할합니다.
// 여기서는 pivot 을 주어진 배열의 가장 마지막 값(right) 로 선정하였습니다.
int partition(int arr[], int left, int right){
    int pivot = right;
    int pivotIdx = left;
    for (int i = left; i < right; i++) {   
        if ( arr[i] < arr[pivot] ) {
            swap(arr[i], arr[pivotIdx]);
            printArray(arr, 7);
            pivotIdx++;
        }
    }

    swap(arr[pivotIdx], arr[pivot]);
    return pivotIdx; 
}

// 실제 정렬 함수입니다.
// 분할과정을 수행한 후, pivot 기준 왼쪽, 오른쪽 배열에 대하여 다시 quick sort 를 진행해 줍니다.
void quickSort(int arr[], int left, int right) {
    if ( left < right ) {
        int pivotIdx = partition(arr, left, right);
        quickSort(arr, left, pivotIdx - 1);
        quickSort(arr, pivotIdx + 1, right);
    } else {
        // Do nothing for left >= right case.
        return ;
    }
}  

int main() {
    int a[7] = {2, 5, 1, 4, 7, 3, 6};
    int arraySize = 7;
    quickSort(a, 0, arraySize-1);
    printArray(a, arraySize);
    return 0;
}