scalaでいろんなソート

scalasort.scala

import java.math._

def bogosort(list: List[Int]): List[Int] = {
  val r = new Random()
  def suffle(xs: List[Int]): List[Int] = {
    xs.sortWith((i, j) => r.nextInt < 0)
  }
  def isSorted(xs: List[Int]): Boolean = {
    xs == xs.sorted
  }
  def check(xs: List[Int]): List[Int] = xs match {
    case Nil => List()
    case list : List[Int] if isSorted(list) => {
      println("sorted")
      list
    }
    case list: List[Int] => {
      println("suffle")
      val s = suffle(list)
      check(s)
    } 
  }
  check(list)
}

def bubblesort(list: List[Int]): List[Int] = {
  def bswap(in: List[Int]): List[Int] = in match {
    case xs if xs.length == 1 => List(xs.head)
    case xs => {
      lazy val ys = bswap(xs.tail)
      if(xs.head > ys.head) ys.head::xs.head::ys.tail
      else xs.head::ys.head::ys.tail
    }
  }
  val ys = bswap(list)
  ys match {
    case Nil => Nil
    case x::xs => x::bubblesort(xs)
  }
}

def insertionsort(list: List[Int]): List[Int] = {
  def iswap(x: Int, xs: List[Int]): List[Int] = {
    xs match {
      case Nil => List(x)
      case y::ys => {
        if(x < y) x::xs
        else  y::iswap(x, ys)
      }
    }
  }
  list match {
    case Nil => Nil
    case x::xs => iswap(x, insertionsort(xs))
  }
}

def shellsort(list: List[Int]): List[Int] = {
  def sinsert(h: Int, xs: List[Int]): List[Int] = {
    lazy val ys = insertionsort(xs.filter(_ % h == 0))
    if(h == 1) ys else sinsert(h - 1, ys)
  }
  val h = list.size / 3
  sinsert(3, list)
}


def fibonacci(limit: Int): List[Int] = {
  def exec(list: List[Int]): List[Int] = list match {
    case Nil => Nil
    case list if list.size == 1 => exec(1::list)
    case a::b::tail => {
      if(a + b > 1000) a::b::tail else exec((a + b)::a::b::tail)
    }
  }
  exec(List(0)).reverse
}

def fibonacci(limit: Int) = {
  var i = 0;
  var j = 1;
  println(i)
  println(j)
  while((i + j) <= limit) {
    println(i + j)
    val k = i + j
    i = j
    j = k
  }
}