【学習ログ】【Ruby】選択ソート(単純選択法)プログラム

※このページは過去に自分がRubyの勉強をしたときの学習ログです。誰かの参考になれば幸いです。

選択ソート(単純選択法)プログラムをRubyで作成してみた

完成コードの前に選択ソートについて考える

選択ソート(単純選択法)は配列の最小値(最大値)を持つ要素を探して、それを配列の先頭要素と交換することで整列を行うアルゴリズムのこと。
動きがないとわかりづらいが、以下の動画が参考になった。

完成コードいろいろ

# 選択ソート
def selection_sort(numbers)
  i = 0
  while i < numbers.length - 1
    min = i
    k = i + 1
    while k < numbers.length
      if numbers[k] < numbers[min]
        min = k
      end
        k += 1
    end
    numbers[min], numbers[i] = numbers[i], numbers[min]
    i += 1
  end
  numbers
end

p selection_sort([12, 13, 11, 14, 10])

実行結果 →
[12, 13, 11, 14, 10]
[10, 13, 11, 14, 12]
[10, 11, 13, 14, 12]
[10, 11, 12, 14, 13]
[10, 11, 12, 13, 14]

def selection_sort(numbers)
	(numbers.length-1).times do |i|
    min = i
    k = i + 1
    (numbers.length-k).times do
      if numbers[k] < numbers[min]
          min = k
      end
      k = k + 1
    end

	numbers[min] , numbers[i] = numbers[i] , numbers[min]
		i = i + 1
  end
numbers
end

p selection_sort([3,9,6,1,2])

実行結果 →[1, 2, 3, 6, 9]

def selection_sort(numbers)
  numbers.each_index do |i|
    min = i
    
    ((i+1)...numbers.length).each do |k|
      if numbers[k] < numbers[min]
        min = k
      end
    end
    numbers[min] , numbers[i] = numbers[i] , numbers[min]
  end
end

p selection_sort([3,9,6,1,2])

実行結果 →[1, 2, 3, 6, 9]

解説(我流です)

本当に数学的なものが苦手でして・・

繰り返し処理の中で繰り返し処理を行っていたり、
変数ikminの関係について何故そうなるのかしっくり来ていない現状。。
だが、処理の流れについては概ね理解できた(と思う)

時間はかかったがなんとか理解できた

ようやく全体像が理解できてきた。
最小値を見つけるコード、正解例をみてもピンとこなかったが、
ひとつづつ隣の要素と比べるんですね(地道・・)
まとめると以下の通り。

また、選択ソートプログラムについては、以下の動画の説明がわかりやすかった。
言語は異なるが、考え方としては概ね同じだと思うので。

本日は以上となります。

最後までお読みくださりありがとうございました。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

コメントする