Haskell勉強メモ 7

クイックソート

アルゴリズムの定番クイックソート。

といっても、私はアルゴリズムをちゃんと勉強したことないので名前しか知らないのだけれど。。

これを関数型ではどうやって解くのかを見ていく。

が、先に手続き型ではどうやるのか。アルゴリズム本を見ながら慣れてるScalaで手続き的に書いてみる。

クイックソートとは

配列を分割して、それぞれ再帰的に解いてまとめる分割統治法にのっとったアルゴリズム。

適当にpivotを選び出し、配列全体を「pivot未満のグループ」と「pivot以上のグループ」に分割してそれぞれ再帰的に解く。

Scalaで手続き的に書く場合（参考）

def quickSort(xs: Array[Int]): Array[Int] = {
  def swap(i: Int, j: Int): Unit = {
    val t = xs(i)
    xs(i) = xs(j)
    xs(j) = t
  }
  def sort(left: Int, right: Int): Unit = {
    val pivot = xs((left + right) / 2)
    var i     = left
    var j     = right

    while (i <= j) {
      while (xs(i) < pivot) i += 1
      while (xs(j) > pivot) j -= 1
      if (i <= j) {
        swap(i, j)
        i += 1
        j -= 1
      }
    }
    if (left < j) sort(left, j)
    if (j < right) sort(i, right)
  }
  sort(0, xs.length - 1)
  xs
}

写経してみたが、手続き的な実装はいまいち分からん。。

Haskell版

quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x : xs) =
  let smallerOrEqual = [a | a <- xs, a <= x]
      larger = [a | a <- xs, a > x]
   in quicksort smallerOrEqual ++ [x] ++ quicksort larger

*Main> quicksort [10,8,1,3,4,12,4,1,3,9,8]
[1,1,3,3,4,4,8,8,9,10,12]

なんと分かりやすいことか。。ピボット a より小さいものと大きいものに分けてそれを再帰する。とても分かりやすい。

これをScalaで書いてみる。

def quickSort(list: List[Int]): List[Int] = {
  list match {
    case Nil => Nil
    case ::(x, xs) =>
      val smallerOrEqual = for (a <- xs; if a <= x) yield a
      val larger = for (a <- xs; if a > x) yield a
      quickSort(smallerOrEqual) ++ List(x) ++ quickSort(larger)
  }
}

ロジックがそのまま記述されており、手続き的な実装と比べて明らかに読みやすい。