6. Quick Sort

오늘은 Quick Sort를 구현해보았다.

Quick Sort 알고리즘을 대충 설명한다.

1,4,2,5,7,3,6,8을 가지는 배열 arr가 있다고 가정하자.

여기서 가운데 값인 5를 기준을 잡는다.

이 때, 이 기준인 5를 pivot이라고 부른다.

그리고 왼쪽부터 pivot까지를 탐색하여

pivot보다 값이 큰가? 하고 물어본다.

1 < 5 는 pivot보다 값이 작기 때문에 내려놓는다.

4와 2 또한 마찬가지다.

그렇다면, 오른쪽으로 가서 하나씩 물어본다.

8은 pivot보다 큰가? 참이다.

이런식으로 하다가 3에서 걸리게된다.

3은 pivot보다 큰가? 에서 거짓이 나오게되고.

3과 pivot의 위치를 바꾸게 된다.

루프를 한번 돌게되면

1 4 2 3 7 5 6 8이 된다.

이걸 Recursion을 이용해 다 돌리게 되면 O(n * log n)의 처리 속도의 Quick Sort를 완성하게된다.

(최악의 경우 O(n^2)가 소모되긴 하지만).

#include <iostream>
 
using namespace std;
 
void Q_Sort(int arr[], int left, int right) {
  int b_left = left;
  int b_right = right;
  int pivot = arr[(left+right)/2];
  
  while(left <= right) {
    while(*(arr+left) < pivot) left++;
    while(*(arr+right) > pivot) right--;
    
    if(left <= right) {
      int temp = *(arr+left);
      *(arr+left) = *(arr+right);
      *(arr+right) = temp;
      left++;
      right--;
    }
  }
  if(b_left < right) Q_Sort(arr, b_left, right);
  if(left < b_right) Q_Sort(arr, left, b_right);
}
int main(int argc, char* argv[]) {
  int arr[] = {1,4,2,5,7,3,6,8};
  int __size__ = 8 - 1;
  int index = 0;
  // default array value;
  for(int i = 0; i < 8; ++i) cout << *(arr+i) << " ";
  cout << endl;
  Q_Sort(arr, index, __size__);
  for(int i = 0; i < 8; ++i) cout << *(arr+i) << " ";
  return 0;
}