バブルソートについてちょっとだけ考えてみる

バブルソート - Wikipedia

[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)))