qsortは一貫性のある比較を要求しますか、それともシャッフルに使用できますか？

Question

更新：悪い考えでこれを提出してください。あなたは人生で何も無料では得られません。そして、確かに証拠です。シンプルな考えが悪かった。それは間違いなく、しかし、学ぶものです。

レイジープログラミングの課題。 50-50がqsortの比較関数に対してtrueまたはfalseを返す関数を渡すと、3行のコードを書く構造体の配列を効果的にソートできないと思います。

int main (int argc, char **argv) 
{ 
    srand(time(NULL)); /* 1 */ 
    ... 
    /* qsort(....) */  /* 2 */ 
} 

...

int comp_nums(const int *num1, const int *num2) 
{ 
    float frand = 
      (float) (rand())/((float) (RAND_MAX+1.0)); /* 3 */ 

    if (frand >= 0.5f) 
     return GREATER_THAN; 
    return LESS_THAN; 
} 

私が探すために必要な任意の落とし穴？スワップすることで行数を減らすことは可能ですか？これは3つの単純でない行の中で最もきれいですか？

Answer 1

悪い考え。私は本当に悪いことを意味する。

あなたのソリューションは、予測不可能結果、ないランダム結果を与え、大きな違いがあります。ランダム比較を行うqソートが何をするのか、またすべての組み合わせが同じようになるかどうかは、実際には分かりません。これはシャッフルにとって最も重要な基準です。すべての組み合わせが同じようになるはずです。バイアスされた結果は大きな問題に等しい。あなたの例でそれを証明する方法はありません。

Fisher-Yates shuffle（別名クヌスシャッフル）を実装する必要があります。

Answer 2

ランドはそこで最もランダムなものではありません...カードや何かをシャッフルしたい場合は、これは最善ではありません。またKnuthシャッフルは速くなりますが、ループが永久にループしない場合はあなたの解答はOKです

Answer 3

いいえ、これは配列を適切にシャッフルしません。指数分布で要素を元の位置にほとんど移動させません。

Answer 4

比較関数は、負の数、正の数、または0を返すと想定されています。qsort()は、どちらの引数が大きいかを判断するために使用します。

Answer 5

他の回答に加えて、これは遅すぎるため、単純なフィッシャー・イェイツのシャッフルよりも悪いです。 qsortアルゴリズムはO（n * log（n））、Fisher-YatesはO（n）です。

いくつかの詳細は、「シャッフル」のこの種は、一般的に働くだけでなく、the Fisher-Yates methodしない理由についてウィキペディアで提供されています：

他のシャッフル のアルゴリズムとの比較

フィッシャーイエーツshuffleがありますかなり 効率的です。確かに、その漸近時間 と空間の複雑さが最適です。 高品質の非公開 乱数ソースと組み合わせると、 も保証されています。 の結果が保証されています。いくつかの他の ソリューションに比べて、それはまた、得られた 順列の一部のみが必要な場合、それは、必要に応じて増分順列 を生成 を が途中で停止し、あるいは を停止して繰り返し再起動することができる、という利点 を有します。ハイレベルで高速 と プログラミング言語はビルトインアルゴリズムをソート、各要素セットの をシャッフルする 代替方法は、 乱数を割り当てられ、セットは、その後 これらの数に応じてソートされ 漸近的時間の複雑さ（O（n log n） 対O（n））が悪化しているにもかかわらず、実際にはより速くなる可能性がある[引用 が必要]。 Fisher-Yates シャッフルのように、正しく が実装されていれば、 の偏りのない結果も生成され、ランダムな の数字にバイアスのある種の が許容される可能性があります。ただし、 番号が重複しないように注意する必要があります。 ソートアルゴリズムは一般的に タイの場合には 要素をランダムに並べ替えないため、 を割り当てる必要があります。 ユーザー指定の比較関数でソートサポート言語 の一部の使用を見ている上記方法 の変異体は ランダムな値を返す 比較関数でそれをソートしてリストをシャッフルする あります。しかし、これは は常に動作しません。多くの場合、ソートアルゴリズムである が使用されており、 の結果は の内部で の実装で非対称になります。

この

は hereにリンク：

ちょうどもう一つのことを私は方法の様々な バージョンで実験し、元のバージョン に 1つのより多くの欠陥を発見し、この 記事を書いている間（私が名前を変更〜shuffle_sort）。私が言ったとき、私は 間違っていた「それがうまく シャッフル配列にそれが と呼ばれるたびに返されます。」

結果がうまく すべてでシャッフルされていません。彼らは偏っている。ひどく。それは、 は、要素のいくつかの順列（すなわち、 の順序）が他のものより である可能性が高いことを意味します。ここで再び ニュースグループの議論から借り、それを証明する コードの別のスニペットは、です：

N = 100000 
A = %w(a b c) 
Score = Hash.new { |h, k| h[k] = 0 } 
N.times do 
    sorted = A.shuffle 
    Score[sorted.join("")] += 1 
end 

Score.keys.sort.each do |key| 
    puts "#{key}: #{Score[key]}" 
end 

3つの 要素のこのコード シャッフル10万回の配列：A、B、Cおよびレコードがどのように多くの 回のそれぞれの可能な結果は に達しました。この場合は、 の6つの発注があり、 はそれぞれ約16666.66回になるはずです。 なら、私たちはshuffle （shuffleまたはshuffle_sort_by）の公平なバージョンを試してみてください予想通り、 結果は以下のとおりです。もちろん

 
abc: 16517 
acb: 16893 
bac: 16584 
bca: 16568 
cab: 16476 
cba: 16962 

、いくつかの偏差が があるが、彼らは 超えるべきではありません の数パーセントは期待値であり、このコードを実行するたびに異なる である必要があります。 分布は であると言えます。

OKshuffle_sortメソッドを使用するとどうなりますか？

 
abc: 44278 
acb: 7462 
bac: 7538 
bca: 3710 
cab: 3698 
cba: 33314 

これは、すべての均一な分布 ではありません。再び？

これは、ソート方法がどのように偏っているかを示しており、これがなぜそうであるかを詳しく説明しています。最後に彼はCoding Horrorにリンク：

のが正しい クヌース・フィッシャーイエーツシャッフルアルゴリズムを見てみましょう。

for (int i = cards.Length - 1; i > 0; i--) 
{ 
    int n = rand.Next(i + 1); 
    Swap(ref cards[i], ref cards[n]); 
} 

あなたは違いを参照していますか？私は 初めてそれを逃した。

 
Naïve shuffle Knuth-Fisher-Yates shuffle 
rand.Next(3); rand.Next(3); 
rand.Next(3); rand.Next(2); 
rand.Next(3); 

素朴なシャッフル3^3で 結果（27）の可能なデッキ 組み合わせ：3カードデッキのためのスワップ の比較。それは 数学は実際には があることを私たちに教えてくれるので、奇妙です！または可能な6つのカードデッキの の組み合わせ。 KFYシャッフルでは、最初に の注文から始めて、3番目のカードと交換してから、 の残りの2枚のカードをもう一度 と交換します。

Answer 6

The Old New Thing私はランダムに（それはOの平均値（nは* n個を記録しますダウン途中で再帰的に設定し、最大がうまくいく途中で結果を連結し、パーティションの基本的な考え方だと思います。この1

になります）バイナリの決定とそれはlog2（fact（n））に近いですが、q-sortはランダムな述語でそれを行うことは確かではありません。 （n * log n）ソート戦略