シェルソートの順位性

質問

このカテゴリーのNo.137（#35189）の続きなのですが、シェルソートについてご存知の方お願いします。

　上記の質問にて、ヒープソートは完全二分割木型で、同一の値であってもその順序は保証されない、ということがわかりました。
　そこで、配列の内容をソートする処理をシェルソートで組んでみました。

　やろうとしているのは、n1、n2 の２つの配列に値を入れ、n1 が同じ値だったら n2 の値を使ってソートする、という処理です。
　しかし実際には、n3、n4と無制限に続く２次元配列なので各配列を個別にソートしなければならず、n2 を先にソートしてから n1 をソートする、という処理を入れています。
　ところがこれだと、n1 のソート時に同一の値の順序が崩れると、せっかく行った n2 のソートが無駄になってしまいます。

　シェルソートの場合、こういうことは起こるのでしょうか。
　よろしくお願いします。

回答No.1

alfeim · ベストアンサー

ソートには2種類あり、
安定なソート(キーになる値が同値の場合もとの順位が保証される)と
安定でないソートがあります(元の順位が保証されない)

安定なソートでないと多分上記の用件は満たせないでしょう
ソートのアルゴリズムについてはweb上で検索するなり、その手の書籍を買えば
色々載っているでしょう

シェルソートは安定ではないので同値の順位は崩れてしまいますので
安定なソートを使う必要があると思います

参考URLに各種ソートアルゴリズムのソースコードがあります

参考URL：

http://www.vector.co.jp/soft/data/prog/se002453.html

お礼

回答が遅くなりました。
　ありがとうございました。