すのものの「風変わりなソートアルゴリズム（15 パズルに関連）」

これは，バブルソートに似たアルゴリズムである。しかし，一つの余分な操作を加えなければ，ソートアルゴリズムにならない。バブルソートよりも効率はよくない。しかし，15 パズルを解くための，やや実践的なアルゴリズムを与える。

int 型の配列 a[0], a[1], ..., a[N-1] を非・減少順にソートする例で示す。

アルゴリズム：もしも i ≥ 2 であり "a[i-2] > a[i] または a[i-1] > a[i]" が成り立つ i があれば， a[i] に二つの元 a[i-2] と a[i-1] を飛び越させる。

この操作は次のコードで実現できる。

    if (a[i-2] > a[i] || a[i-1] > a[i]) {
        int tmp = a[i];

        a[i] = a[i-1], a[i-1] = a[i-2], a[i-2] = tmp;
    }

よく知られているように，配列 a[ ] の 転倒数 inv は次のコードで計算される。

    int inv = 0;

    for (j = 1; j < N; j++) {
        for (i = 0; i < j; i++) {
            if (a[i] > a[j]) {
                inv++;
            }
        }
    }

転倒数は次のコードでも計算できる。

    int inv2 = 0;

    for (j = 1; j < N; j++) {
        n = 0;
        for (i = 0; i < j; i++) {
            if (a[i] > a[j]) {
                n++;
            }
        }
        inv2 += n;
    }

上の操作は転倒数を増加させない。もしも a[ ] が 0, 1, 2, ..., N-1 の並び替えならば，上の操作は転倒数 modulo 2 を変えない。よって，ソートアルゴリズムではない。

定義：配列 a[ ] の 三つ組転倒数 trinv は次のコードで計算される。

    int trinv = 0;

    for (k = 2; k < N; k++) {
        for (j = 1; j < k; j++) {
            for (i = 0; i < j; i++) {
                if (a[i] <= a[k] && a[j] > a[k] || a[i] > a[k] && a[j] <= a[k]) {
                    trinv++;
                }
            }
        }
    }

三つ組転倒数は次のコードでも計算できる。

    int trinv = 0;

    for (k = 2; k < N; k++) {
        int less_equal = 0;
        int greater = 0;

        for (j = 0; j < k; j++) {
            if (a[j] <= a[k]) {
                less_equal++;
            } else {
                greater++;
            }
        }
        trinv += less_equal * greater;
    }

以上をテストするサンプルプログラムである。配列は rand() 関数で初期化される。種は現在時刻である。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 32

int a[N];

int main() {
    int i, j, k, n;
    int inv, inv2, trinv, trinv2;

    srand((unsigned)time(NULL));
    for (i = 0; i < N; i++) {
        a[i] = rand() % 16;
    }

    for (i = 0; i < N; i++) {
        printf("%x", a[i]);
    }
    putchar('\n');

    inv = 0;
    for (j = 1; j < N; j++) {
        for (i = 0; i < j; i++) {
            if (a[i] > a[j]) {
                inv++;
            }
        }
    }
    printf("%d ", inv);

    inv2 = 0;
    for (j = 1; j < N; j++) {
        n = 0;
        for (i = 0; i < j; i++) {
            if (a[i] > a[j]) {
                n++;
            }
        }
        inv2 += n;
    }
    printf("%d ", inv2);

    trinv = 0;
    for (k = 2; k < N; k++) {
        for (j = 1; j < k; j++) {
            for (i = 0; i < j; i++) {
                if (a[i] <= a[k] && a[j] > a[k] || a[i] > a[k] && a[j] <= a[k]) {
                    trinv++;
                }
            }
        }
    }
    printf("%d ", trinv);

    trinv2 = 0;
    for (k = 2; k < N; k++) {
        int less_equal = 0;
        int greater = 0;

        for (j = 0; j < k; j++) {
            if (a[j] <= a[k]) {
                less_equal++;
            } else {
                greater++;
            }
        }
        trinv2 += less_equal * greater;
    }
    printf("%d ", trinv2);
    putchar('\n');
}

