ソートアルゴリズムの速度比較
ソートアルゴリズムについて
大小関係が定められたたくさんのデータを、小さい順（昇順）あるいは大きい順（降順）に並べ替える作業をソート（整列）と言い、それを行うアルゴリズムをソートアルゴリズムと言います。 この処理は、さまざまなプログラムの中で頻繁に使われ、それ故、古くからいろいろなアルゴリズムが考案されてきました。動機
ソートの勉強を調べていたらソートアルゴリズムがたくさんあることに少しだけ疑問があった。なぜなら数字などを順番に並び変えるのにソートアルゴリズムなんて一つで十分ではないのか？と思ったという素朴な疑問。
一つ一つ調べると、どのソートが効率が良く、どのソートが効率が悪いなど色々あることが分かったのですが、どれが良くてどれが悪いかを知るだけじゃいまいち物足りない気のするので実装してみようと思いつきました。
その中で代表的なものの中の5つのソートアルゴリズムの速度を比較したいと思います。(ちなみに昇順に並べるコード)
測定するアルゴリズム
- まず1つ目はソートと聞いて自分がパッと思いついた"バブルソート"です。これは比較的短いコードで書け、簡単なアルゴリズムですがソートアルゴリズムの中でもかなり効率の悪いアルゴリズムで、計算量はO(n^2)。
- 2つ目は先ほどのバブルソートの改良版の"シェーカーソート"というもので、計算量はO(n^2)。
- 3つ目はシェーカーソートよりは速いがクイックソートよりは遅い"挿入ソート"で、計算量はO(n^2)。
- 4つ目はソートの中でも高速とされる"クイックソート"で、計算量はO(nlogn)。
- 5つ目はC++のライブラリである"標準ソートです"。
測定コード
#include<iostream> #include<vector> #include<algorithm> #include<stdlib.h> #include<time.h> #include<iomanip> // バブルソート関数 void Buble_Sort(int x[], int n); // シェーカーソート関数 void Shaker_Sort(int x[], int n); // 挿入ソート関数 void Insertion_Sort(int [], int ); // クイックソート関数 void Quick_Sort(int list[], int left, int right); using namespace std; int main(void){ int i; // 異なる乱数の入った配列を保持する一時的に作った配列 int *Temporary_Array; // それぞれのソート用のポインタ配列 int *Buble_Array,*Shaker_Array,*Insertion_Array,*Quick_Array; int Array_Size; // 標準ソートで使う動的配列クラス vector<int> v; cout << "データサイズを入力してください : "; cin >> Array_Size; // それぞれの配列のメモリの動的確保 Temporary_Array = new int[Array_Size]; Buble_Array = new int[Array_Size]; Shaker_Array = new int[Array_Size]; Insertion_Array = new int[Array_Size]; Quick_Array = new int[Array_Size]; // 異なる乱数の生成 srand((unsigned)time(NULL)); for(i = 0;i < Array_Size;i++){ Temporary_Array[i] = rand(); v.push_back(rand()); } /* 異なる乱数の入った配列をバブルソートを行う配列に代入 */ for(i = 0;i < Array_Size;i++) Buble_Array[i] = Temporary_Array[i]; /* 異なる乱数の入った配列をシェーカーソートを行う配列に代入 */ for(i = 0;i < Array_Size;i++) Shaker_Array[i] = Temporary_Array[i]; /* 異なる乱数の入った配列を挿入ソートを行う配列に代入 */ for(i = 0;i < Array_Size;i++) Insertion_Array[i] = Temporary_Array[i]; /* 異なる乱数の入った配列をクイックソートを行う配列に代入 */ for(i = 0;i < Array_Size;i++) Quick_Array[i] = Temporary_Array[i]; // メモリを解放 delete[] Temporary_Array; /* バブルソート計測開始 */ clock_t Start_Buble_Sort = clock(); Buble_Sort(Buble_Array,Array_Size); /* バブルソート計測終了 */ clock_t End_Buble_Sort = clock(); delete[] Buble_Array; /* シェーカーソート計測開始 */ clock_t Start_Shaker_Sort = clock(); Shaker_Sort(Shaker_Array,Array_Size); /* シェーカーソート計測終了 */ clock_t End_Shaker_Sort = clock(); delete[] Shaker_Array; /* 挿入ソート計測開始 */ clock_t Start_Insertion_Sort = clock(); Insertion_Sort(Insertion_Array,Array_Size); /* 挿入ソート計測終了 */ clock_t End_Insertion_Sort = clock(); delete[] Insertion_Array; /* クイックソート計測開始 */ clock_t Start_Quick_Sort = clock(); Quick_Sort(Quick_Array, 0, Array_Size-1); /* クイックソート計測終了 */ clock_t End_Quick_Sort = clock(); delete[] Quick_Array; // 標準ソート計測開始 clock_t Standard_Start = clock(); sort(v.begin(),v.end()); // 標準ソート計測終了 clock_t Standard_End = clock(); cout << "・バブルソートによる実装時間は " << fixed << setprecision(7) << (double)(End_Buble_Sort - Start_Buble_Sort) / CLOCKS_PER_SEC << "秒" << endl; cout << "・シェーカーソートによる実装時間は " << fixed << setprecision(7) << (double)(End_Shaker_Sort - Start_Shaker_Sort) / CLOCKS_PER_SEC << "秒" << endl; cout << "・挿入ソートによる実装時間は " << fixed << setprecision(7) << (double)(End_Insertion_Sort - Start_Insertion_Sort) / CLOCKS_PER_SEC << "秒" << endl; cout << "・クイックソートによる実装時間は " << fixed << setprecision(7) << (double)(End_Quick_Sort - Start_Quick_Sort) / CLOCKS_PER_SEC << "秒" << endl; cout << "・標準ソートによる実装時間は " << fixed << setprecision(7) << (double)(Standard_End - Standard_Start) / CLOCKS_PER_SEC << "秒" << endl; return 0; } /* バブルソート */ void Buble_Sort(int x[], int n) { int i, j, tmp; for (i = 0; i < n - 1; i++) { for (j = n - 1; j > i; j--) { if (x[j - 1] > x[j]) { tmp = x[j]; x[j] = x[j - 1]; x[j - 1]= tmp; } } } } /* 挿入ソート */ void Insertion_Sort(int x[], int N){ int i,j,v; for(i = 1;i < N;i++){ v = x[i]; j = i - 1; while(j >= 0 && x[j] > v){ x[j + 1] = x[j]; j--; } x[j + 1] = v; } } /* シェーカーソート */ void Shaker_Sort(int x[], int N){ int right, left, work, shift; int i, j; right = N - 1; left = 0; while(right > left){ for(i = left; i < right; i++){ if(x[i] > x[i + 1]){ work = x[i]; x[i] = x[i + 1]; x[i + 1] = work; shift = i; } } right = shift; for(i = right; i > left; i--){ if(x[i] < x[i - 1] ){ work = x[i]; x[i] = x[i - 1]; x[i - 1] = work; shift = i; } } left = shift; } } /* クイックソート */ void Quick_Sort(int list[], int left, int right){ int i, last; int tmp; if (left >= right) return; last = left; for (i = left + 1; i <= right;i++){ if (list[i] < list[left]){ last++; tmp = list[last]; list[last] = list[i]; list[i] = tmp; } } tmp = list[left]; list[left] = list[last]; list[last] = tmp; Quick_Sort(list,left,last-1); Quick_Sort(list,last+1,right); }
ちょっと雑な感じになってしまいましたがとりあえずこんな感じに書きました。
言語は先ほどちらっと言った、標準ライブラリのvectorを使うためC++です。C++は去年の学校の授業で触って以来全くやっていなかったので書くのに多少苦労もあった。。
ちなみにソートアルゴリズムは主にこちらの本を参考にした。
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
- 作者: 渡部有隆
- 出版社/メーカー: マイナビ出版
- 発売日: 2015/01/30
- メディア: Kindle版
- この商品を含むブログを見る
実装
コンパイルを行いsortという実行ファイルを生成
./sortで実行するとデータ数を入力するよう促される。試しに12345といったデータサイズの値を入力。そうすると各ソートの実装時間が表示される。
データサイズを1から10億をそれぞれ10回測定しそれらの平均の時間を調べた。
結果
結果は以下の表にまとめた。
空白の箇所はあまりにも時間がかかるため断念したところです。
データサイズが少ないと一般的に速いとされているクイックソートや標準ライブラリによるソートが他のより若干遅いことがわかりました。
ただデータサイズが大きくなるにつれやはり高速と呼ばれるクイックソートと標準ソートは100万まではデータサイズが小さい時とあまり変わらない速度でソートしてます。
10億といった値だとなんと標準ソートの速度がクイックソートの半分といった結果でやはりライブラリは強い(確信)
要するに
まさしくこのbotの言う通りである()
んー、そこクイックソートにしてるけどデータサイズが小さいしバブルでも問題なさそう……ん、釈然としない表情をしているね？
— 情報系彼女bot (@jkgf_bot) 2017年6月2日
一般的に効率的な解法が全てのケースに対して効率良く働くとは限らないんだよ
あ、これ恋愛も同じだからね？
