[C code] 퀵 정렬 (Quick Sort)

#include <stdio.h>
#include <stdlib.h>

void Swap(int * a, int * b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

int Partition(int arr[], int l, int r)
{
    int pivot = arr[r];
    int smll = l-1;     // pivot보다 작은 수 찾는 index

    // pivot보다 큰 값이 있으면, arr[smll]과 바꾸기
    for(int bg=l ; bg<r ; bg++) // pivot보다 큰 수 찾는 index (처음부터 pivot index 전까지 반복)
    {
        if(arr[bg] < pivot)
        {
            smll++;
            Swap(&arr[smll], &arr[bg]);
        }
    }

    Swap(&arr[smll+1], &arr[r]);    // arr[smll+1]과 pivot값 바꾸기
    return (smll+1);                // smll+1을 기준점으로, 양쪽의 배열 quick sort
}

// Function to sort an array using quick sort
void QuickSort(int arr[], int l, int r)
{
    // for left index == right index ( an array with one element )
    if(l < r)
    {
        int pivot_index = Partition(arr, l, r);

        // pivot 양쪽으로 Divide하여 재귀함수이용
        QuickSort(arr, l, pivot_index-1);
        QuickSort(arr, pivot_index+1, r);
    }
}

/* Function to print an array */
void PrintArray(int arr[], int size)
{
   printf("\n********************************\n");
   for(int i=0 ; i<size ; i++)
   {
       printf("%4d", arr[i]);
   }
}

// Driver program to test above functions
int main()
{
    int array[7];

    for(int i=0 ; i<7 ; i++)
    {
        printf("Put your %d integers : ", i);
        scanf("%d", array+i);
    }

    int n = sizeof(array)/sizeof(array[0]);
    PrintArray(array, n);
    QuickSort(array, 0, n-1);
    PrintArray(array, n);

    return 0;
}

합병 정렬(Merge Sort)처럼, 퀵 정렬(Quick Sort)은 분할 정복(Divide and Conquer) 알고리즘이다

배열의 한 요소를 피벗으로 정하여 정렬하는데, 피벗을 정하는 방법은 여러가지다 (위의 코드는 마지막 요소를 피벗으로 정하는 방법) - (계속적으로 많은 연구가 이어짐)

1. Always pick first element as pivot.

2. Always pick last element as pivot (implemented below)

3. Pick a random element as pivot.

4. Pick median as pivot.

...

Partition(arr, l, r)에서는, 마지막 요소인 arr[r]을 피벗으로 두고, 적절하게 위치시킨다

그리고 그 전에는 피벗보다 작은 값들로, 그 후에는 피벗보다 큰 값들로 두게 한다

이들은 선형시간을 따르게 된다

​

퀵 정렬은 평균, 최선으로 O(nlogn)을 따른다

(

최악의 경우에만 O(n^2)이고, 이는 모든 경우에서 피벗이 가장 왼쪽 혹은 오른쪽에 위치하는 경우를 뜻한다

T(n) = T(0) + T(n-1) + O(n)

T(n) = T(n-1) + O(n)

...

- 최악 O(n^2)​ / Stable버전, Unstable버전 둘 다 있음 

​

따라서 데이터가 균등하게 분할되어 있을 때 사용하는 것이 좋다

(잘 사용하지 않기를 권장하기도 함)

)

​

- GeeksforGeeks