c - ページネーションによるソートアルゴリズム

Question

エントリのリストを並べ替えてから、その並べ替えられたリストのサブセット (ページ) を選択したいと考えています。例えば; 10.000 個のアイテムがあり、アイテムを 101 から 200 まで保持したいと考えています。単純なアプローチは、最初に 10.000 個のアイテムすべてを並べ替えてからページを選択することです。これは、項目 1 から 100 および 201 から 10.000 がすべて不必要に完全にソートされていることを意味します。ページ内のアイテムのみを完全にソートし、ページ内にないことが明らかになったエントリのそれ以上のソートを停止する既存のアルゴリズムはありますか? C のソース コードは素晴らしいですが、説明も問題ありません。

Answer 1

n の中から p から q までの項目が必要だとします。ソートには O(n·log n) の時間がかかりますが、あなたが言及した操作は、次のように O(n) 時間 (qp « n である限り) で実行できます: O(n)-time メソッドを適用して pᵗʰそしてqᵗʰ値。次に、時間 O(n+k) (k=qp の場合) または約 O(n) 時間で、p から q までの値を持つアイテムのみを選択し、それらのアイテムを時間 O(k・log k) (約 O) で並べ替えます。 (1)、k が O(1) の場合、正味時間 O(n) に対して。