Sorting by swap distance - コードの恵み

ゲーム

おはじきを使ったゲームをやっていた。
おはじきに 1 から 100 までの数字を書き缶に入れておく。
缶を振ってから10個とりだして並べる。
両手の指を使っておはじきを入れ替えながら数字の順に並べる。
一応競争なんだけど一斉にやったりしているわけではないので好き勝手に遊んでいた。
すぐに効率的なやり方に気がついた。
1番小さい数字を探して1番左と入れ替える。
2番目に小さい数字を探して左から2番目と入れ替える。
要するに Selection sort だ。
他のみんなもその方法だったのだけれどもひとりだけ違っていた。
こまめに入れ替えている。Bubble sort だった。
彼は言った「これ速いよね」。
その後、競争したのかは覚えていない。
ただ覚えているのは彼がとても絵がうまかったということと、
彼の書いた絵が金賞をとって展覧会で逆さ向きに飾られていたことだけだ。

彼は正しかったのか?

話は創作なんだけれどもずっと気になっていた。
勉強して Bubble sort より効率がいい方法があることがわかった。
でも世の中的には Bubble sort の方が使われているのではないか？
例えば学校で背の順に並べるとき先生は Bubble sort を使っていたような気がする。
どうしてもっと効率のいい方法を使わないのか？
思いついた理由は2つ

隣り合っている方が比較しやすいから
列を乱したくないから(再度整列させるのが手間だから)

でも間違っていたことに最近気がついた。
『岩波講座ソフトウェア科学 3 アルゴリズムとデータ構造』に書いてあった。

ランダムアクセスできることが多くのアルゴリズムを効率よく実現する上での鍵になる

つまり、現実世界ではおはじきが手の届く範囲を超えたり、おはじきの直径が 2m だったりすると離れているものは簡単に交換できないのだ。

アルゴリズムを Swap 距離でソートする

とりあえず Bubble sort, Selection sort, Quick sort で比較してみる。

def bubble_sort(a) {
  final int N = a.size()
  for (int i = 0; i < N-1; i++) {
    for (int j = 1; j < N-i; j++) {
      if (a[j-1] > a[j]) swap(a, j-1, j)
    }
  }
  return a
}

def selection_sort(a) {
  final int N = a.size()
  for (int i = 0; i < N-1; i++) {
    int min = i
    for (int j = i+1; j < N; j++) {
      if (a[j] < a[min]) min = j
    }
    swap(a, i, min)
  }
  return a
}

def quick_sort(a) {
  def sort = { left, right ->
    if (left < right) {
      def pivot = a[left]
      int p = left
      for (int i = left+1; i <= right; i++) {
        if (a[i] < pivot) swap(a, ++p, i)
      }
      swap(a, left, p)
      call(left, p-1)
      call(p+1, right)
    }
  }
  sort(0, a.size()-1)
  return a
}

// total swap distance
distance = 0
def swap(a, i, j) {
  distance += (i-j).abs()
  Collections.swap(a, i, j)
}

def algorithms = []
algorithms << this.&bubble_sort
algorithms << this.&selection_sort
algorithms << this.&quick_sort


def result = [:].withDefault{ 0 }
1000.times {
  def a = [*1..100].with{ Collections.shuffle(it); it.take(10) }
  def sorted = a.sort(false)
  println "a=$a"
  algorithms.each {
    distance = 0
    assert sorted == it(a.clone())
    result[it.method] += distance
  }
}
result.sort{ it.value }.each {
  println sprintf("%15s: %d", it.key, it.value)
}

結果はアルゴリズム間に距離の差がなかった。

     quick_sort: 22192
 selection_sort: 22310
    bubble_sort: 22336

 selection_sort: 22171
    bubble_sort: 22443
     quick_sort: 22586

    bubble_sort: 22055
     quick_sort: 22124
 selection_sort: 22287

彼が正しかったかはまだわからないが Bubble sort は現実世界では遅くはなかった。
しかも、交換を終えた場所から次の交換位置まで移動するコストを考えると Bubble sort の方が速そうだ。

その他の現実世界向けのソート

Wikipedia には現実世界の制約を利用したソートが4つ挙げられている

Bead sort
Simple pancake sort
Spaghetti (Poll) sort
Sorting networks

Bead sort と Pancake sort に関しては Rosetta Code にプログラムでの実装が載っている

Swap 距離が最短のソートは何なのか?

同じ疑問を持つ人がいた。

結局どれがいいのかわからない。

Sorting by Short Swaps

関係ありそうな気がする*1。

記憶にあるランダムアクセスの関連の話題

Java の Collections も RandomAccess かどうかで分岐していたような気がする。

終わりに

現実世界ではまだランダムアクセスが完成していないのでコンピュータ世界のアルゴリズムが必ずしも通用するわけではないことがわかった。
もしかすると、どこかの学校で並べ替えリレーなるものが行われていてカーソルが交換毎に先頭に戻らなければいけない場合に最適なアルゴリズムが考案されているかもしれない。

2012-02-22 追記

最終的な位置まで移動することは一緒なのでどのソートでも移動距離があまり変わらない。
微妙な違いは確率の問題で最終的な位置に移動するまでに要素を逆方向へ移動するロスが発生しているからだ。
例） [5,4,3,2,1] の場合

Selection sort では 1と5、2と4を交換するだけなのでロスは発生しない
Bubble sort では1回目の Bubbling のあと [4,3,2,1,5] となるので3と4が最終的な位置から遠ざかっている

例） [2,3,4,5,1] の場合

Selection sort では1回目の Swap の後 [1,3,4,5,2] となりロスが発生する

ロスが出来る限り発生しないようにするには最終的な位置を予め知っている必要があるのだろうか？

*1:vectorsort なるものの実装が検索しても見つからない