Verständnis eines median-Algorithmus Auswahl?

Ich bin derzeit lernen algorithmen in meiner Freizeit, aber habe folgende Frage während des Studiums Kapitel 3 wählen Sie () - algorithmen.

Ich verstehe, dass ich kann verwenden Sie die select () - Algorithmus zu finden, der median Anzahl (n/2-th kleinste Zahl) wenn ich mit einem array aus n zahlen.

1), aber dies ist das bit, die ich bin kämpfen, um Sie zu verstehen. Ein = [3, 7, 5, 1, 4, 2, 6, 2]. nehme an, dass das array. was ist Inhalt des Arrays nach jedem Aufruf von Partition(), und die Parameter in jedem rekursiven Aufruf von Select().

kann jemand erklären, wie arbeiten Sie dieses bitte heraus?

nachfolgend ist der pseudo-code für die 2-algorithmen.

Select(A, p, r, k) {
    /* return k-th smallest number in A[p..r] */
    if (p==r) return A[p] /* base case */
    q := Partition(A,p,r)
    len := q – p + 1
    if (k == len) return A[q]
    else if (k<len) return Select(A,p,q-1,k)
    else return Select(A,q+1,r,k-len)
}

und der zweite code ist

Partition(A, p, r) { /* partition A[p..r] */
    x := A[r] /* pivot */
    i := p-1
    for j := p to r-1 {
        if (A[j] <= x) {
            i++
            swap(A[i], A[j])
        }
    }
    swap(A[i+1], A[r])
    return i+1
}

Dem Buch, das ich verwende, ist aufgerufen Die Ableitung von Algorithmen von Anne Kaldewaij.

InformationsquelleAutor | 2012-03-05

10

Dieser Algorithmus arbeitet in zwei Schritten. Die Partitionierung Schritt funktioniert durch abnehmen einige pivot-element, dann die Neuordnung der Elemente des Arrays, so dass alles, was kleiner als der pivot ist an der einen Seite, alles, was größer als das pivot ist auf der anderen Seite, und der Drehpunkt ist an der richtigen Stelle. Zum Beispiel bei einem array
```
3  2  5  1  4
```
Wenn wir Holen ein pivot 3, dann könnten wir die partition-array wie dieses:
```
2  1  3  5  4
+--+  ^  +--+
 ^    |    ^
 |    |    +--- Elements greater than 3
 |    +-------- 3, in the right place
 +------------- Elements less than 3
```
Beachten Sie, dass wir noch nicht sortiert das array haben, haben wir es einfach gemacht, es näher an, die sortiert wird. Dies ist übrigens der erste Schritt in quicksort.

Der Algorithmus dann die folgende Logik verwendet. Angenommen, wir möchten zu finden das element, das gehört auf den index k im sortierten Reihenfolge (die kth kleinste element). Dann, in Bezug auf den Drehpunkt, die wir ausgesucht haben, gibt es drei Möglichkeiten:
1. Der pivot an der position k. Dann, da der Drehpunkt ist an der richtigen Stelle, der Wert, den wir suchen, müssen Sie die pivot. Sind wir fertig.
2. Der pivot an der position größer als k sein. Dann die kth kleinste element muss in dem Teil des array vor dem pivot -, so können wir rekursiv suchen, die Teil eines Arrays, für die kth kleinste element.
3. Der pivot an der position kleiner als k sein. Dann die kth kleinste element muss irgendwo in der oberen region des Arrays, und wir können den Parameter recurse gibt.
In unserem Fall, nehmen wir an, wir wollen die zweit-kleinste element (das man an position 2). Da der Drehpunkt endete an position 3, das bedeutet, dass die zweit-kleinste element muss irgendwo in der ersten Hälfte des Arrays, so würden wir recurse auf dem subarray
```
2  1
```
Wenn wir wollten, dass der tatsächliche median-element, da der Drehpunkt landete genau in der Mitte des Arrays, wir würden nur die Ausgabe, dass der median ist 3 und getan werden.

Schließlich, wenn wir wollten, so etwas wie die vierte-kleinste element, dann ist da der Drehpunkt ist vor der position 4, wir würden recurse auf der oberen Hälfte des Arrays, nämlich
```
5  4
```
und würde mich für die erste kleinste element hier, da gibt es drei Elemente, bevor dieser region.

Den rest des Algorithmus sind die details, wie die Partitionierung in Schritt (was wahrscheinlich die meisten beteiligten Teil des Algorithmus) und wie die drei-Wege-Entscheidung, ob recurse oder nicht (ein bisschen weniger schwierig). Hoffentlich, obwohl, dieses high-level-Struktur hilft der Algorithmus mehr Sinn machen.

Hoffe, das hilft!
- vielen Dank dafür, ich habe es gerade gelesen und es ist einfacher zu verstehen als das Buch. Ich habe noch eine Frage und zwar, Wenn A in umgekehrter Reihenfolge sortiert, d.h. A = [- n, n,-1, ..., 2, 1], wie viele rekursive Aufrufe von Select() gemacht wird?
- Ich überlasse dies als übung ^_^, aber als Tipp, Hinweis, dass der Algorithmus nimmt das erste element des array als pivot-jedes mal. Wo ist das verschieben des pivot? In welcher Reihenfolge werden die restlichen Elemente bis zu Ende gehen? Auch als ein Hinweis, darüber nachzudenken, was quicksort hier machst.
- Ersten Satz von Punkt #3, ich denke du meinst "pivot an der position kleiner als k".
- Jetzt denke ich, dass beide #2 und #3 falsch sind... 🙂
- Ihr Punkt #2 sagt "pivot kleiner ist als k". Der folgende Satz sagt dann muss das Ziel sein, bevor die pivot. Sollte nicht das Ziel sein, nachdem die pivot? Gleiche Problem mit #3 aber in umgekehrter Richtung.
- D ' Oh! Mein schlechtes. Lassen Sie mich korrigieren. Vielen Dank für hartnäckig zu sein. 🙂
- Das ist, warum ich gerade std::nth_element und vermeiden Sie die Erstellung meiner eigenen Fehler.
InformationsquelleAutor templatetypedef

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.