アルゴリズムの勉強 バブルソート

Webアプリを作っているとアルゴリズムなんて忘れてしまいます。
でも、たまに転職の時にコードを書かされたり・・・

実際にバブルソートの質問はありました。

さて、このバブルソートですが、まあシステムで使われる事は無いでしょう。
単純で分かりやすいですが、遅すぎます!

仕組みは、n番目とn+1番目を比較して大きい(小さい)場合は交換します。 それを一番目の要素から最後まで実施します。 交換が無くなればソート完了です。

処理フロー

例えば1,2,6,3,8,9,6と並んでいるリストを小さい順に並べてみます。

最初1,2を比較し小さい順に並んでいるので、次は2,6を比較し、、、
次々と比較すると、6,3が小さい順に並んでいないことがわかります。

さて6,3は小さい順に並んでいないので、交換して並び替えます。 その際、「交換しました」というフラグをONにします。

引き続き6,8を比較し小さい順に並んでいるので、次へ、、、
次に9,6が小さい順に並んでいないので、交換して並び替えます。

最後の行まで入れ替え処理を行いましたが、「交換しました」フラグがONのままです。
まだ並んでいない箇所があるかもしれないため、再度１番目から順に比較していきます。
その際、「交換しました」フラグはOFFに初期化しておきます。

値を順に比較していくと、8,6がまだ並んでいませんでしたので入れ替えます。
ここでまた「交換しました」というフラグをONにします。

この時点で並んでいますが、「交換しました」フラグはONです。 そのため、再度１番目から比較し、「交換しました」フラグがOFFのまま終われば並び替えが完了したと判断します。

ソースコード

Scalaで記述

def sort[T: ClassTag](list: Array[T])(compare: (T, T) => Boolean): Array[T] = {
  val result = copy[T](list)
  var swapFlag = false
  do {
    swapFlag = false
    for (i <- 0 until result.size - 1) {
      if (compare(result(i + 1), result(i))) {
        val tmp = result(i)
        result(i) = result(i + 1)
        result(i + 1) = tmp
         swapFlag = true
      }
    }
  } while (swapFlag)
  result
}

sort(array)((a1, a2) => a1 > a2)

Sampleソース

GitHub patolie/play-sampleにソースコードをあげています。