[4,3,1,5,2] こんな配列があったとして、最終的に[1,2,3,4,5]っていうふうにしたい。
バブルソートとして、隣り合う要素の大小を比較して、入れ替えて、これを繰り返すアルゴリズム。
入れ替えるということはどういうことなのかということを[4,3,1,5,2]という配列で考えてみる。
[4,3,1,5,2] [3,4,1,5,2] [3,1,4,5,2] [3,1,4,5,2] // 4 < 5なのでそのまま [3,1,4,2,5] // 最終的にこうなる
配列の全要素を一回なめてみて、隣り合う要素の大小を比較して入れ替えてみると、[3,1,4,2,5]になる。つまり、一番大きい数が配列の右端に追いやられるわけだ。
この右端を除外して、残りの配列をなめてみる。([3,1,4,2])
[3,1,4,2] [1,3,4,2] [1,3,4,2] // 3 < 4なのでこのまま [1,3,2,4] // 最終的にこうなる
これを繰り返すと、[1,2,3,4,5]になるわけだね。
これをPHPで実装したのがこれ(Wikipediaより)
<?php function bubbleSort( &$arr ) { $len = count( $arr ); $i = 0; $ordered = false; $newLen = $len; while ( !$ordered ) : $ordered = true; for ( $i = 1; $i < $len; $i++ ) : $a = $arr[ $i - 1 ]; $b = $arr[ $i ]; $comp = (float)( (float)$a - (float)$b ); if ( $comp > 0 ) : $arr[ $i - 1 ] = $b; $arr[ $i ] = $a; $ordered = false; $newLen = $i; endif; endfor; $len = $newLen; endwhile; } $arr = array(4,3,1,5,2); $iterations = bubbleSort( $arr ); print_r( $arr );
Scalaだと、こう。
var list = Array(4,3,1,5,2) def bsort(list: Array[Int]): Array[Int] = { var len = list.length var newlen = 0 var ordered = false while(!ordered) { ordered = true for(i <- 1 until len) { val a = list(i) val b = list(i - 1) if (list(i) < list(i - 1)) { list(i) = b list(i - 1) = a ordered = false newlen = i } } len = newlen } list } for(i <- bsort(Array(4,3,1,5,2))) println(i)
で、これをScalaの再帰を使うと、こうなる。
def bswap(xs: List[Int]): List[Int] = xs match { case xs if xs.length == 1 => xs case (x::y::zs) if x > y => y :: bswap(x::zs) case (x::y::zs) if x <= y => x :: bswap(y::zs) } def bsort(xs: List[Int]): List[Int] = xs match { case xs if xs.length == 1 => xs case xs => { val ys = bswap(xs) bsort(ys.dropRight(1)) ++ List(ys.last) } } println(bswap(List(4,3,1,5,2))) println(bswap(List(3,1,4,2))) println(bsort(List(4,3,1,5,2))) println(bsort(List(1,1,4,3,5,2)))