Scalaクイックソート

クイックソートは、ぶんかつほう(Divide and conquer)ポリシーを使用して、1つのシーケンス#シーケンス#(list)を2つのサブシーケンス(sub-lists)に分割します.
手順は次のとおりです.

数列から「基準」(pivot)と呼ばれる要素を選択し、

は数列を並べ替え、すべての要素が基準値より小さいものは基準の前に配置され、すべての要素が基準値より大きいものは基準の後ろに配置されます(同じ数は任意の側に配置できます).このパーティションが終了すると、基準は数列の中間位置にあります.これをパーティション操作と呼ぶ.

再帰(recursive)基準値要素より小さいサブ数列と基準値要素より大きいサブ数列を並べ替える.

再帰の最も下部の状況は、数列のサイズがゼロまたは1であり、つまり永遠にソートされていることです.ずっと再帰していますが、このアルゴリズムは必ず終わります.毎回の反復(iteration)では、少なくとも1つの要素を最後の位置に置くからです.
以上ウィキペディアより
配列に対する高速ソートの多くはすでに実現されている.
このクイックソートはList向けであり、scalaのListは再帰タイプ(チェーンテーブルクラス)であり、scalaで再帰クラスを実現するクイックソートは以下の通りである.

def sort(ls: List[Int]): List[Int] = {
  ls match {
    case Nil => Nil
    case base :: tail => {
      val (left, rigth) = tail.partition(_ < base)
      sort(left) ::: base :: sort(rigth)
    }
  }
}

sort(List(4,3,5,2,20,1))

 
6行のコードはすべて書き終わって、しかも論理はとてもはっきりしていて、私自身はすべてこんなにきれいなコードがあると信じられません
私たちは1行1行見に来ました.

ls match {

lsをモードマッチングし、

 case Nil => Nil

リストが空の場合は戻ります

case base :: tail => {

リストがヘッダーと末尾に分割できる場合は、一致は成功します(ヘッダーと末尾の基準).

 val (left, rigth) = tail.partition(_ < base)

末尾をbaseより小さい分割で左、baseより大きい分割で右にします.

sort(left) ::: base :: sort(rigth)

再帰左+中間+再帰右.
この数行のコードだけでListクラスの迅速なソートが完了します.
この再帰的な文法は本当にきれいですね.