algorithm - クイックソートを使用してK個の最小値を見つける方法

Question

すべての値を並べ替えて最初の K 値を選択すれば、問題は簡単です。しかし、配列全体がソートされる前に最小の K 値がソートされている可能性があるため、時間がかかりすぎます。この問題を解決するには、コードにフラグを追加する方法があると思いますが、最小の k 値がソートされたかどうかを判断するフラグの付け方がわかりません。

Answer 1

ランダム選択アルゴリズムを使用して、この問題を O(n) 時間で解決できます。最後に、0 から k までの部分配列を返すだけです。

Answer 2

k番目に小さい値を見つけることで問題を解決できると思います。partitionクイックソートの関数のシグネチャが であると仮定するとint partition(int* array, int start, int end)、基本的な考え方を示す疑似コードは次のとおりです。

int select(int[] a, int start, int end, int k)
{
    j = partition(a,start,end);

    if( k == j)
        return a[j];
    if( k < j )
        select(a,start,j-1,k);
    if( k > j )
        select(a,j+1,end,k-j);
}

index = select(a, 0, length_of_a, k);

次に、a[0...index] は、配列 a の最初の k 個の最小値です。並べ替えたい場合は、[0...index] をさらに並べ替えることができます。