私はランキングのセットを含む1D配列を持っています。例えばスコアに基づく並べ替え
0 | 0
1 | 2
2 | 2
3 | 1
4 | 0
5 | 1
（ここで示した第一列は配列インデックスである）
私はこのようにランクを付けたいです
1 | 2
2 | 2
3 | 1
5 | 1
0 | 0
4 |インデックスがタイがある場合、数値の昇順にとどまることが0
注意。これを行うにはどのようなアルゴリズムを検討すべきですか？
他のポスターが答えてきたように、あなたはおそらく安定したソートをしたいです。安定ソートアルゴリズムは、私が選択したことだった場合、それは最高の複雑さを持っているので、私はおそらくマージソートとなるだろう
が含まれます。挿入の並べ替えは、しかし、小さなリストでそれを打つことができます。私はバブルソートがひどいわけではないが、それが何であるか忘れているケースが1つあることを読んで覚えています。
しかし、安定性を心配すると、指定されていない言語がソート関数で使用するアルゴリズムであるかもしれないquicksortのようなアルゴリズムが除外されます。
どのような言語を使用していても、ソートの実装では、2つのアイテムを比較し、どちらが「より大きい」かを確認する関数を使用できます。だから、あなたが本当にする必要があるすべては、ランクが等しい場合、ランクが等しくない場合は大きい数値indiceを持つアイテムは、「大きい」
これは、言語に付属するソートアルゴリズムを使用して項目を辞書順に並べ替えているだけで、同じインデックスを持つ2つの項目が等しいと見なすことができると仮定して安定性を不要にします。
この関数の正確なプロトコルは、言語によって異なります。
+1最も完全 – BlackBear
ありがとう素敵な答え。私はJavaを使用して、どの実装が使用されているのか調べました。これはmergesortと思われます。 –
+1。 「バブルソートがひどいものではないケースが1つあることを読んで覚えています。リストが既にソートされている場合は、バブルソートが最良のアルゴリズムです。 –
あなたが探しているのは「安定」ソートアルゴリズムです。これは、等価として比較される要素の順序を変更しないアルゴリズムです。あなたは、使用している言語やツールセットについては言及していないので、具体的に何を使用するかを教えてもらえません。不安定性は、いくつかのアルゴリズムの固有の特徴であり、他のものは、安定した形態または不安定な形態のいずれかで実施することができる。一般に、ライブラリソートアルゴリズムは、可能であれば安定した実装を選択します。
最後の文章が正しくありません。安定性は、一般に、ソーリングアルゴリズムの関数である。 mergesortは安定していて、クイックソートはそうではありません。 – aaronasterling
私はそれを明確にするために書きました。 – divegeek
それがどのように効率的で良い知っているが、しないでください。
// suppose you have scores[n]
for c1 = 1 to n
for c2 = c1 + 1 to n
if scores[c2]>scores[c1] then swap them
うーん..その安定性は重要ですか？
ランキングでソートされていませんか？
データにrankの横に他の属性がある場合は、その属性を比較操作に含める方がよいでしょう。
安定した並べ替えでは、複雑さが増しながら不必要なパフォーマンスの低下を招く可能性があります。
これは、汎用アルゴリズムよりも言語固有の問題です。 – marcog