3-way QuickSort (3분할 퀵정렬)

https://sol248.tistory.com/51

QuickSort (퀵정렬)

퀵정렬은 중복된 값이 많을수록 느리다는 단점이 있기 때문에 

앞에서는 중복된 값이 없다는 가정을 하고 진행했습니다.

 

이것을 극복할 수 있는 방법이 3-way partitioning 입니다.

 

앞에서는 pivot 값보다 작은것과 큰 것 두 묶음으로 나누었지만,

 

여기서는

key 값보다 작은 값,

key 값과 같은 값,

key 값보다 큰 값

이렇게 3가지로 나눕니다.

 

구현 자체는 어렵지 않습니다.

 

코드)

 

void Quick3way(std::vector<int>& v, int low, int high) {
  if (low >= high) return;

  int lt = low;
  int i = low + 1;
  int gt = high;

  int k = v[low];
  std::cout << "Key = " << k << '\n';
  while (i <= gt) {
    if (v[i] < k) {
      std::swap(v[lt], v[i]);
      lt++;
      i++;
    } else if (v[i] > k) {
      std::swap(v[gt], v[i]);
      gt--;
    } else {
      i++;
    }
  }

  Print(v, low, high);
  Quick3way(v, low, lt - 1);
  Quick3way(v, gt + 1, high);
}

 

key 값을 설정해주고 배열을 하나씩 보며 큰지, 작은지, 같은지 비교하면 됩니다.