/ 알고리즘

Quick Sort

알고리즘 sort algorithm quick sort
https://4am.kr/quick-sort/
#include<iostream>
using namespace std;
#define MAX 10
#define SWAP(A, B) {int TT = A; A = B; B = TT;}
int datas[MAX + 1] = {3, 2, 6, 7, 30, 22, 66, 33, 99, 13};

void quick_sort(int left, int right)
{
  int i = left, j = right;
  int mid = (left + right) / 2;
  int pivot = datas[mid];

  //Partition
  while(i <= j)
  {
    while (datas[i] < pivot) i++;
    while (datas[j] > pivot) j--;
    if(i <= j)
    {
       SWAP(datas[i], datas[j])
       i++, j--;
    }
  }
  //Recursion
  if(left < j) quick_sort(left, j);
  if(i < right) quick_sort(i, right);
}

void print()
{
  for(int i = 0; i < MAX; i++)
    cout << datas[i] << " ";
  cout << endl;
}

int main()
{
    cout << "Unsorted Array" << endl;
    print();
    quick_sort(0, MAX - 1);
    cout << "Sorted Array" << endl;
    print();
    return 0;
}

/* result: tested by https://www.codechef.com/ide
Unsorted Array
3 2 6 7 30 22 66 33 99 13
Sorted Array
2 3 6 7 13 22 30 33 66 99
*/
/* reference
상상플러스 :: 퀵소트 알고리즘
http://comefeel.com/tt/comefeel/363
QUICKSORT (Java, C++) | Algorithms and Data Structures
http://www.algolist.net/Algorithms/Sorting/Quicksort
퀵 정렬 - 위키백과, 우리 모두의 백과사전
https://ko.wikipedia.org/wiki/퀵_정렬
*/