[c++][template] quick sort

반열림구간 [start, end)에서의 quick sort template

// reference를 불러와서 실제 배열에도 swap의 결과를 반영한다.
void swap(int& a, int& b){
  int tmp=a;
  a=b;
  b=tmp;
}

void qsort(vector<int>& arr, int start, int end){
  // 분할된 원소가 0개이거나 1개일때까지 함수 호출
  // start+1==end일 때, 원소의 개수는 1개
  if(start+1>=end) return;

  int pivot=start; 
  // 값 설정 기준 : 첫번째 원소

  int bigger=start+1; 
  // bigger : pivot보다 큰 원소를 찾는 index
  // 값 설정 기준 : pivot + 1

  int smaller=end-1; 
  // smaller : pivot보다 작은 원소를 찾는 index
  // 값 설정 기준 : 마지막원소

  // `bigger`와 `smaller`이 교차할때 까지 pivot보다 크거나 작은 원소들을 서로 교환한다.
  while(bigger<=smaller){
    // end는 아무 원소도 가리키지 않으므로 end보다 작아야한다.
    // bigger이 가리키는 원소가 pivot이 가리키는 원소보다 작으면 계속 bigger을 키운다.
    while(bigger<end && arr[bigger]<=arr[pivot]) ++bigger;

    // smaller은 나중에 pivot과 swap해야하기 때문에 pivot의 index인 start와 같으면 안된다.
    // 역시, smaller이 가리키는 원소가 pivot이 가리키는 원소보다 크면 계속 smaller을 줄인다.
    while(start<smaller && arr[pivot]<=arr[smaller]) --smaller;

    // bigger과 smaller이 교차하면 종료한다.
    if(bigger>=smaller) break;

    // 교차하지 않았다면 서로가 가리키는 원소를 swap하고 다시 반복한다.
    swap(arr[bigger], arr[smaller]);
  }
  // 교차했다면 pivot과 smaller가 가리키는 원소를 서로 교환한다.
  // 이렇게 하면 pivot 왼쪽에는 pivot보다 작은것, 오른쪽에는 pivot보다 큰것이 위치한다.
  swap(arr[smaller], arr[pivot]);

  // pivot을 기준으로 오른쪽과 왼쪽으로 나눠서 다시 정렬을 수행한다.
  qsort(arr, smaller+1, end);
  qsort(arr, start, smaller);
}