algorithm - 10 億人の学生のリストを並べ替える

Question

インタビューごとの質問で、「10 億人の生徒のリストを、テストの総合得点に基づいてどのように並べ替えますか?」と尋ねられました。生徒の動きのロール番号は 1 ～ 1B で、マークの範囲は 10 ～ 100 です。 ." どのソートアルゴリズムでも実行できますが、効率的なアルゴリズムは何でしょうか?

Answer 1

この場合は、範囲が制限されているため、入力に対してカウントソートを実行するだけです。O(n)また、すべての生徒を出力するには Ω(n) が必要になるため、最も効率的な方法です。

利用可能なスコアをループすることにより、学生を出力できます (たとえば、90 の可能なスコアが存在する場合、学生を 90 回ループし、最初の出力ではスコア 100 の学生を....)。

このタスクは、バケット ソートで実行できます。ただし、最初に入力をループして、学生数に関連する各スコアを見つけ、その後、学生数を考慮して各スコアのバケットを作成し、次にバケットを埋める必要があります。バケットの配列を作成する必要があることに注意してください。各バケットに現在のアイテム数を保存する追加のパラメーター。

最初のアプローチ (並べ替えを直接使用する) は O(n) で O(1) の余分なスペースがあり、2 番目のアプローチは O(n) で O(n) の余分なスペースがありますが、2 番目のアプローチは で2*nあり、最初のアプローチは です90*n。

Answer 2

ある種の分割統治アルゴリズム (マージ ソート、クイック ソート、バケット ソートなど) を使用し、このアイデアを使用してソートを複数のバケットに分割します。すべてのデータをマージして大きな配列に戻す必要がある場合に問題が発生しますが、サブ配列は既にソートされているため、O(n) しかかかりません。

bucket sort(L)
{
list Y[k+1]
for (i = 0; i <= k; i++) Y[i] = empty
while L nonempty
{
    let X = first record in L
    move X to Y[key(X)]
}
for (i = 0; i <= k; i++)
concatenate Y[i] onto end of L
}

O(k) 時間かかる 2 つのループと O(n) かかる 1 つのループがあるので、合計時間は O(n+k) です。これは、k が n より小さい場合に適しています。たとえば、1,000,000,000 人をスコアで並べ替えたいとします。n=1000000000、k=100-10 なので、時間 = O(n) です。