퀵 정렬(Quick Sort)

실제로 퀵 정렬은 nlong(2)n의 복잡도를 갖는 다른 정렬 알고리즘과 비교했을 때에도 평균적으로 제일 빠른 것으로 알려져 있습니다. 그 이유는 퀵 정렬의 데이터 이동횟수가 상대적으로 적고, 병합 정렬과 같이 메모리 공간을 요구하지 않는다는 사실에 있습니다. 결론은 퀵 정렬의 시간 복잡도는 nlong(2)n 입니다.

#include <stdio.h>
 
void Swap(int arr[], int idx1, int idx2) {
    int temp = arr[idx1];
    arr[idx1] = arr[idx2];
    arr[idx2] = temp;
}
 
int Partition(int arr[], int left, int right) {
    int pivot = arr[left];
    int low = left + 1;
    int high = right;
 
    while (low <= high) {
 
        while (pivot >= arr[low] && low <= right)
            low++;
        while (pivot <= arr[high] && high >= (left + 1))
            high--;
 
        if (low <= high)
            Swap(arr, low, high);
    }
 
    Swap(arr, left, high);
    return high;
}
 
void QuickSort(int arr[], int left, int right) {
    if (left <= right) {
        int pivot = Partition(arr, left, right);
        QuickSort(arr, left, pivot - 1);
        QuickSort(arr, pivot + 1, right);
    }
}
 
int main(void) {
    int arr[] = { 3,2,4,1,7,6,5 };
    int len = sizeof(arr) / sizeof(int);
    int i;
 
    QuickSort(arr, 0, sizeof(arr) / sizeof(int) - 1);
    for (i = 0; i < len; i++)
        printf("%d ", arr[i]);
 
    printf("\n");
    return 0;
}