安定なソートかを調べる関数

(前提知識)
参考文献(アルゴリズムとデータ構造)によれば、安定なソートとは、ソート判定において同一であると判断された入力データの順序が、ソート後も変わらないソートアルゴリズムのことを言う(そうだ)。

■安定なソート
(入力データ)
山田(57才) 上田(18才) 磯野(27才) 吉田(18才) 水野(41才)
    ↓
  [年齢でソート]
    ↓
(出力データ)
上田(18才) 吉田(18才) 磯野(27才) 水野(41才) 山田(57才)

入力データで、上田→吉田の順番になっているが、出力でもこの順番が崩れていない。

■非安定なソート
(入力データ)
山田(57才) 上田(18才) 磯野(27才) 吉田(18才) 水野(41才)
    ↓
  [年齢でソート]
    ↓
(出力データ)
吉田(18才) 上田(18才) 磯野(27才) 水野(41才) 山田(57才)

入力データで、上田→吉田の順番になっているのが、出力では吉田→上田の順番になっている。

安定ソートチェック関数を作る

『アルゴリズムとデータ構造』によると、以下のような安定ソートチェック関数の擬似コードがあります。

P.71より転載。

isStable(in, out)
  for i = 1 to N-1
    for j = i+1 to N
      for a = 1 to N-1
        for b = a+1 to N
          if in[i]とout[j]の数字が等しい && in[i]==out[b] && in[j]==out[a]
            feturn false
return true

しかし、変数iと変数bでループしている部分は、i=1(あるいはa=1)ではなく、i=0(あるいはa=0)と、0から始まるのが正解ではないかと思うのです。

なぜなら、1始まりだと以下のような第1要素と第2要素が非安定になった場合に、判定できないからです。

それを確かめるために、前記擬似コードをPythonで書いてみました。

〜コーディング中〜

参考文献

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

Pythonプログラミング物語 © 2016 Frontier Theme