【実装コード有り】アルゴリズム初心者がセレクトソートとクイックソートをElixirで実装する

ソートの必要性について

前回の記事で実装した二分探索は対象のリストがソートされていることが前提であり、つまりはリストをソートしてくれるアルゴリズムが必要になるということ
え？もうEnum.sort()あるけど?とは言わない約束
一度自分で実装することが大事なんじゃないかと勝手に思ってます

セレクトソートについて

超シンプルなソート方法です
リストから最小値を取得して新たな配列に順次追加してくというもの
シンプルなリストを使って実際の動きを見てみる

簡単な例

lst = [7,3,2,5,4,8,9,1,10,6]
sorted_lst = []

#1回目
min_num = 1
lst = [7,3,2,5,4,8,9,10,6]
sorted_lst = [1]

#2回目
min_num = 2
lst = [7,3,2,5,4,8,9,10,6]
sorted_lst = [1,2]
:
:
#10回目
min_num = 10
lst = []
sorted_num = [1,2,3,4,5,6,7,8,9,10]

とりあえずElixirで実装してみる

Elixirでのセレクトソート
最小値の探索とベースのリストから最小値の削除には Enum.min()とList.delete()メゾットをコンボで行なっている
同じ数値が現れても問題なく操作を行える

iex(13)> min = Enum.min([1,1,2,3,4,5])
1
iex(14)> List.delete([1,1,2,3,4,5], min)
[1, 2, 3, 4, 5]

こいつを使ってセレクトソートを実装するとこんな感じになった

defmodule Algo do
  def select_sort(lst) do
    _select_sort(lst, [])
  end
  defp _select_sort([], accum), do: accum
  defp _select_sort(lst, accum) do
    min_num = lst |> Enum.min()
    next_lst = List.delete(lst, min_num)
    _select_sort(next_lst, accum ++ [min_num])
  end
end

正しく動作しているかを簡易テストで確かめる

tests = [
  Algo.select_sort([1,4,3,7,5,1,2,13,9,23,5,57]) == [1, 1, 2, 3, 4, 5, 5, 7, 9, 13, 23, 57],
  Algo.select_sort([]) == [],
  Algo.select_sort([1]) == [1],
  Algo.select_sort([2,4,3,5]) == [2,3,4,5],
  Algo.select_sort([4,2,6,7,8,3,12,1,3,76,345,0,67]) == [0, 1, 2, 3, 3, 4, 6, 7, 8, 12, 67, 76, 345]
]

IO.inspect(tests)
#[true, true, true, true, true]

いい感じですね
ただ、この方式だとリストの要素数だけ上記の試行を行う必要がある
そのため10億個の要素があるようなリストが現れた日には詰む
より手順の少ないソートが必要になる

クイックソートについて

言葉で説明するのが難しいので実データの動きを見ていく
先ほど同様にシンプルなリストを用意した

lst = [7,3,2,5,4,8,9,1,10,6]

ではソートを開始
lstの先頭の値を取得してsorted_lstに追加していく
追加する際は昇順になるように適宜行う

#1回目
lst = [3,2,5,4,8,9,1,10,6]
sorted_lst = [7]

#2回目
lst = [2,5,4,8,9,1,10,6]
sorted_lst = [3,7]

#3回目
lst = [5,4,8,9,1,10,6]
sorted_lst = [2,3,7]

#4回目
lst = [4,8,9,1,10,6]
sorted_lst = [2,3,5,7]
:
:
#10回目
lst = [6]
sorted_lst = [1,2,3,4,5,6,7,8,9,10]

クイックソートはどのように要素を取得するかによって試行回数が大きく変化するらしい
今回はElixirのheadとtailを使いたかったので先頭の要素をマッチさせて取得している
この取得した要素のことをピポットと言い、ピポットの取得方法によって性能が変化する

Elixirでのクイックソート
quick_sort()とappend()でそれぞれ再帰している
quick_sort()では受け取ったリストから先頭を取得してソート済み配列に追加していく
追加の際には昇順になるように追加したいのでappend()で判定しつつ良しなに追加する

defmodule Algo do
  def quick_sort(lst), do: _quick_sort(lst, [])
  defp _quick_sort([], accum), do: accum
  defp _quick_sort([head | tail], accum) do
    res = append(head, accum, [])
    _quick_sort(tail, res)
  end
  def append(num, [], accum), do: accum ++ [num]
  def append(num, [head | tail], accum) do
    case num > head do
      true -> append(num, tail, accum ++ [head])
      false -> accum ++ [num] ++ [head] ++ tail
    end
  end
end

同様にテストを試す

tests = [
  Algo.quick_sort([1,4,3,7,5,1,2,13,9,23,5,57]) == [1, 1, 2, 3, 4, 5, 5, 7, 9, 13, 23, 57],
  Algo.quick_sort([]) == [],
  Algo.quick_sort([1]) == [1],
  Algo.quick_sort([2,4,3,5]) == [2,3,4,5],
  Algo.quick_sort([4,2,6,7,8,3,12,1,3,76,345,0,67]) == [0, 1, 2, 3, 3, 4, 6, 7, 8, 12, 67, 76, 345]
]

IO.inspect(tests)
#result
#[true, true, true, true, true]

もう少し短く早くできたのでこちらもどうぞ
たぶんこれが一番早いと思います(大嘘

defmodule Algo do
  def quick_sort(lst) when length(lst) < 2, do: lst
  def quick_sort([head | tail]) do
    smaller = Enum.filter(tail, &(&1 <= head))
    bigger = Enum.filter(tail, &(&1 > head))
    quick_sort(smaller) ++ [head] ++ quick_sort(bigger)
  end
end

二分探索のように

ピポット以上の値を持つリスト
ピポット以下の値を持つリスト

の2つに分割してソートを行なっていく

lst = [3,2,5,4,8,9,1,10,6]
fetch_num = 3
smaller = [2,1]
bigger = [5,4,8,9,10,6]

quick_sort(smaller) ++ [fetch_num] ++ quick_sort(bigger)
#最終形はこんな感じになる
[1] ++ [2] ++ [3] ++ [4] ..... [10]

また簡易テストを試す

tests = [
  Algo.quick_sort([1,4,3,7,5,1,2,13,9,23,5,57]) == [1, 1, 2, 3, 4, 5, 5, 7, 9, 13, 23, 57],
  Algo.quick_sort([]) == [],
  Algo.quick_sort([1]) == [1],
  Algo.quick_sort([2,4,3,5]) == [2,3,4,5],
  Algo.quick_sort([4,2,6,7,8,3,12,1,3,76,345,0,67]) == [0, 1, 2, 3, 3, 4, 6, 7, 8, 12, 67, 76, 345]
]

IO.inspect(tests)
#result
#[true, true, true, true, true]