ビジュアルプログラミング(23) - エレファント・ビジュアライザー調査記録

偶置換・奇置換(1)

Blocklyでブロックを繋げるときに何も選択しなくてもよい例を考えてみます。

「群論の計算(9) - エレファント・コンピューティング調査報告」や「エレファントな線形代数(5) - エレファント・コンピューティング調査報告」で取り上げた、置換が偶置換なのか奇置換なのかを調べることを考えます。この記事の中では「バブルソート」と書きましたが、プログラムを書くことができて、それが正しく動作することが言えれば、置換が偶置換なのか奇置換なのかわかると言えます。よってプログラムを作る際には普通に作ることができます。

一般的定義がよくわからないので、ここでは、何個の要素の置換なのか(サイズと呼ぶことにします)に基づいた方法を「選択ソート」、逆順になっている組の数に基づいた方法を「バブルソート」と呼ぶことにします。

「選択ソート」(TyprScript)は以下のようになります。

var count: number = 0;
function exchange(list: number[], i: number, j: number): void {
    count++;
    var tmp: number = list[i];
    list[i] = list[j];
    list[j] = tmp;
}
function selection_sort(list: number[]): void {
    for (var i = 0; i < list.length - 1; i++) {
        for (var j = i + 1; j < list.length; j++) {
            if (list[i] > list[j]) {
                exchange(list, i, j);
            }
        }
    }
}

count が偶数ならば偶置換、奇数ならば奇置換となります。元のリストが決まれば count は決まります。また、繰り返しの回数はサイズで決まるので、繰り返しは有限回で終了します。よって任意の置換は偶置換または奇置換となります。

「バブルソート」(TyprScript)は以下のようになります。

var count: number = 0;
function exchange(list: number[], i: number, j: number): void {
    count++;
    var tmp: number = list[i];
    list[i] = list[j];
    list[j] = tmp;
}
function bubble_sort(list: number[]): void {
    for (; ;) {
        for (var i = 0; i < list.length - 1; i++) {
            if (list[i] > list[i + 1]) {
                break;
            }
        }
        if (i < list.length - 1) {
            exchange(list, i, i + 1);
        } else {
            break;
        }
    }
}