CombSort

なんか今日はTopCoderでTCOがあるらしくて、SRMのPracticeができない状態っぽい。 んで、まあアルゴリズムの勉強でもしようかと。

さて、世の中には不思議なソートがあります。 今回紹介いたしますのは、日本人にはたまらないあの「コンブ」を利用したソートです。 昆布のぬめりを利用して、効率的なソートが出来るのです。 それをCombSortといいます。

(画像は Wikipedia より)

んなわけないですね。

CombSort はコムソートと読んで、バブルソートを改良したアルゴリズムです。 思いの外有名だったりします。 (コンピュータ部の大会の問題でもシェーカソートと共に登場してたりする…）

Comb は髪の毛をとくあの「コーム」。くし。 まあバブルソートをちょいといじるだけでものすごく早くなるんで、 小学生のお友達からおじいちゃんおばあちゃんにも教えてあげましょう！

バブルソートはずっと隣のコ同士を比較して交換していくけど、こいつは違います。

まず、「受けとった配列の長さ÷1.3(小数点以下切捨て)」っていうなんとも奇妙な計算をします。 仮にこいつをgapと呼びます。 そして配列のi番目の要素とi番目からgap個離れたところの要素を比較していくわけです。 iは0から1ずつ増やしていって、i + gap が配列の末端まで届くと、 次は「gap <- gap / 1.3」なんてことをしてまた上から繰り返します。 こいつをgapが1になるまで繰り返すわけです。 gapが1になって、かつ一回も並べ替えが行われなければソートされているわけだから完成。 ってな寸法です。

とりあえずJavaでソースを書いたんで解説します。

public class TestComb{
  public static int[] 昆布ソート(int[] moto){
    int i, temp, flg, gap = moto.length;
    String result;
    while(true){    //(3)
      gap = (int)(gap / 1.3); //(4)
      if(gap == 0) gap = 1;   //(5)
      flg = 0;
      for(i = 0; i + gap < moto.length; i++){ //(6)
        if(moto[i] > moto[i+gap]){
          temp = moto[i];
          moto[i] = moto[i+gap];
          moto[i+gap] = temp;
          flg = 1;
        }
      }
      if(gap == 1 && flg == 0) break; //(7)
    }
    return moto;
  }
  public static void main(String[] args){
    int i,len = args.length;
    int[] i_args = new int[len];
    for(i = 0; i < len; i++)i_args[i] = Integer.parseInt(args[i]);  //(1)
    i_args = 昆布ソート(i_args);   //(2)
    for(i = 0; i < len; i++)System.out.print(i_args[i]+",");
  }
}

C:\Users\Yantene\Desktop>java TestComb 10 5 7 100 34 20 79

5,7,10,20,34,79,100,

• (1) mainメソッドが受けとった引数を全部 int 型に変換してi_argsに突っ込む。
• (2) 「昆布ソート」メソッドを呼び出す。
• (3) while のカッコ内にtrueを書いていつでも条件成立。乃ち無限ループ。
• (4) gapの値を1.3で割って int 型にしてgapに突っ込む。勝手に切り捨てられる。
• (5) ところがgapの値を1.3で割ったときに切り捨てられてその値が0になっていては困るんでその場合は1を入れる。(これに気づくのに大変だった(汗
• (6) i + gapがmoto配列の末端まで行くまでiを増やし続ける。iとi + gapを比較して昇順になってなかったら交換。 ここはバブルソートと変わらないですね。 (7) で今回のループで交換があったかどうかを知るために、 交換されたらflgを1にしておく。 あたりまえだけどループの上の方でflgを0に戻すようになってる。
• (7) gapが1で、1度も交換されていなければ、見事ソート完了。お疲れ様でした。