C++でクイックソートを２パターン実装してみた

# はじめに
以前ソートをいくつか作成したのだが、簡単なソートしか作成しなかった。
その続きとしてクイックソートをC++で実装してみた。

# インデックスによるクイックソート
こちらは比較的簡単に実装できた。とはいえ、クイックソートは以前実装したソートより複雑で、Wikipediaさんにお世話になってしまった。
また、クイックソートはソート対象を変更して再帰するのだが、`vector`配列とは別に要素番号が必要になってしまい、３引数という非常に不恰好な関数となってしまった。また、中央値算出も`if-else`ゴリ押ししたため、非常に汚いコードになってしまった。

```cpp:quickSortByIdx
template<typename T> void quickSort(std::vector<T>& v, const int left, const int right){
  if(right - left < 1) return ;
  auto central = v[(right-left)/2];
  auto pivot = central;
  if(v[left]<v[right]){
    if(v[left]<central){
      if(central<v[right]){
      }else{
        pivot = v[right];
      }
    }else{
      pivot = v[left];
    }
  }else{
    if(central<v[right]){
      pivot = v[right];
    }else{
      if(v[left]<central){
        pivot = v[left];
      }else{
      }
    }
  }
  int i = left, j = right;
  while(1){
    while(v[i]<pivot) i++;
    while(pivot<v[j]) j--;
    if(i >= j) break;
    swap(v[i],v[j]);
    i++;
    j--;
  }
  if(right - left < 2) return ;
  quickSort(v, left, i-1);
  quickSort(v, j+1, right);
}
```

# イテレータによるクイックソート
上述の関数をイテレータで実装した。イテレータ自体触れるのが初めてだったので、こちらは苦労した。

```cpp:quickSortByItr
template<class Iterator> void quickSort(const Iterator& begin, const Iterator& end){
  if(end - begin < 2 ) return;
  auto left = begin;
  auto right = end-1;
  auto central = left + distance(left, right)/2;
  auto pivot = *central;
  if(*left<*right){
    if(*left<*central){
      if(*central>*right){
        pivot = *right;
      }
    }else{
      pivot = *left;
    }
  }else{
    if(*central<*right){
      pivot = *right;
    }else{
      if(*left<*central){
        pivot = *left;
      }else{
      }
    }
  }
  auto i = left;
  auto j = right;
  while(1){
    while(*i<pivot) i++;
    while(pivot<*j) j--;
    if(i >= j) break;
    iter_swap(i,j);
    i++;
    j--;
  }
  if(end - begin <= 2) return ;
  if(i-begin>1)quickSort(begin, i);
  if(end-j>1)quickSort(j+1, end);
}
```

# 実行プログラム全体
今回は、ランダムに`vector<int>`を生成して、それに対してインデックスによるクイックソートとイテレータによるクイックソートを試した。

```cpp:main.cpp
#include <iostream>
#include <vector>
#include <random>
using namespace std;

#define debug(var)  do{std::cout << #var << " : "; view(var);}while(0)

template<typename T> using V = std::vector<T>;
template<typename T> using VV = std::vector<std::vector<T>>;
template<typename T> using VVV = std::vector<std::vector<std::vector<T>>>;
template<typename T> void view(const std::vector<T>& v){ for(const auto& e : v) std::cout << e << " "; std::cout << std::endl; }

constexpr size_t arSize = 50;
//constexpr size_t arSize = 100;
//constexpr size_t arSize = 1000;
constexpr int rndMax = 100;

std::vector<int> genVectorByRandom(size_t size, int rndMax){
  std::mt19937 mt{ std::random_device{}() };
  std::uniform_int_distribution<int> rnd(0, rndMax);
  std::vector<int> v(size);
  for(size_t i=0; i<size; ++i){
    v[i] = rnd(mt);
  }
  return v;
}


template<typename T> void quickSort(std::vector<T>& v, const int left, const int right){
  if(right - left < 1) return ;
  auto central = v[(right-left)/2];
  auto pivot = central;
  if(v[left]<v[right]){
    if(v[left]<central){
      if(central<v[right]){
      }else{
        pivot = v[right];
      }
    }else{
      pivot = v[left];
    }
  }else{
    if(central<v[right]){
      pivot = v[right];
    }else{
      if(v[left]<central){
        pivot = v[left];
      }else{
      }
    }
  }
  int i = left, j = right;
  while(1){
    while(v[i]<pivot) i++;
    while(pivot<v[j]) j--;
    if(i >= j) break;
    swap(v[i],v[j]);
    i++;
    j--;
  }
  if(right - left < 2) return ;
  quickSort(v, left, i-1);
  quickSort(v, j+1, right);
}

template<class Iterator> void quickSort(const Iterator& begin, const Iterator& end){
  if(end - begin < 2 ) return;
  auto left = begin;
  auto right = end-1;
  auto central = left + distance(left, right)/2;
  auto pivot = *central;
  if(*left<*right){
    if(*left<*central){
      if(*central>*right){
        pivot = *right;
      }
    }else{
      pivot = *left;
    }
  }else{
    if(*central<*right){
      pivot = *right;
    }else{
      if(*left<*central){
        pivot = *left;
      }else{
      }
    }
  }
  auto i = left;
  auto j = right;
  while(1){
    while(*i<pivot) i++;
    while(pivot<*j) j--;
    if(i >= j) break;
    iter_swap(i,j);
    i++;
    j--;
  }
  if(end - begin <= 2) return ;
  if(i-begin>1)quickSort(begin, i);
  if(end-j>1)quickSort(j+1, end);
}

template<typename T> bool alignmentCheck(vector<T>& v){
  bool alignment = true;
  for(size_t i=1; i<v.size(); ++i){
    if(v[i-1]>v[i]) alignment = false;
  }
  return alignment;
}

int main(int argc, char **argv) {
  vector<string> args(argv, argv+argc);
  auto v = genVectorByRandom(arSize, rndMax);
  debug(v);
  cout << (alignmentCheck(v)? "OK" : "NG" ) << endl;
  auto vTemp = v;
  quickSort(vTemp, 0, vTemp.size()-1);
  debug(vTemp);
  cout << (alignmentCheck(vTemp)? "OK" : "NG" ) << endl;
  vTemp = v;
  quickSort(vTemp.begin(), vTemp.end());
  debug(vTemp);
  cout << (alignmentCheck(vTemp)? "OK" : "NG" ) << endl;

  return 0;
}
```

# 実行結果
無事ソートできたようである。

```sh:output
v : 49 68 16 8 100 59 74 17 83 19 87 100 22 51 50 31 45 26 39 69 23 13 71 74 97 86 39 75 31 8 79 76 59 15 59 49 84 11 97 34 57 74 34 74 72 61 22 53 21 52 
NG
vTemp : 8 8 11 13 15 16 17 19 21 22 22 23 26 31 31 34 34 39 39 45 49 49 50 51 52 53 57 59 59 59 61 68 69 71 72 74 74 74 74 75 76 79 83 84 86 87 97 97 100 100 
OK
vTemp : 8 8 11 13 15 16 17 19 21 22 22 23 26 31 31 34 34 39 39 45 49 49 50 51 52 53 57 59 59 59 61 68 69 71 72 74 74 74 74 75 76 79 83 84 86 87 97 97 100 100 
OK
```

# 速度について
前回同様、速度も測ってみた。ここでは、インデックスベースとイテレータベースだけでなく`std::sort()`も比較してみた。

![quickSorts.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/282145/d9d57c25-1821-6027-9f90-e1c30da1f4bc.png)

# おわりに
`std::sort()`速すぎぃぃぃ！
自分のプログラムを見直さなければいけない・・・