algorithm - バイナリ配列のクイックソート

Question

最悪の場合、 Quicksort で size のバイナリ配列をソートする必要がある比較の数を知りたいですn。
この問題の最悪のケースが何かわかりません。[0 1 0 1 0 1..]?
乾杯、
えお

Answer 1

正確にはクイックソートではありませんが、バイナリ配列をソートしたい場合は、O(n) で実行できます。1 と 0 の数を数えてから、好きな順序で書きます。

たとえば、次の配列の場合:

[0 1 0 1 0 1 1]

3 つの 0 と 4 つの 1 があることを O(n) で数えることができます。次に、配列を最初に 3 つの 0 で書き直し、次に 4 つの 1 で書き直します。

Answer 2

少数の一意のキーで構成される配列の並べ替えは、実際には一般的です。一意のキーの数が O(1) の場合、O(n) 回に適応するアルゴリズムが必要です。あなたの場合、一意のキーは2つだけです。

QuickSort は平均で O(nlogn) ですが、最悪の場合は O(n^2) です。あなたのケースでは、この配列 [ 0 1 1 0 1 0 1 0 0 0 1 0 1 ]でクイックソート アルゴリズムをテストしました。配列の長さは13要素であり、アルゴリズムは170これをソートするために反復を行います。配列ですn^2。

そして、O(n) アルゴリズムのこの擬似コード:

let n0 <- 0;
for i=0  to lenght(A)
    if A[i] == 0
        A[n0] = 0;
        ++n0

for i=n0 to lenght(A)
    A[i] = 1