ソート 速度比較

C++のソートの速度比較をしました。
条件は、長さが$10^5,10^6,10^7$ のvectorまたは配列です。本文で書いてあるのは$10^6$のみで、$10^5$や$10^7$についてもまとめたものは一番下のまとめに書きます。
vector、配列はランダムに生成します。
10回ずつ計測します。

# 計測

## STLのソート

### vector

<details><summary>コード</summary>

``` STL_sort_vector.cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>
#include <random>
using namespace std;
using namespace chrono;

const int N = 1000000;

int main() {
  random_device rd;
  mt19937 mt(rd());
  vector<int> a(N);
  for (int i = 0; i < N; i++)
    a[i] = mt();
  system_clock::time_point start = system_clock::now();
  sort(a.begin(), a.end());
  system_clock::time_point end = system_clock::now();
  cout << duration_cast<milliseconds>(end - start).count() << " msec\n";
}
```
</details>

|回|ms|
|-|-|
|1|341|
|2|347|
|3|347|
|4|354|
|5|347|
|6|347|
|7|347|
|8|347|
|9|346|
|10|347|

平均は347.0msでした。

### 配列

<details><summary>コード</summary>

``` STL_sort.cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>
#include <random>
using namespace std;
using namespace chrono;

const int N = 1000000;

int main() {
  random_device rd;
  mt19937 mt(rd());
  int a[N];
  for (int i = 0; i < N; i++)
    a[i] = mt();
  system_clock::time_point start = system_clock::now();
  sort(a, a + N);
  system_clock::time_point end = system_clock::now();
  cout << duration_cast<milliseconds>(end - start).count() << " msec\n";
}
```
</details>

|回|ms|
|-|-|
|1|187|
|2|195|
|3|194|
|4|195|
|5|196|
|6|195|
|7|194|
|8|195|
|9|205|
|10|196|

平均は195.2msでした。

## シェルソート

間隔については、[こちらの記事](https://web.archive.org/web/20170212072405/http://www.programming-magic.com/20100507074241/)で最速だったものを採用しました。

### vector

<details><summary>コード</summary>

``` shellsort_vector.cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>
#include <random>
using namespace std;
using namespace chrono;

const int N = 1000000;

int main() {
  random_device rd;
  mt19937 mt(rd());
  vector<int> a(N);
  for (int i = 0; i < N; i++)
    a[i] = mt();
  system_clock::time_point start = system_clock::now();
  // 間隔
  const vector<int> h = {262913, 65921, 16577, 4193, 1073, 281, 77, 23, 8, 1};
  for (int i: h) {
    for (int j = 0; j < N; j++) {
      int k = j;
      int tmp = a[j];
      while (k >= i && a[k - i] > tmp) {
        a[k] = a[k - i];
        k -= i;
      }
      a[k] = tmp;
    }
  }
  system_clock::time_point end = system_clock::now();
  cout << duration_cast<milliseconds>(end - start).count() << " msec\n";
}
```
</details>

|回|ms|
|-|-|
|1|347|
|2|354|
|3|354|
|4|354|
|5|352|
|6|354|
|7|353|
|8|356|
|9|354|
|10|355|

平均は353.3秒でした。


### 配列

<details><summary>コード</summary>

``` shellsort.cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>
#include <random>
using namespace std;
using namespace chrono;

const int N = 1000000;

int main() {
  random_device rd;
  mt19937 mt(rd());
  int a[N];
  for (int i = 0; i < N; i++)
    a[i] = mt();
  system_clock::time_point start = system_clock::now();
  // 間隔
  const int h[] = {262913, 65921, 16577, 4193, 1073, 281, 77, 23, 8, 1};
  for (int i: h) {
    for (int j = 0; j < N; j++) {
      int k = j;
      int tmp = a[j];
      while (k >= i && a[k - i] > tmp) {
        a[k] = a[k - i];
        k -= i;
      }
      a[k] = tmp;
    }
  }
  system_clock::time_point end = system_clock::now();
  cout << duration_cast<milliseconds>(end - start).count() << " msec\n";
}
```
</details>

|回|ms|
|-|-|
|1|148|
|2|156|
|3|155|
|4|155|
|5|156|
|6|156|
|7|156|
|8|155|
|9|156|
|10|156|

平均は154.9msとなりました。

## マージソート

### vector

<details><summary>コード</summary>

``` mergesort_vector.cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>
#include <random>
using namespace std;
using namespace chrono;

const int N = 1000000;
const int inf = numeric_limits<int>::max();

void mergesort(vector<int> &a, int l, int r) {
  if (l + 1 < r) {
    int m = (l + r) / 2;
    mergesort(a, l, m);
    mergesort(a, m, r);
    int n1 = m - l, n2 = r - m;
    vector<int> L(n1 + 1), R(n2 + 1);
    for (int i = 0; i < n1; i++) L[i] = a[l + i];
    for (int i = 0; i < n2; i++) R[i] = a[m + i];
    L[n1] = inf;
    R[n2] = inf;
    int j = 0, k = 0;
    for (int i = l; i < r; i++) {
      if (L[j] <= R[k]) {
        a[i] = L[j];
        j++;
      } else {
        a[i] = R[k];
        k++;
      }
    }
  }
}

int main() {
  random_device rd;
  mt19937 mt(rd());
  vector<int> a(N);
  for (int i = 0; i < N; i++)
    a[i] = mt();
  system_clock::time_point start = system_clock::now();
  mergesort(a, 0, N);
  system_clock::time_point end = system_clock::now();
  cout << duration_cast<milliseconds>(end - start).count() << " msec\n";
}
```
</details>

|回|ms|
|-|-|
|1|778|
|2|782|
|3|786|
|4|793|
|5|786|
|6|785|
|7|788|
|8|783|
|9|778|
|10|800|

平均は785.9msとなりました。

### 配列

<details><summary>コード</summary>

配列の参照がよくわからなかったので以下のようにグローバルに置いてます。

``` mergesort.cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>
#include <random>
using namespace std;
using namespace chrono;

const int N = 1000000;
const int inf = numeric_limits<int>::max();

int a[N];

void mergesort(int l, int r) {
  if (l + 1 < r) {
    int m = (l + r) / 2;
    mergesort(l, m);
    mergesort(m, r);
    int n1 = m - l, n2 = r - m;
    int L[n1 + 1], R[n2 + 1];
    for (int i = 0; i < n1; i++) L[i] = a[l + i];
    for (int i = 0; i < n2; i++) R[i] = a[m + i];
    L[n1] = inf;
    R[n2] = inf;
    int j = 0, k = 0;
    for (int i = l; i < r; i++) {
      if (L[j] <= R[k]) {
        a[i] = L[j];
        j++;
      } else {
        a[i] = R[k];
        k++;
      }
    }
  }
}

int main() {
  random_device rd;
  mt19937 mt(rd());
  for (int i = 0; i < N; i++)
    a[i] = mt();
  system_clock::time_point start = system_clock::now();
  mergesort(0, N);
  system_clock::time_point end = system_clock::now();
  cout << duration_cast<milliseconds>(end - start).count() << " msec\n";
}
```
</details>

|回|ms|
|-|-|
|1|137|
|2|143|
|3|143|
|4|143|
|5|143|
|6|143|
|7|143|
|8|144|
|9|143|
|10|142|

平均は142.4msでした。

## ヒープソート

### vector

<details><summary>コード</summary>


``` heapsort_vector.cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>
#include <random>
using namespace std;
using namespace chrono;

const int N = 1000000;

void heapify(vector<int> &a, int l, int r) {
  int tmp = a[l], c, p;
  for (p = l; p < (r + 1) / 2; p = c) {
    int cl = p * 2 + 1, cr = cl + 1;
    c = ((cr <= r && a[cr] > a[cl]) ? cr : cl);
    if (tmp >= a[c])
      break;
    a[p] = a[c];
  }
  a[p] = tmp;
}

void heapsort(vector<int> &a) {
  for (int i = (N - 1) / 2; i >= 0; i--)
    heapify(a, i, N - 1);
  for (int i = N - 1; i > 0; i--) {
    swap(a[0], a[i]);
    heapify(a, 0, i - 1);
  }
}

int main() {
  random_device rd;
  mt19937 mt(rd());
  vector<int> a(N);
  for (int i = 0; i < N; i++)
    a[i] = mt();
  system_clock::time_point start = system_clock::now();
  heapsort(a);
  system_clock::time_point end = system_clock::now();
  cout << duration_cast<milliseconds>(end - start).count() << " msec\n";
}
```
</details>

|回|ms|
|-|-|
|1|366|
|2|343|
|3|342|
|4|344|
|5|343|
|6|343|
|7|341|
|8|344|
|9|343|
|10|334|

平均は344.3msでした。

### 配列

<details><summary>コード</summary>


``` heapsort.cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>
#include <random>
using namespace std;
using namespace chrono;

const int N = 1000000;
int a[N];

void heapify(int l, int r) {
  int tmp = a[l], c, p;
  for (p = l; p < (r + 1) / 2; p = c) {
    int cl = p * 2 + 1, cr = cl + 1;
    c = ((cr <= r && a[cr] > a[cl]) ? cr : cl);
    if (tmp >= a[c])
      break;
    a[p] = a[c];
  }
  a[p] = tmp;
}

void heapsort() {
  for (int i = (N - 1) / 2; i >= 0; i--)
    heapify(i, N - 1);
  for (int i = N - 1; i > 0; i--) {
    swap(a[0], a[i]);
    heapify(0, i - 1);
  }
}

int main() {
  random_device rd;
  mt19937 mt(rd());
  for (int i = 0; i < N; i++)
    a[i] = mt();
  system_clock::time_point start = system_clock::now();
  heapsort();
  system_clock::time_point end = system_clock::now();
  cout << duration_cast<milliseconds>(end - start).count() << " msec\n";
}
```
</details>

|回|ms|
|-|-|
|1|155|
|2|161|
|3|161|
|4|160|
|5|161|
|6|157|
|7|156|
|8|161|
|9|153|
|10|160|

平均は158.5msでした。

# まとめ

|ソートの種類|$N=10^5$|$N=10^6$|$N=10^7$|
|-|-|-|-|
|STLvector|42.6ms|347.0ms|3935.2ms|
|STL配列|26.4ms|195.2ms|2150.8ms|
|シェルソートvector|42.0ms|353.3ms|4619.3ms|
|シェルソート配列|20.2ms|154.9ms|1878.5ms|
|マージソートvector|88.8ms|785.9ms|8410.9ms|
|マージソート配列|19.6ms|142.4ms|2929.4ms|
|ヒープソートvector|39.2ms|344.3ms|4545.6ms|
|ヒープソート配列|20.4ms|158.5ms|2244.3ms

~~配列はヒープソート以外では$N=10^7$でsegmentation faultになりましたがヒープソートのコードに問題があるのでしょうか。~~
8/22追記:newを使うことで解消しました。
newを使った範囲はSTL配列、シェルソート配列、マージソート配列の3箇所です。
追記終わり

# 感想

ヒープソートやマージソートが思ったより速くて驚きました。シェルソートが謎に速すぎますね。(STLに全て勝っています)配列ではすべてのソートアルゴリズムでSTLより速かったです。

[Xアカ](https://twitter.com/hiro_1729)ぜひフォローお願いします。