Help us understand the problem. What is going on with this article?

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

はじめに

代表的な4つのソート生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はクイックソートでした!
他と比較して圧倒的な速さ

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

おわりに

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

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

※私事ながら、当記事で通算100記事目の投稿でした!:fist_tone1:
これからも学習継続していきます:raised_hands_tone1:

terufumi1122
小売業経験8年。異業種から未経験・完全独学でサーバーサイドエンジニアになった人。 ストックついでに「いいね!」もしてもらえると嬉しいです。 HTML/CSS/JavaScript/Vue.js/Ruby/Ruby on Rails #駆け出しエンジニアとつながりたい #元転勤族
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした