Quick Sortのプログラムです。乱択クイックソート

quick.cpp

#include <iostream>
#include <random>
#include <vector>
#include <algorithm>

template<typename T>
long choosePivot (const std::vector<T>& ary, long head, long tail) {
  std::random_device rd;
  std::mt19937 mt(rd());
  std::uniform_int_distribution<long> dist(head, tail);
  return ary.at(dist(mt));
}

template<typename T>
void quick_sort (std::vector<T>& ary, long head, long tail) {
  if (head >= tail) return;
  T pivot = choosePivot(ary, head, tail);
  std::vector<T> L, M, R;
  for (long i = head; i <= tail; i++) {
    if (ary[i] < pivot) { L.push_back(ary[i]); }
    else if(pivot < ary[i]) { R.push_back(ary[i]); }
    else { M.push_back(ary[i]); }
  }
  long idx = head;
  for (auto el : L) ary[idx++] = el;
  for (auto el : M) ary[idx++] = el;
  for (auto el : R) ary[idx++] = el;
  long N_L = L.size(),
       N_R = R.size();
  if (N_L > 1) quick_sort<T>(ary, head, head+N_L-1);
  if (N_R > 1) quick_sort<T>(ary, tail-N_R+1, tail);
}
template<typename T>
void quick_sort2 (std::vector<T>& ary, long head, long tail) {
  if (head >= tail) return;
  long leftIdx = head,
       rightIdx = tail;
  T pivot = choosePivot(ary, head, tail);
  long countPivot = 0;
  while (true) {
    while(ary[leftIdx] <= pivot && leftIdx <= tail) {
      if (ary[leftIdx] == pivot) ++countPivot;
      ++leftIdx;
    }
    while(pivot < ary[rightIdx] && head <= rightIdx) {
      --rightIdx;
    }
    if (rightIdx - leftIdx < countPivot) break;
    std::swap(ary[leftIdx], ary[rightIdx]);
  }
  if (leftIdx - head > 1) quick_sort<T>(ary, head, leftIdx);
  if (tail - rightIdx > 1) quick_sort<T>(ary, rightIdx, tail);
}

template <typename F>
long measure(F proc) {
  auto start   = std::chrono::high_resolution_clock::now();
  proc();
  auto end     = std::chrono::high_resolution_clock::now();
  auto elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count(); 
  return elapsed;
}

int main(int argc, char *argv[]) {
  const long N = 1e6;
  std::vector<int> ary(N),
                   ary2(N),
                   random_ary1(N),
                   random_ary2(N);
  std::random_device rd;
  std::mt19937 mt(rd());
  std::iota(begin(ary), end(ary), 1);
  std::shuffle(begin(ary), end(ary), mt);
  std::copy(begin(ary), end(ary), begin(ary2));

  // create random data
  std::uniform_int_distribution<long> dist(1, N);
  for (long i = 0; i < N; i++) {
    long r = dist(mt);
    random_ary1[i] = r;
    random_ary2[i] = r;
  }
  //[&](){for(auto el : ary) {std::cout<<el<<" ";}std::cout<<std::endl;}();
  std::cout<<"[QUICK SORT]"<<std::endl;
  std::cout<<measure([&](){quick_sort<int>(ary, 0, N-1);})<<"[ms]"<<std::endl;
  std::cout<<measure([&](){quick_sort2<int>(ary2, 0, N-1);})<<"[ms]"<<std::endl;
  std::cout<<measure([&](){quick_sort<int>(random_ary1, 0, N-1);})<<"[ms]"<<std::endl;
  std::cout<<measure([&](){quick_sort2<int>(random_ary2, 0, N-1);})<<"[ms]"<<std::endl;
  //[&](){for(auto el : ary) {std::cout<<el<<" ";}std::cout<<std::endl;}();
  return 0;
}