ここから本文です

ソーティングアルゴリズムでO(n)を実現するもの。 問:1から1000までの間のn個...

アバター

ID非公開さん

2016/5/811:10:34

ソーティングアルゴリズムでO(n)を実現するもの。

問:1から1000までの間のn個の整数がランダムに存在する。これらをO(n)実行時間でソートするアルゴリズムをデザインしなさい。

という問題があるのですが、つまりこれは擬似コードを書けということだと思うのですが、ソートを外部記憶に頼らずに、また、すでにある程度ソート済みなどの仮定なしに、O(n)で実行する方法は存在しますか?どのようなものになるのでしょうか?
私は、データの状況にかかわらず基本的にO(nlogn)になるマージソートが高速なアルゴリズムだと思っていたのですが、ランダムに並んだn個の整数をO(n)でソートする方法はどのようなものになるのでしょうか?

基数ソートが検索結果にでたのですが、外部記憶を使うようなのでアウトとします。

閲覧数:
86
回答数:
2
お礼:
25枚

違反報告

ベストアンサーに選ばれた回答

ari********さん

編集あり2016/5/813:00:30

「Key の比較を伴うソートアルゴリズム」の計算量は最小で O(n・logn) になる事が証明されている。例えば クイックソート、ヒープソート、マージソート 等が当て嵌まる。

「Key の比較を伴わないソートアルゴリズム」例えば ビンソート、分布数え上げソート、基数ソート 等の計算量は O(n)。是れらは一般に「デジタルソート」と呼ばれる。

参考迄に。

アバター

質問した人からのコメント

2016/5/8 13:53:50

お二人様ありがとうございました。

どうやら、比較を伴わないというのがポイントのようですね!

ベストアンサー以外の回答

1〜1件/1件中

プロフィール画像

カテゴリマスター

man********さん

2016/5/813:06:45

値域が(1から1000)でw個の整数が連続した範囲の場合、
w個の度数分布表を数ええ上げる方法であれば、
データ数nがメモリに格納できない程度に多くても外部記憶を使わないで、
O(w*n)でソートできます。

http ://ideone. com/Agt3LE

でも、n=4でw=(1..31767)等、w>nの場合、早くはありません。

みんなで作る知恵袋 悩みや疑問、なんでも気軽にきいちゃおう!

Q&Aをキーワードで検索:

Yahoo! JAPANは、回答に記載された内容の信ぴょう性、正確性を保証しておりません。
お客様自身の責任と判断で、ご利用ください。
本文はここまでです このページの先頭へ

「追加する」ボタンを押してください。

閉じる

※知恵コレクションに追加された質問は選択されたID/ニックネームのMy知恵袋で確認できます。

不適切な投稿でないことを報告しました。

閉じる