これは GW Advent Calendar 2020 俺GW頑張った の6日目の記事です。
前日の記事は Fediverseにいます さんの いろいろした です。
翌日の記事は しそのは とうふ さんの 結果何かやったかと言われたら微妙 です。
はじめに
ソートアルゴリズムの復習とScalaの学習を兼ねて、各種ソートアルゴリズムをScalaで実装してみる。
ソースは nhiguchi/sort-samples にアップした。
基本trait
trait Sorter {
def sort(seq: Seq[Int]): Seq[Int]
}
各種ソートアルゴリズム
挿入ソート
object InsertionSorter extends Sorter {
override def sort(seq: Seq[Int]): Seq[Int] = {
seq.foldLeft(Seq.empty[Int]) { (seq, e) =>
val index = seq.indexWhere(_ > e)
if (index == -1) {
seq :+ e
} else {
seq.take(index) :+ e :++ seq.drop(index)
}
}
}
}
マージソート
object MergeSorter extends Sorter {
override def sort(seq: Seq[Int]): Seq[Int] = {
def _sort(leftSeq: Seq[Int], rightSeq: Seq[Int]): Seq[Int] = {
(leftSeq, rightSeq) match {
case (left, Nil) => left
case (Nil, right) => right
case (leftHead :: leftTail, rightHead :: rightTail) =>
if (leftHead < rightHead) leftHead +: _sort(leftTail, rightSeq)
else rightHead +: _sort(leftSeq, rightTail)
}
}
val pivot = seq.size / 2
if (pivot == 0) seq
else {
val split = seq.splitAt(pivot)
_sort(sort(split._1), sort(split._2))
}
}
}
クイックソート
object QuickSorter extends Sorter {
override def sort(seq: Seq[Int]): Seq[Int] = {
if (seq.size <= 1) seq
else {
val pivot = seq(seq.size / 2)
sort(seq.filter(_ < pivot)) ++
seq.filter(_ == pivot) ++
sort(seq.filter(pivot < _))
}
}
}
まとめ
Scalaは高レイヤ処理が得意だが、関数型言語は低レイヤ処理にも強いことを改めて感じた。
これ以上複雑なソートになると実装が大変だが、気が向いたら残りのソートも実装してみたい。