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

Question

インタビューの質問ごとに、「テストで全体的なスコアに基づいて10億人の学生のリストをどのように並べ替えるのですか？ 1Bとマークの範囲は10-100です。 どのようなソートアルゴリズムも行いますが、効率的なアルゴリズムは何ですか？

Answer 1

入力にはcounting sortを単に実行します。この場合は、範囲が制限されているため、O(n)です。また、すべての生徒を出力する方法がΩ（n）であるため、最も効率的です。

利用可能なスコア（例えば、90の得点がある場合、生徒を90回ループする、スコア100の生徒を初めて出力する場合など）についてルーピングすることによって出力することができます。

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

O（n）余分なスペースでO（n）、O（n）余分なスペースでO（n）ですが、2番目の方法は2*nであるため、最初は90*nです。

Answer 2

カウントソートを使用します。あなたが最大値とこの問題で満足されるいくつかの他のパラメータを知っているのは良いことです。

Answer 3

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

O（k）時間を取る2つのループとO（n）を取る1つのループがあり、合計時間はO（n + k）です。これは、kがnより小さい場合に有効です。例えば。スコアで1,000,000,000人をソートするとします。 n = 1000000000、k = 100-10、したがって時間= O（n）。