単連結リストの整列 #69 比較／交換回数と要素数の関係

整列順と完全に逆順に並んでいる場合と既に整列させたい順序に並んでいる場合について、
整列処理時の比較と交換の回数とリストの要素数との関係を見てみる。

#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 intlist_t make_descending_list(int size)
{
    int i;
    intlist_t list = NULL;
    if (size >= 0 && (list = intlist_new()) != NULL) for (i = 1; i <= size; i++) intlist_add_first(list, i);
    return list;
}

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)
{
    int i;
    for (i = 0; i <= 10; i++) {
        intlist_t list = make_descending_list(i);
        printf("#n=%d\n", i);
        print(list);
        intlist_sort(list, issup, NULL);
        print(list);
        printf("#comparisons=%lu, #swaps=%lu\n", intlist_get_compare_counts(list), intlist_get_swap_counts(list));
        intlist_reset_counts(list);
        intlist_sort(list, issup, NULL);
        print(list);
        printf("#comparisons=%lu, #swaps=%lu\n", intlist_get_compare_counts(list), intlist_get_swap_counts(list));
        intlist_dispose(list);
    }
    return 0;
}

要素数を0個から10個まで変えて降順と昇順のリストを昇順に整列するようにしただけである。
整列結果はどの要素数でも正しかったので、要素の比較と交換の回数だけを示すと、

$ ./a.out | grep '^#'
#n=0
#comparisons=0, #swaps=0
#comparisons=0, #swaps=0
#n=1
#comparisons=0, #swaps=0
#comparisons=0, #swaps=0
#n=2
#comparisons=1, #swaps=1
#comparisons=1, #swaps=0
#n=3
#comparisons=3, #swaps=3
#comparisons=2, #swaps=0
#n=4
#comparisons=6, #swaps=6
#comparisons=3, #swaps=0
#n=5
#comparisons=10, #swaps=10
#comparisons=4, #swaps=0
#n=6
#comparisons=15, #swaps=15
#comparisons=5, #swaps=0
#n=7
#comparisons=21, #swaps=21
#comparisons=6, #swaps=0
#n=8
#comparisons=28, #swaps=28
#comparisons=7, #swaps=0
#n=9
#comparisons=36, #swaps=36
#comparisons=8, #swaps=0
#n=10
#comparisons=45, #swaps=45
#comparisons=9, #swaps=0

降順→昇順の最悪ケースでは要素数に対して比較・交換回数は回になっている。
昇順→昇順の最良ケースでは比較回数は回、交換は行われない。

変更前の既に整列が成っていても途中で処理を打ち切らないlistsortのバージョンで実行すると、

$ ./a.out | grep '^#'
#n=0
#comparisons=0, #swaps=0
#comparisons=0, #swaps=0
#n=1
#comparisons=0, #swaps=0
#comparisons=0, #swaps=0
#n=2
#comparisons=1, #swaps=1
#comparisons=1, #swaps=0
#n=3
#comparisons=3, #swaps=3
#comparisons=3, #swaps=0
#n=4
#comparisons=6, #swaps=6
#comparisons=6, #swaps=0
#n=5
#comparisons=10, #swaps=10
#comparisons=10, #swaps=0
#n=6
#comparisons=15, #swaps=15
#comparisons=15, #swaps=0
#n=7
#comparisons=21, #swaps=21
#comparisons=21, #swaps=0
#n=8
#comparisons=28, #swaps=28
#comparisons=28, #swaps=0
#n=9
#comparisons=36, #swaps=36
#comparisons=36, #swaps=0
#n=10
#comparisons=45, #swaps=45
#comparisons=45, #swaps=0

昇順→昇順でも比較は降順→昇順と同じ回数行われるが交換操作は行われない。