読者です 読者をやめる 読者になる 読者になる

merge sortの練習

Scala

この二ヶ月間ちょい、仕事の方で一杯一杯だったので、全然趣味的なプログラミングができずに、割と悶々としておりました。

で、最近になって落ち着いてきたので、以前少し触っていたScalaを思い出そうとしたら完全に忘れていることに気づきリハビリがてら何か書いてみようかと。あと、EclipseScala IDEを試したい、など。

object Main {
  def mergeSort[T <% Ordered[T]](xs: List[T]): List[T] = {
    def split(xs: List[T]): (List[T], List[T]) = xs.splitAt(xs.size / 2)

    def merge(ls: List[T], rs: List[T], ms: List[T]): List[T] = (ls, rs) match {
      case (Nil, Nil) => ms
      case (hd :: tl, Nil) => merge(tl, rs, hd :: ms)
      case (Nil, hd :: tl) => merge(ls, tl, hd :: ms)
      case (lhd :: ltl, rhd :: rtl) if lhd < rhd => merge(ltl, rs, lhd :: ms)
      case (lhd :: ltl, rhd :: rtl) => merge(ls, rtl, rhd :: ms)
    }

    def sort(xs: List[T]): List[T] = xs match {
      case Nil => xs
      case x :: Nil => xs
      case _ =>
        val (l, r) = split(xs)
        merge(sort(l), sort(r), Nil).reverse
    }

    sort(xs)
  }

  def main(args: Array[String]): Unit = {
    val sortedInt = mergeSort[Int](List(7, 3, 9, 4, 2, 8, 1, 6, 5))
    println(sortedInt)
    val sortedStr = mergeSort[String](List("qwer", "cvbn", "kjhg", "asdf", "zxcv", "mnbv"))
    println(sortedStr)
  }
}

以前、IntelliJ IDEAを使ってみたときは操作感が気持ち悪い系の印象をもったのですが、EclipseScala IDEはまぁまともで、動作も軽いのでしばらくこっちを使ってみることにしました。