バブルソート

Scala 30分プログラム

30分プログラム、その506。
「バブルソートってどう書くのー」って聞かれて、こう書くんだよーっとさらさらっと書いてやろうとしたら、普通に解らなかったので非常にあせった。
そういえば、クイックソートとかマージソートはたまに書くけど、バブルソートはめったに書いたことないなぁ。
というわけで、ちゃんと調べて、Scalaで書いてみた。

使い方

scala> bsort(Array(1,5,3))
res1: Array[Int] = Array(1, 3, 5)

ソースコード

def swap[A](xs : Array[A], i : Int, j : Int){
  val s = xs(i)
  val t = xs(j);
  xs.update(i,t)
  xs.update(j,s)
}

def bsort[A <% Ordered[A]](xs : Array[A]) : Array[A] =
{
  val n = xs size

  for(i <- 0 to n - 1){
    for(j <- 0 to n - i - 2){
      if(xs(j) > xs(j+1))
	swap(xs,j,j+1)
    }
  }
  xs
}

参考