命題：もしも上の操作が転倒数を減らさないなら，三つ組転倒数が減る。

証明：二つの場合がある。 (i) a[i-2] < a[i] && a[i-1] > a[i] と (ii) a[i-2] > a[i] && a[i-1] < a[i] である。

ケース (i). 次のように置く。

S_le = # {j | j < i-2 かつ a[j] ≤ a[i-2]},
S_gt = # {j | j < i-2 かつ a[j] > a[i-2]},
M_le = # {j | j < i-2 かつ a[j] ≤ a[i]},
M_gt = # {j | j < i-2 かつ a[j] > a[i]},
L_le = # {j | j < i-2 かつ a[j] ≤ a[i-1]},
L_gt = # {j | j < i-2 かつ a[j] > a[i-1]}.

三つ組転倒数の第二の定義を思い出そう。三つの元 a[i-2], a[i-1], a[i] の三つ組転倒数への寄与は次のようになる：

S_le * S_gt + (M_le + 1) * (M_gt + 1) + (L_le + 1) * L_gt.

操作後は次のようになる：

S_le * (S_gt + 1) + M_le * M_gt + (L_le + 2) * L_gt.

「操作後」-「操作前」は - S_le + M_le + M_gt + 1 - L_gt になる。 M_le + M_gt は j-3 に等しく S_le + L_gt は j-3 以下である。ゆえに，これは正である。

ケース (ii). 次のように置く。

S_le = # {j | j < i-2 かつ a[j] ≤ a[i-1]},
S_gt = # {j | j < i-2 かつ a[j] > a[i-1]},
M_le = # {j | j < i-2 かつ a[j] ≤ a[i]},
M_gt = # {j | j < i-2 かつ a[j] > a[i]},
L_le = # {j | j < i-2 かつ a[j] ≤ a[i-2]},
L_gt = # {j | j < i-2 かつ a[j] > a[i-2]}.

三つの元 a[i-2], a[i-1], a[i] の三つ組転倒数への寄与は次のようになる：

S_le * (S_gt + 1) + (M_le + 1) * (M_gt + 1) + L_le * L_gt.

操作後は次のようになる：

S_le * (S_gt + 2) + M_le * M_gt + (L_le + 1) * L_gt.

あとはケース (i) と同じである。［証明終］

ゆえに，上の操作は転倒数か三つ組転倒数を減少させる。よって，上の操作は永遠には続かない。もしも転倒数が正なら，上の操作をおこなうことができる。ただし，転倒数が 1 であり a[0] > a[1] の場合を除く。

次は，このソートのサンプルプログラムである。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 64

int a[N];

int main() {
    int i, j, k, n;
    int inv, trinv;

    srand((unsigned)time(NULL));
    for (i = 0; i < N; i++) {
        a[i] = rand() % 16;
    }

    while (1) {
        inv = 0;
        for (j = 1; j < N; j++) {
            for (i = 0; i < j; i++) {
                if (a[i] > a[j]) {
                    inv++;
                }
            }
        }

        trinv = 0;
        for (k = 2; k < N; k++) {
            for (j = 1; j < k; j++) {
                for (i = 0; i < j; i++) {
                    if (a[i] <= a[k] && a[j] > a[k] || a[i] > a[k] && a[j] <= a[k]) {
                        trinv++;
                    }
                }
            }
        }

        printf("inv. %5d: 3inv. %5d: ", inv, trinv);
        for (i = 0; i < N; i++) {
            printf("%x", a[i]);
        }
        putchar('\n');

        for (i = N - 1; i >= 2; i--) {
            if (a[i-2] > a[i] || a[i-1] > a[i]) {
                int tmp = a[i];

                a[i] = a[i-1], a[i-1] = a[i-2], a[i-2] = tmp; break;  /* for */
            }
        }
        if (i == 1) {
            break;      /* while */
        }
    }
}

15 パズルとの関連については，「すのものの「15 パズル（およびその拡張）を解く」」を見られたい。

すのもの