コムソート

コムソート（）やコームソートや櫛（くし）ソートは、ソートのアルゴリズムの一つ。1980年に Włodzimierz Dobosiewicz が発表し、1991年に Stephen Lacey と Richard Box が再発見しコムソートと命名した。
バブルソートの改良版。内部ソートだが、安定ソートではない。実行速度は、ほぼO(n log n)になる。
アルゴリズム.
挿入ソートをシェルソートに改良したときと同様の改良を施す。適当な間隔で整列後、間隔を少しずつ狭めて整列していく。
Javaによる実装例.
public static void combSort(int[] data) {
 int h = data.length * 10 / 13;
 while (true) {
 int swaps = 0;
 for (int i = 0; i + h < data.length; ++i) {
 if (data[i] > data[i + h]) {
 swap(data, i, i + h);
 ++swaps;
 if (h == 1) {
 if (swaps == 0) {
 break;
 } else {
 h = h * 10 / 13;
private static void swap(int[] a, int i, int j) {
 int t = a[i];
 a[i] = a[j];
 a[j] = t;
C言語による実装例.
void comb_sort(int* array, int size) {
 int h = size;
 bool is_swapped = false;
 while (h > 1 || is_swapped) {
 if (h > 1) {
 h = (h * 10) / 13;
 is_swapped = false;
 for (int i = 0; i < size - h; ++i) {
 if (array[i] > array[i + h]) {
 // swap
 int temp = array[i];
 array[i] = array[i + h];
 array[i + h] = temp;
 is_swapped = true;
動作例.
動作例として
という数列を昇順に整列してみる。
このとき n=8 だから h=8÷1.3≒6 から始める。
8と2、4と1を比較して2回交換を行う。
次は h = 6÷1.3 ≒ 4。2と6、1と5のように比較してゆき、7と4のみが交換される。
以下 h は 3 → 2 → 1 の順に減っていくので
h=3：交換なし
h=2：交換なし
h=1：交換3回
この例では6回の交換で整列が終了した。
改良版アルゴリズム.
h=9,10となったとき、強制的にh=11とすることで高速化したアルゴリズムを、Comb sort 11と呼ぶ。
hが9→6→4→3→2→1や10→7→5→3→2→1と遷移するよりも、11→8→6→4→3→2→1と遷移する方がうまく櫛が梳けるためである。