[자료구조] Quick sort(퀵 정렬) 구현 c++ [컴공과고씨]

Quick Sort는 배열을 더 작은 하위 배열로 분할하고 해당 하위 배열을 재귀적으로 정렬합니다.

즉, 분할 정복 알고리즘(divide-and-conquer)를 이용한 정렬이라고 볼 수 있습니다.

평균 및 최선의 시간 복잡도는 O(n log n)이고 최악의 시간 복잡도는 O(n^2)입니다. 효율적인 분할 및 무작위화 기술로 인해 버블 정렬 및 삽입 정렬과 같은 다른 정렬 알고리즘보다 빠른 경우가 많습니다. 또한 내부 알고리즘이므로 배열을 정렬하는 데 추가 메모리가 필요하지 않습니다.

 

Quick sort 구현

1. 배열에서 "pivot" 요소를 선택합니다. 이 요소는 배열을 두 개의 하위 배열로 분할하는 데 사용됩니다. 하나는 피벗보다 작은 요소를 포함하고 다른 하나는 피벗보다 큰 요소를 포함합니다.

 

ex) 6,9,7,3,5,2,4,1,8 라는 배열이 있다고 할 때 이 중 pivot 을 하나 선택해줍니다. 

이 코드에서는 맨 앞쪽 원소를 pivot으로 잡고 있습니다. 그럼 6이 pivot이 되는 겁니다.

 

2. 배열을 반복하고 피벗보다 작은 모든 요소를 ​​왼쪽으로 이동하고 피벗보다 큰 모든 요소를 ​​오른쪽으로 이동하여 배열을 분할합니다. 

ex) 6,9,7,3,5,2,4,1,8 여기서 왼쪽부터 오른쪽으로 가는 변수, 오른쪽 부터 왼쪽으로 가는 변수를 선언해줍니다. 그러면

9부터 확인하면서 9는 6보다 큰 값인데 왼쪽에 있으므로 오른쪽으로 몰아줘야합니다.

그래서 이동하는 것을 멈춰주고 오른쪽에서 확인하면서 8은 6보다 큰 값이고 오른쪽에 이미 있기 때문에 패스 다음은 1 인데 1은 6보다 작음에도 불구하고 오른쪽에 있기 때문에 아까 확인했던 9와 값을 바꾸어 줍니다.

6,1,7,3,5,2,4,9,8 이 되겠네요. 이것을 왼쪽 변수가 오른쪽 변수를 넘어 갈때 까지 반복해 줍니다.

6,1,4,3,5,2,7,9,8 이런식으로 될겁니다.

 

3. 2번 과정 후 오른쪽 변수는 2가 6보다 작은 수였기 때문에 멈췄을 것입니다.

마지막으로 pivot과 2를 바꾸어주면 2,1,4,3,5,6,7,8,9 이런식으로 만들어져 6기준으로 작은 수와 큰 수를 나눌 수 있는 것이죠. 자 그렇다면 이제는 재귀를 이용하여 6을 기준으로 2부터 5까지 다시 pivot을 정해서 정렬하고 7부터 9까지 다시 pivot을 정해서 정렬해주는 식으로 반복해주면 정렬이 되어지게됩니다.

 

전체코드

#include <iostream>
using namespace std;
typedef int ItemType;
void Swap(int& a, int& b) {
    int temp = a;
    a = b;
    b = temp;
}
void Split(ItemType values[], int first, int last, int& splitPoint)
{
  ItemType splitVal = values[first]; // pivot point
  int saveFirst = first;
  bool onCorrectSide;
 
  first++;
  do
  {
    onCorrectSide = true;
    while (onCorrectSide)         // Move first toward last.
      if (values[first] > splitVal)
        onCorrectSide = false;
      else
      {  
        first++;
        onCorrectSide = (first <= last);
      }
 
    onCorrectSide = (first <= last);
    while (onCorrectSide)             // Move last toward first.
      if (values[last] <= splitVal)
        onCorrectSide = false;
      else
      {
        last--;
        onCorrectSide = (first <= last);
      }
   
    if (first < last)
    {
      Swap(values[first], values[last]);
      first++;
      last--;
    }
  } while (first <= last);
 
  splitPoint = last;
  Swap(values[saveFirst], values[splitPoint]);
}
 
 
template<class ItemType>
void QuickSort(ItemType values[], int first, int last)
{
  if (first < last)
  {
    int splitPoint;
 
    Split(values, first, last, splitPoint);
    // values[first]..values[splitPoint-1] <= splitVal
    // values[splitPoint] = splitVal
    // values[splitPoint+1]..values[last] > splitVal
 
    QuickSort(values, first, splitPoint-1);
    QuickSort(values, splitPoint+1, last);
  }
}
int main() {
    int arr[9] = { 1,4,6,3,2,9,8,7,5 };
    QuickSort(arr, 0, 8);
    for (int i = 0; i < 9; i++) {
        cout << arr[i] << " ";
    }
    cout << '\n';
    return 0;
}
 

* 참고서적 c++ plus data structures

* 다른 자료구조에 대한 코드는 https://github.com/goragoraki/Data-Structure 에서 볼 수 있습니다.