[scala] mergesort(match) 예제

코세라 Scala 강의 중 MergeSort 예제에서 조금 이해하기 쉽게 분리한 예제이다.

https://www.coursera.org/learn/progfun1/lecture/0uFfe/lecture-5-2-pairs-and-tuples

object MergeSort {
  def merge(left: List[Int], right: List[Int]): List[Int] = (left, right) match {
    case (l, Nil) => l
    case (Nil, r) => r
    case (leftHead :: leftTail, rightHead :: rightTail) =>
      if (leftHead < rightHead) leftHead::merge(leftTail, right)
      else rightHead :: merge(left, rightTail)
  }

  def mergeSort(list: List[Int]): List[Int] = {
    val n = list.length / 2
    if (n == 0) list
    else {
      val (left, right) = list splitAt n
      merge(mergeSort(left), mergeSort(right))
    }
  }
}

결과

scala> MergeSort.mergeSort(List())

res17: List[Int] = List()

scala> MergeSort.mergeSort(List(100,50,120,19))

res16: List[Int] = List(19, 50, 100, 120)

Int 타입을 T 타입으로 (order:(T, T) => scala.Boolean)을 추가해서 compare를 할 수 있게 한다.

object MergeSort {
  def mergeSort[T](list: List[T])(order: (T, T) => scala.Boolean): List[T] = {
    val n = list.length / 2
    if (n == 0) list
    else {
      def merge(left: List[T], right: List[T]) : List[T] = (left, right) match {
        case (l, Nil) => l
        case (Nil, r) => r
        case (leftHead :: leftTail, rightHead :: rightTail) =>
          if (order(leftHead, rightHead)) leftHead::merge(leftTail, right)
          else rightHead :: merge(left, rightTail)
      }
      val (left, right) = list splitAt n
      merge(mergeSort(left)(order), mergeSort(right)(order))
    }
  }
}

object Main extends App {
  println(MergeSort.mergeSort(List(100,50,120,19))((x: Int, y: Int) => (x < y)))
  println(MergeSort.mergeSort(List(100,50,120,19))((x: Int, y: Int) => (x > y)))
  println(MergeSort.mergeSort(List("samuel","jack","juno","ben"))((x: String, y: String) => (x.compareTo(y) < 0)))
  println(MergeSort.mergeSort(List("samuel","jack","juno","ben"))((x: String, y: String) => (x.compareTo(y) > 0)))
}

결과는 다음과 같다.

List(19, 50, 100, 120)

List(120, 100, 50, 19)

언제나 스칼라는 타입을 숨길 수 있다.

List(100,50,120,19))((x, y) => (x > y))

여기에 math.Ordering을 임포트해본다.

import math.Ordering
object MergeSort {
  def mergeSort[T](list: List[T])(order: Ordering[T]): List[T] = {
    val n = list.length / 2
    if (n == 0) list
    else {
      def merge(left: List[T], right: List[T]) : List[T] = (left, right) match {
        case (l, Nil) => l
        case (Nil, r) => r
        case (leftHead :: leftTail, rightHead :: rightTail) =>
          if (order.lt(leftHead, rightHead)) leftHead::merge(leftTail, right)
          else rightHead :: merge(left, rightTail)
      }
      val (left, right) = list splitAt n
      merge(mergeSort(left)(order), mergeSort(right)(order))
    }
  }
}

object Main extends App {
  println(MergeSort.mergeSort(List(100,50,120,19))(Ordering.Int))
  println(MergeSort.mergeSort(List(100,50,120,19))(Ordering.Int))
  println(MergeSort.mergeSort(List("samuel","jack","juno","ben"))(Ordering.String))
  println(MergeSort.mergeSort(List("samuel","jack","juno","ben"))(Ordering.String))
}

결과는 이전과 동일하다. 

여기에 implicit을 추가해본다. 그리고 implicit을 쓰면 적당히 코드 삭제가 가능하다.

import math.Ordering
object MergeSort {
  def mergeSort[T](list: List[T])(implicit order: Ordering[T]): List[T] = {
    val n = list.length / 2
    if (n == 0) list
    else {
      def merge(left: List[T], right: List[T]) : List[T] = (left, right) match {
        case (l, Nil) => l
        case (Nil, r) => r
        case (leftHead :: leftTail, rightHead :: rightTail) =>
          if (order.lt(leftHead, rightHead)) leftHead::merge(leftTail, right)
          else rightHead :: merge(left, rightTail)
      }
      val (left, right) = list splitAt n
      merge(mergeSort(left), mergeSort(right))
    }
  }
}

object Main extends App {
  println(MergeSort.mergeSort(List(100,50,120,19)))
  println(MergeSort.mergeSort(List(100,50,120,19)))
  println(MergeSort.mergeSort(List("samuel","jack","juno","ben")))
  println(MergeSort.mergeSort(List("samuel","jack","juno","ben")))
}

역시 결과가 동일하다.