정렬 (sort) : 퀵 정렬 (quick sort)

원리

---

퀵 정렬 (quick sort)은 병합 정렬(merge sort)처럼 분할 정복 (divide and conquer) 알고리즘을 사용합니다. 단, 병합 정렬(merge sort)과 달리 별도의 메모리가 필요하지 않다는 장점이 있습니다.
퀵 정렬(quick sort)에서 가장 중요한 점은 pivot이라는 기준점을 세운다는 점입니다. 또한, pivot을 어디다 두는지에 따라 성능이 달라집니다. 아래 소스 코드는 Median of three를 이용하여 구현한 개선된 퀵정렬입니다.

• while문 분석
  

  

• 재귀함수 분석
  

  

소스 코드 (구현)

---

#include <iostream>
#include <algorithm>
#include <functional>

using namespace std;

template <typename T>
void qsort(T *start, T *end, function<bool(const T data1, const T data2)> cmp = [](const T data1, const T data2) { return data1 < data2; })
{
    if (start >= end)
        return;
    T *pivot = (end - start) / 2 + start;
    T *left = start;
    T *right = end;

    while (left <= right)
    {
        while (cmp(*left, *pivot))
            left++;
        while (cmp(*pivot, *right))
            right--;

        if (left <= right)
        {
            swap(*left, *right);
            left++;
            right--;
        }
    }

    qsort(start, right, cmp);
    qsort(left, end, cmp);
}

int main()
{
    int arr[5] = {13, 11, 51, 2, 7};

    qsort(arr, arr + 4);

    for (const auto r : arr)
    {
        cout << r << ' ';
    }

    return 0;
}

성능

---

퀵 정렬	Big O (정렬된 상태)
일반적인 퀵정렬	\(O(n^2)\)
Three of median - 개선된 퀵정렬	\(O(log_2n)\)

• unstable sort입니다.