Zenn
🔖

Elixir でクイックソートかいてみた（Goとの比較付き）

2020/10/10に公開
Elixir
Go
tech

クイックソート

Elixir 好きなのでクイックソート書いてみました。
Qiitaで投稿していること多めですが、最近気になってたのでzennで初投稿！
https://qiita.com/koyo-miyamura

defmodule QuickSort do
  def sort([]), do: []

  def sort([a]), do: [a]

  def sort([pivot | a]) do
    sort(a |> Enum.filter(&(&1 < pivot))) ++ [pivot] ++ sort(a |> Enum.filter(&(&1 >= pivot)))
  end
end

IO.inspect(QuickSort.sort([1, 3, 2, 7, 13, 21, 11, 4]))

 $ elixir main.exs 
[1, 2, 3, 4, 7, 11, 13, 21]

ちなみにGoだとこんな感じかな（ピボット選定は変えてますが）

func quickSort(a []int) {
	if len(a) <= 1 {
		return
	}

	pi := len(a) / 2
	pivot := a[pi]
	a[pi], a[len(a)-1] = a[len(a)-1], a[pi]

	i := 0
	for j := 0; j < len(a)-1; j++ {
		if a[j] < pivot {
			a[i], a[j] = a[j], a[i]
			i++
		}
	}
	a[i], a[len(a)-1] = a[len(a)-1], a[i]

	quickSort(a[:i])
	quickSort(a[i+1:])
}

Elixirはパターンマッチを用いてifなしで条件分岐を表現できるので、再帰の終了処理を簡潔に記述出来ていいですね。
とはいえGoの方はin-placeになるように書いているので純粋な比較ではないですが参考までに。

福岡のElixirコミュニティ、 fukuoka.ex もよろしくお願いいたします！
https://fukuokaex.connpass.com/

Discussion