1サイクルでCで配列をソートする方法は？

フロート数の配列を1サイクルでソートする方法はありますか？1サイクルでCで配列をソートする方法は？

出典

2010-12-06 Pupkov-Zadnij

「1サイクル」とは何ですか？ – birryree

「ワンパスで」という意味ですか？ – ruslik

ここで意図した意味が配列を1回通過するかどうか、つまりO（n）かどうか疑問に思っています。 –

チェックNは、入力配列のサイズであり、Mは、その上にクイックソートプログラムとラップトップを取るソート配列サイズ

出典

2010-12-06 18:13:39 matcheek

入力配列に浮動小数点が含まれている場合、どのようにソート配列を作成できますか？ – AShelly

@AShelly ...無限のテープを与えました... :-) –

質問から浮動小数点の部分を逃しましたが、浮動小数点型の基数ソートを取ると、浮動小数点数のソート配列の作成方法がわかります、http://stackoverflow.com/questions/2685035/is-there-a-good-radixsort-implementation-for-floats-in-c – matcheek

1回のパスを意味する場合は、いいえ。ソートには一般にO（N log N）が必要です。シングルパスはO（N）を意味します。

基数ソートでは、平均キー長kでO（N * k）をとります。線形時間であっても、複数のパスが必要です。また、通常はフロートのソートには適していません。

出典

2010-12-06 18:02:28

基数ソートはどうですか？ – Andrey

@Andrey浮動小数点で追加情報なし？ – ruslik

比較ベースのソートアルゴリズムではO（N log N）時間が必要です – matcheek

ベストケースではO（n）のソートアルゴリズムがいくつかあります。 hereを参照してください。

出典

2010-12-06 18:05:20 mkb

ベスト・ケースではO（n）のソート・アルゴリズムを設計するのは簡単ですが、最良のケースは「配列がすでにソートされているとき」であり、ソートされているかどうかをチェックして実行し、その上で別のソートアルゴリズムを実行します。最良のケース分析はめったに興味深いものではありません。ヴォルテールが言うように、「すべての可能な世界の中で最高」 –

ライプニッツはヴォルテールではなくそう言った。 –

いいえ、O（n）アルゴリズムはありません。あなたのアレイに要素があるか、量子コンピュータを使っているかのように多くの並列コンピュータを使用している可能性がありますが、通常のコンピュータでO（n）を使用したい場合は、忘れてしまいます。

出典

2010-12-06 18:08:31 darioo

であることがOで実行Counting sort （N + M）の時間。その後、ラップトップを一輪車に乗せてください。タダ！ 1サイクルでソート。

出典

2010-12-06 19:02:37 redtuna

+1（ポイント）と面白い答えを得るために。 –

号

<aside> @codinghorror：なぜ私の記事は> = 15個の文字を持っている必要がありますか？ </aside>

出典

2010-12-06 20:55:01

落札を説明するコメントはいいですね.... –

1サイクルでCで配列をソートする方法は？

答えて

関連する問題