質問: このカテゴリーのNo.137(#35189)の続きなのですが、シェルソートについてご存知の方お願いします。 上記の質問にて、ヒープソートは完全二分割木型で、同一の値であってもその順序は保証されない、ということがわかりました。 そこで、配列の内容をソートする処理をシェルソートで組んでみました。 やろうとしているのは、n1、n2 の2つの配列に値を入れ、n1 が同じ値だったら n2 の値を使ってソートする、という処理です。 しかし実際には、n3、n4と無制限に続く2次元配列なので各配列を個別にソートしなければならず、n2 を先にソートしてから n1 をソートする、という処理を入れています。 ところがこれだと、n1 のソート時に同一の値の順序が崩れると、せっかく行った n2 のソートが無駄になってしまいます。 シェルソートの場合、こういうことは起こるのでしょうか。 よろしくお願いします。
回答: ソートには2種類あり、 安定なソート(キーになる値が同値の場合もとの順位が保証される)と 安定でないソートがあります(元の順位が保証されない) 安定なソートでないと多分上記の用件は満たせないでしょう ソートのアルゴリズムについてはweb上で検索するなり、その手の書籍を買えば 色々載っているでしょう シェルソートは安定ではないので同値の順位は崩れてしまいますので 安定なソートを使う必要があると思います 参考URLに各種ソートアルゴリズムのソースコードがあります 参考URL: