単連結リストの整列 #85 基本選択法の問題点：安定性

前回示したように基本選択法は隣接交換法に比べて時間性能が随分よくなっている。
しかし、基本選択法には、問題にしなくていいのなら問題にならないが、
場合によっては困ったことになるようなある性質がある。

#include <stdio.h>
#include "intlist.h"

#define UNUSED_ARG(x) (void)(x)

static int issup(cintelem_t p, cintelem_t q, void *arg)
{
    UNUSED_ARG(arg);
    return intelem_get_val(p) > intelem_get_val(q);
}

static void print(intlist_t list)
{
    intiter_t i = intlist_iterator(list);
    while (intiter_has_next(i)) {
        cintelem_t e = intiter_next(i);
        printf("%d ", intelem_get_val(e));
    }
    intiter_dispose(i);
    putchar('\n');
}

int main(void)
{
    intlist_t list = intlist_new();
    intlist_add_first(list, 1);
    intlist_add_first(list, 2);
    intlist_add_first(list, 2);
    print(list);
    intlist_sort(list, issup, NULL);
    print(list);
    return 0;
}

整数値を持つ要素3個のリストを昇順に整列するプログラムである。
これを実行すると、

2 2 1
1 2 2

何の問題なく昇順に整列する。
しかし、リストの内容を表示する関数printの各要素の内容を表示するprintfを、

static void print(intlist_t list)
{
...snip
        printf("(%d, %p) ", intelem_get_val(e), e);
...snip
}

に変更して、基本選択法による実装をリンクすると、

(2, 003e3c80) (2, 003e3c70) (1, 003e3c60)
(1, 003e3c60) (2, 003e3c70) (2, 003e3c80)

各要素の二つ目の値は参照、つまりそれぞれの要素の識別子である。
昇順に整列した結果、整数値2を持つ要素二つのうち整列前にはリストの先頭にあった要素003e3c80が、
二つ目の要素003e3c70の後に移動しており、要素の順序が元から逆転している。
同じ順位を持つものが整列前後で同順序に、つまり、より前にあるものは変わらず前にある性質を整列の安定性という。
上の結果から分かるように基本選択法は安定でない整列法である。

このプログラムに隣接交換法の実装をリンクして実行すると、

(2, 003e3c80) (2, 003e3c70) (1, 003e3c60)
(1, 003e3c60) (2, 003e3c80) (2, 003e3c70)

要素003e3c80は整列前後で変わらず要素003e3c70の前に位置している。
隣接交換法は安定な整列法である。

解決したいものに整列の安定性が不要ならこれは気にしなくていい性質ではある。