Rubyでソート（選択・バブル・挿入・クイック）を試してみた．

ソートとは

今回も前回同様，基本的なお話なので配列で考えます．配列の中にある要素を大きさ順で並べ替えれないかな？...はい，そこのあなた！そんな時はソートを使いましょうよ！！
とまぁニュアンスはこんな感じですね．

注意：配列の頭 -> 要素番号が小さい方・配列のお尻 -> 要素番号が大きい方　とさせてください．

選択ソート（selective_sort）

• 確定していない配列の要素から一番小さい要素を見つけてきて，それを配列の確定しない箇所の頭に移動させ確定させる．

これを要素の数-1回繰り返すとできます．（なぜ要素の数-1回なのかと言うと，最後の一個は別に何もしなくてもソートされていることになっているからです）

selective_sort.rb

def selective_sort(nums)
  sorts = nums.clone
  min_index = get_min_index(sorts, 0)
  for i in 0...sorts.size-1
    min_index = get_min_index(sorts, i)
    sorts[i], sorts[min_index] = sorts[min_index], sorts[i]
  end
  return sorts
end

def get_min_index(nums, start)
  return nil if start >= nums.size
  min_index = start
  for check in start...nums.size
    min_index = check if nums[check] < nums[min_index]
  end
  return min_index
end

nums = 10.times.map{rand(100)}
sorted = selective_sort(nums)
p "nums: #{nums}" # "nums: [47, 63, 93, 58, 29, 27, 96, 36, 60, 62]"
p "sorted: #{sorted}" # "sorted: [27, 29, 36, 47, 58, 60, 62, 63, 93, 96]"

バブルソート（bubble_sort）

1. 配列のお尻から見て2つの要素を比べて小さい方・大きい方の順に並べ替える．
2. 1を確定していない配列の頭に来るまで繰り返して，頭にきたら先頭にある値を確定させる．
3. 2を配列全体が確定するまで繰り返す．

bubble_sort.rb

def bubble_sort(nums)
  sorts = nums.clone
  for k in 0...sorts.size-1
    # confirm minimum nums from sorts.start
    (sorts.size-1).step(k+1, -1) do |i|
      # comparing 2nums from sorts.last
      sorts[i-1], sorts[i] = sorts[i], sorts[i-1] if sorts[i-1] > sorts[i]
    end
  end
  return sorts
end

nums = 10.times.map{rand(100)}
sorted = bubble_sort(nums)
p "nums: #{nums}" # "nums: [23, 77, 31, 51, 20, 70, 6, 58, 12, 76]"
p "sorted: #{sorted}" # "sorted: [6, 12, 20, 23, 31, 51, 58, 70, 76, 77]"

挿入ソート（insert_sort）

1. 配列の頭の一つを確定させます．
2. 確定していない配列の頭の要素を抜き取ります．（あくまでイメージです）
3. 抜き取った値を確定している配列の要素の頭から比べていく，
4. 抜き取った値がその要素より小さかったらその要素の前に抜き取った値を挿入する．

この1~4を配列の要素が全て確定するまで繰り返します．

insert_sort.rb

def insert_sort(nums)
  sorts = nums.clone
  for i in 1...sorts.size
    # confirm minimum nums from sorts.start+1
    check = sorts[i].clone
    k = i
    while k>0 && sorts[k-1]>check
      # shift sorts[k-1] to k if sorts[k-1] greater than check
      sorts[k] = sorts[k-1]
      k -= 1
    end
    sorts[k] = check
  end
  return sorts
end
nums = 10.times.map{rand(100)}
sorted = insert_sort(nums)
p "nums: #{nums}" # "nums: [73, 6, 76, 73, 44, 46, 47, 98, 69, 98]"
p "sorted: #{sorted}" # "sorted: [6, 44, 46, 47, 69, 73, 73, 76, 98, 98]"

クイックソート（quick_sort）

これは説明がちょっと図がないと難しいので気になる方はネットで調べて見てもらうことをお勧めします．
イメージとしては

1. 配列の頭の要素を基準に要素を大小で頭の方とお尻の方に振り分けていく．
2. 全部振り分けられたら，基準の要素を大小の境目の要素と入れ替える．
3. 基準の要素だった要素以外の配列（大体が2つに分かれる）を別々に1と2を繰り返す．

これを繰り返していくとソートできます．

quick_sort.rb

def quick_sort(nums, left, right)
  i = left + 1
  k = right
  while i<k
    while nums[i]<nums[left] && i<right
      i += 1
    end
    while nums[k]>=nums[left] && k>left
      k -= 1
    end
    nums[i], nums[k] = nums[k], nums[i] if i<k
  end
  nums[left], nums[k] = nums[k], nums[left] if nums[left]>nums[k]
  nums = quick_sort(nums, left, k-1) if left<k-1
  nums = quick_sort(nums, k+1, right) if right>k+1
  return nums
end

nums = 10.times.map{rand(100)}
sorted = quick_sort(nums.clone, 0, nums.size-1)
p "nums: #{nums}" # "nums: [79, 31, 56, 83, 80, 54, 54, 84, 65, 50]"
p "sorted: #{sorted}" # "sorted: [31, 50, 54, 54, 56, 65, 79, 80, 83, 84]"

まとめ

前回と同じまとめになってしまいます．
詳しい内容はこの本に載っていますので，オススメですよ！一見，初心者向けのイラスト豊富な内容のない本のように見えますが，中身はしっかりしていました．言語を決めてコードを書いているわけでもないのでどの言語を使う人でも読みやすい一冊でした．
https://www.amazon.co.jp/dp/B01CZDTINE/ref=dp-kindle-redirect?_encoding=UTF8&btkr=1