私は特定の比較関数でソートされた文字列のリストを持っています。ほぼ完全にソートされたリストを再ソートするのに最適なソートアルゴリズムはどれですか？
異なる比較機能を使用してこのリストを並べ替える必要があります。
この新しい比較関数は、たとえばUmlautsのような特定の特殊文字を比較するときにわずかに異なります。ほとんどの場合、正しい位置に到達するには、要素を1つまたは2つのスロットだけ移動する必要があります。
どのソートアルゴリズムが、このほぼ完全にソートされたリストをランタイム実行速度に関して再ソートするのに最適ですか？
Insertion sortは、小規模またはほぼソートされたリストでうまく機能します。このACM Paperから
：リスト長 と小さなsortedness比の 様々な組み合わせのランダムに生成されたリストの
テストは 示していることをストレート挿入小さなまたは非常に近いソートされたリスト とそのための一種である最高 Quickersortは他の場合は が最適です。ウィキ物品Insertion sortから
：
入力アレイが既にソートされている場合、 挿入ソートが与えられた場合、したがって挿入 ソートより効率的に、わずかN-1として 比較を実行するには またはソート"ほぼソートされた"配列。 SO
QuickerSortはQuickSortではありませんが、類似しています。最近の用語では、QuickerortはQuickSortの変種とみなされ、短いサブセットを最初にソートし（再帰のスタック深度を最小限に抑える）、単純なパーティション選択基準を持ち、おそらく最悪の場合のパフォーマンスが悪い可能性がありますが、ここで議論されているほぼソートされたケース。 –
また、バブルソートと同じです http://en.wikipedia.org/wiki/Bubble_sort – Max
@Max：実際はありません（@Henkと私は短時間前にこのディスラクションを受けました）。 BubbleSortは、通常、開発者が大学からそれを覚えていて、単純ではあるが（挿入の並べ替えよりはるかに簡単ではない）、一般的なソートのように思われ、少数のランダムに注文された項目でテストすると高速です。特定のシナリオで挿入ソートが選択されています。 –
両方の検索操作へのアクセスをお持ちですか？そうであれば、最初のソート処理中にハッシュツリーを構築し、それを他のソート操作に使用することができます。
あなたのデータリストはすべて並べ替えられています（アスキー/国別文字セット順）特定の国に適用されます。例えば、ドイツとそのウムラウト
は、新しいアイテムを挿入されていませんウィキペディア
でGermanic_umlautを参照してください、あなたは少しより厳格なソートルールによってそれらを訴えるしたいです。あなたがここに
http://www.softpanorama.org/Algorithms/Sorting/bubblesort.shtml
バブルソートは、わずか数の順列で出回っソートリストにうまく機能、たとえば読むことができるよう
。これはバブルソートのような音で始まり、良いアルゴリズムです。また、バブルソートは「安定」ソートアルゴリズムであることにも注意してください。これは、シナリオにとって重要なことです。
ほぼソートされたリストでは、Combのバリエーションがクイックソートよりも優れています。私は、櫛の並べ替えが挿入の並べ替えとどのように比較されるかを調べるためのテストは行っていません。
あなたは本当に*アルゴリズム*か、ちょうどヒューリスティックを探していますか？ –
これはアルゴリズムです... –
[どのソートアルゴリズムが大部分のソートされたデータで最もうまくいくのですか？]（http://stackoverflow.com/questions/220044/which-sort-algorithm-works-best-on-mostly-並べ替えられたデータ） – nawfal