---
title: CombSort
tags: [日記, 競技プログラミング, アルゴリズム]
publishedOn: 2010-07-11
lastModifiedOn: 2010-07-11
---

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

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

![](./Kelp_in_Neskowin.jpg)
(画像は Wikipedia より)

んなわけないですね。

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

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

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

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

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

```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度も交換されていなければ、見事ソート完了。お疲れ様でした。