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

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

## 環境
```yaml
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.選択ソート
### 特徴
- 一番小さなデータを**選択**して、先頭から順に並べ替えていく

### コード
```ruby: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
```

## 挿入ソート
### 特徴
- 正しい順序になるようにデータを**挿入**していく

### コード
```ruby: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つに**分割**しながら全体を整列していく
- 実行速度が速く、使用頻度が高い
- **再帰**（自分自身を呼び出す）を使用するので理解が難しい

### コード
```ruby: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`で評価する

```ruby: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 さんにご指摘頂き、サンプルデータの位置を正しく修正しました)

```shell:結果(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)
```
```shell:結果(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)
```
```shell:結果(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:

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