最新閲覧日:

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

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

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

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

このQ&Aに関連する最新のQ&A

A 回答 (1件)

ソートには2種類あり、


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

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

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

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

参考URL:http://www.vector.co.jp/soft/data/prog/se002453. …
    • good
    • 0
この回答へのお礼

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

お礼日時:2001/02/14 16:44

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!


人気Q&Aランキング

おすすめ情報