LoginSignup
1
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

@hiroyuk1

ソート 速度比較

Last updated at Posted at 2023-08-22

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

計測

STLのソート

vector

コード
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";
}
回 ms
1 341
2 347
3 347
4 354
5 347
6 347
7 347
8 347
9 346
10 347

平均は347.0msでした。

配列

コード
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";
}
回 ms
1 187
2 195
3 194
4 195
5 196
6 195
7 194
8 195
9 205
10 196

平均は195.2msでした。

シェルソート

間隔については、こちらの記事で最速だったものを採用しました。

vector

コード
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";
}
回 ms
1 347
2 354
3 354
4 354
5 352
6 354
7 353
8 356
9 354
10 355

平均は353.3秒でした。

配列

コード
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";
}
回 ms
1 148
2 156
3 155
4 155
5 156
6 156
7 156
8 155
9 156
10 156

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

マージソート

vector

コード
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";
}
回 ms
1 778
2 782
3 786
4 793
5 786
6 785
7 788
8 783
9 778
10 800

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

配列

コード

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

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";
}
回 ms
1 137
2 143
3 143
4 143
5 143
6 143
7 143
8 144
9 143
10 142

平均は142.4msでした。

ヒープソート

vector

コード
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";
}
回 ms
1 366
2 343
3 342
4 344
5 343
6 343
7 341
8 344
9 343
10 334

平均は344.3msでした。

配列

コード
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";
}
回 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アカぜひフォローお願いします。

1
2
1

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?