初心者のためのアルゴリズムのソート

Question

.NetとJavaは、ソートアルゴリズムを学ぶのに「必要」ではないと私を台無しにしましたが、今では、この贅沢を持たない別の言語で配列をソートする必要があります。私は小さな問題でバブルのソートを拾うことができました。しかし、いくつかの情報源は、n^2比較の平均的および最悪のシナリオでは恐ろしいパフォーマンスのため、バブルソートの使用を嫌う。バブルの並べ替えは仕事を完成させるようですが、要素数が+100,000の配列に取り組むことについては、この程度でパフォーマンスが問題になる可能性があると私は心配しています。もう一方では、他のアルゴリズムのいくつかは複雑さの点でかなり威圧的です。私の質問は、パフォーマンスの点でバブルのソートにはどのような良いフォローアップがありますが、実装上は複雑な荒廃地には進まないでしょうか？

私は、CS専攻ではなく、必要に応じてプログラムを分析するアナリストです。言うまでもありませんが、私はまだプログラミングの専門知識に満ちています。ありがとう:)

Answer 1

many optionsがあり、それぞれ独自のトレードオフがあります。あなたが発見したように、Bubble Sortのトレードオフは（a）シンプルですが、（b）遠隔の大きな配列でさえ遅いことです。

• Quicksortは良いですが、メモリの問題が発生する可能性があります。
• 私はHeapsortを大いに成功させましたが、安定していることは保証されていません（問題は一度もありませんでしたが）。
• Bogosortは、実装するのは楽しいですが、話はしていますが、全く実用的ではありません。ソートするデータの良い理解を持っ
• のように...

は、1つの最適なアルゴリズムを決めるのに役立ちます。例：

• アレイの大きさはどのくらいですか？
• すでにソートされているか、部分的にソートされている可能性はありますか？
• 配列にはどのような種類のデータが含まれていますか？
• 配列内の2つの要素を比較するのはどれくらい難しく、費用がかかりますか？
• 配列がソートされているかどうかを判断するのはどれくらい難しいのですか？
• のように...

は、他のすべてのよりはましだ誰ソートアルゴリズムはありません。あなたのニーズに合ったものを選ぶことは、時間をかけて練習して拾うものです。

Answer 2

クイックソートを学ぶために時間をかけてください、それは素晴らしいアルゴリズムであり、あなたが遅くなると複雑ではありません。

足を濡らすだけのソートアルゴリズムが必要な場合は、挿入ソートと選択ソートをお勧めします。バブルソートよりも一般的に優れており、理解して実装が簡単です。マージソートは、アルゴリズムコースでも一般的です。あなたはクイックソートのはるかに良い使用します。

また、安定していないソートの違いを理解しておく必要があります。安定したソートでは、同じキーを持つアイテムの順序は変更されませんが、非安定のソートは変更されません。