（蛇足編、その２）C言語教室 第26回 - いろいろなソート - バブルソート、選択ソート、シェルソート、マージソート、クイックソート

調べ出したらキリがない。
Webサイトで入手したアルゴリズムを元に、同じランダム配列をソートして違いを比較します。

ソースコード

lesson26.r2.2.3.c

6.36 KB

ファイルダウンロードについて

ダウンロード

実行結果例

サンプル数= 10,000

jm3nrhMac-mini-:c akio$ ./a.out 10000
Sample size = 10,000
  bubble sort ---- # swapped = 25,053,995 (elapsed second = 0)
  selection sort - # swapped = 18,512,723 (elapsed second = 0)
  shell sort ----- # swapped = 163,982 (elapsed second = 0)
  merge sort ----- # swapped = 73,413 (elapsed second = 0)
  quick sort ----- # swapped = 32,055 (elapsed second = 0)
each sorted results are same.

サンプル数＝100,000

jm3nrhMac-mini-:c akio$ ./a.out 100000
Sample size = 100,000
  bubble sort ---- # swapped = 2,493,637,712 (elapsed second = 23)
  selection sort - # swapped = 1,836,886,664 (elapsed second = 24)
  shell sort ----- # swapped = 2,899,629 (elapsed second = 0)
  merge sort ----- # swapped = 898,429 (elapsed second = 0)
  quick sort ----- # swapped = 397,725 (elapsed second = 0)
each sorted results are same.

サンプル数＝100,000で、10回実施した平均を取ってみます。

、、、同じソート結果を得るのに、バブルソートはのクイックソート6,281倍も値の交換処理が発生しています。

サンプルの値の重複を極力排除した場合

上記のサンプルデータは、rand() % sizeで算出して適度に同じ値が出現するようにしていましたが、rand()だけで算出してみた結果が以下の値です。

Sample size = 100,000
bubble sort ---- # swapped = 2,505,773,583 (elapsed second = 23)
selection sort - # swapped = 2,505,773,583 (elapsed second = 23)
shell sort ----- # swapped = 3,047,845 (elapsed second = 0)
merge sort ----- # swapped = 898,635 (elapsed second = 0)
quick sort ----- # swapped = 387,493 (elapsed second = 0)
each sorted results are same.

バブルソートと選択ソートの値の交換回数は一致しており、選択ソートの効率が下がっています。しかし他のソートアルゴリズムではそれほど影響がないようです。

サンプルの値の種類を100に限定した場合

Sample size = 100,000
  bubble sort ---- # swapped = 2,480,654,837 (elapsed second = 23)
  selection sort - # swapped = 4,942,868 (elapsed second = 6)
  shell sort ----- # swapped = 1,308,895 (elapsed second = 0)
  merge sort ----- # swapped = 904,466 (elapsed second = 0)
  quick sort ----- # swapped = 595,245 (elapsed second = 0)
each sorted results are same.

これは面白い結果ですね。
選択ソートの効率が劇的に改善しています。
シェルソートも２倍以上改善していますね。
一方、クイックソートは効率が落ちています。

更に、サンプルの値の種類を10に限定した場合

Sample size = 100,000
  bubble sort ---- # swapped = 2,257,637,342 (elapsed second = 22)
  selection sort - # swapped = 448,986 (elapsed second = 7)
  shell sort ----- # swapped = 382,164 (elapsed second = 0)
  merge sort ----- # swapped = 969,505 (elapsed second = 0)
  quick sort ----- # swapped = 691,807 (elapsed second = 0)
each sorted results are same.

選択ソートの効率が、更に改善しています。
シェルソートも、劇的に改善していますね。
一方、クイックソートは、更に効率が落ちています。

しかしながら、選択ソートでの値の交換回数が少ないにも関わらず、実行時間はそれほど改善していないこともわかります。

ふむふむ、、、ん？

後記

値の置換に、外部記憶装置との入出力があれば、置換回数の多寡がプログラム自体の効率に多大なる影響するものと思われます。

一方、値の変更自体が少なくても、プログラムの実行時間はそれほど減っていないケースもあります。

この辺りに、それぞれのソートアルゴリズムの性格が出ているようです。

ここまで読んでいただき、有難うございました。