-PR-
解決済み

シェルソートの順位性

  • 暇なときにでも
  • 質問No.35464
  • 閲覧数146
  • ありがとう数1
  • 気になる数0
  • 回答数1
  • コメント数0

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

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

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

 シェルソートの場合、こういうことは起こるのでしょうか。
 よろしくお願いします。 
通報する
  • 回答数1
  • 気になる
    質問をブックマークします。
    マイページでまとめて確認できます。

質問者が選んだベストアンサー

  • 回答No.1
レベル11

ベストアンサー率 58% (114/195)

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

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

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

参考URLに各種ソートアルゴリズムのソースコードがあります
お礼コメント
noname#25358

 回答が遅くなりました。
 ありがとうございました。
投稿日時 - 2001-02-14 16:44:09
関連するQ&A
-PR-
-PR-
このQ&Aのテーマ
このQ&Aで解決しましたか?
関連するQ&A
-PR-
-PR-
こんな書き方もあるよ!この情報は知ってる?あなたの知識を教えて!
このQ&Aにはまだコメントがありません。
あなたの思ったこと、知っていることをここにコメントしてみましょう。

その他の関連するQ&A、テーマをキーワードで探す

キーワードでQ&A、テーマを検索する
-PR-
-PR-
-PR-

特集


新大学生・新社会人のパソコンの悩みを解決!

いま みんなが気になるQ&A

関連するQ&A

-PR-

ピックアップ

-PR-
ページ先頭へ