【Ruby】バブルソート・選択ソート・挿入ソート・クイックソートの速度の違いを検証してみた

はじめに

代表的な４つのソートを生Rubyで書き、ついでに速度の違いを検証してみました。
※勉強として、Rubyの便利メソッドは使わないようにしています。

環境

OS: macOS Catalina 10.15.3
Ruby: 2.6.5

前提

実装方法

• 左->右 に 小->大 となるような昇順での並び替えとする
• Rubyのメソッドは極力使わず、while,if,length,ceilのみで実装する

速度の検証方法

• 1~100000(10万)の重複しない数字をランダムに並べた配列をサンプルとする
• 検証は同条件で3回行い、平均値で評価する
• Benchmarkライブラリの出力のうち、userで評価する

1.バブルソート

特徴

• 隣り合う要素の大小を比較し、小さい方が左になるように並べ替えていく
• 実行速度が遅いためあまり使われない

コード

bubble_sort.rb

def bubble_sort(array)
  k = 0

  while k < array.length - 1
    i = 0

    while i < array.length - 1

      if array[i] > array[i+1]
        w = array[i]
        array[i] = array[i+1]
        array[i+1] = w
      end

      i += 1
    end

    k += 1
  end
  
  array
end

2.選択ソート

特徴

• 一番小さなデータを選択して、先頭から順に並べ替えていく

コード

selection_sort.rb

def selection_sort(array)
  i = 0

  while i < array.length - 1
    indexMin = i
    k = i + 1

    while k < array.length

      if array[k] < array[indexMin]
        indexMin = k
      end

      k += 1
    end

    w = array[i]
    array[i] = array[indexMin]
    array[indexMin] = w

    i += 1
  end
  
  array
end

挿入ソート

特徴

• 正しい順序になるようにデータを挿入していく

コード

insertion_sort.rb

def insertion_sort(array)
  i = 0

  while i < array.length - 1
    x = array[i+1]
    k = i+1

    while (k > 0) && (array[k-1] > x)
      array[k] = array[k-1]
      k = k-1
    end

    array[k] = x
    i += 1
  end
  
  array
end

クイックソート

特徴

• データを大小のグループ2つに分割しながら全体を整列していく
• 実行速度が速く、使用頻度が高い
• 再帰（自分自身を呼び出す）を使用するので理解が難しい

コード

quick_sort.rb

def quick_sort(array, left, right)
  pivot_index = ((left + right).to_f / 2.to_f).ceil
  pivot = array[pivot_index]
  i = left
  k = right

  while i < k

    while (array[i] < pivot) && (i < right)
      i += 1
    end

    while (array[k] > pivot) && (k > left)
      k -= 1
    end

    if i < k
      w = array[i]
      array[i] = array[k]
      array[k] = w
    end
  end

  if array[left] > array[k]
    w = array[left]
    array[left] = array[k]
    p array[k] = w
  end

  ### ここから再帰呼び出し ###
  if left < k-1
    quick_sort(array, left, k-1)
  end
  
  if k+1 < right
    quick_sort(array, k+1, right)
  end
  ### ここまで再帰呼び出し ###

  array
end

速度

以下の内容で検証します。
(2020/2/18 @Nabetani さんにご指摘頂き、サンプルデータの位置を正しく修正しました)

(再掲)速度の検証方法

• 1~100000(10万)の重複しない数字をランダムに並べた配列をサンプルとする
• 検証は同条件で3回行い、平均値で評価する
• Benchmarkライブラリの出力のうち、totalで評価する

benchmark.rb

require 'benchmark'

require './bubble_sort.rb'
require './selection_sort.rb'
require './insertion_sort.rb'
require './quick_sort.rb'

Benchmark.bm 10 do |r|

  array = [*1..100000].shuffle
  r.report "bubble_sort" do
    bubble_sort(array)
  end

  array = [*1..100000].shuffle
  r.report "selection_sort" do
    selection_sort(array)
  end
  
  array = [*1..100000].shuffle
  r.report "insertion_sort" do
    insertion_sort(array)
  end

  array = [*1..100000].shuffle
  r.report "quick_sort" do
    quick_sort(array, 0, array.length - 1)
  end

end

実行結果

(2020/2/18 @Nabetani さんにご指摘頂き、サンプルデータの位置を正しく修正しました)

結果(1回目)

                 user     system      total        real
bubble_sort    570.124053   1.904297 572.028350 (577.834412)
selection_sort 161.563083   0.357987 161.921070 (162.479403)
insertion_sort 145.170302   0.817478 145.987780 (148.046180)
quick_sort       0.121813   0.000896   0.122709 (  0.124643)

結果(2回目)

                 user     system      total        real
bubble_sort    571.812702   2.242382 574.055084 (580.725139)
selection_sort 164.664549   0.478888 165.143437 (165.996426)
insertion_sort 142.275122   0.445982 142.721104 (143.516951)
quick_sort       0.124349   0.001020   0.125369 (  0.129149)

結果(3回目)

                 user     system      total        real
bubble_sort    569.067523   1.805529 570.873052 (574.410594)
selection_sort 164.282769   0.491190 164.773959 (165.733148)
insertion_sort 140.670870   0.424666 141.095536 (141.956379)
quick_sort       0.117259   0.001045   0.118304 (  0.120254)

---

結論

	平均（秒）
バブルソート	570.334
選択ソート	163.503
挿入ソート	142.705
クイックソート	0.120

TOPはクイックソートでした！
他と比較して圧倒的な速さ！

こりゃバブルソートが使われない理由もよく分かりますね

おわりに

最後まで読んで頂きありがとうございました

どなたかの参考になれば幸いです

※私事ながら、当記事で通算１００記事目の投稿でした！
これからも学習継続していきます