In Place randomisierten Auswahlalgorithmus

Question

Wir studieren derzeit Algorithmen daher habe ich diese Frage als "Hausaufgaben" markiert, obwohl dies keine Hausaufgabe ist. Nur um sicher zu sein.

Wir haben gerade den Zufallsauswahlalgorithmus untersucht, und die Logik scheint einfach zu sein. Wählen Sie ein Element aus einer Liste und platzieren Sie das Element dann an der richtigen Stelle. Wiederholen Sie den Vorgang dann in einer Unterliste, bis das Element am Index an seiner Stelle ist. Wobei index die Position des gewünschten Elements in der Sortierliste ist.

Dies sollte eine modifizierte Version des schnellen Sortieralgorithmus sein. Aber wir sortieren nur eine Unterliste, nicht beide Unterlisten. Daher ein Leistungsschub (in Big-Oh).

ich diesen Algorithmus mit externen Speichern erfolgreich implementieren kann (C++, und Null basierte Arrays):

int r_select2(vector<int>& list, int i) 
{ 
    int p = list[0]; 

    vector<int> left, right; 

    for (int k = 1; k < list.size(); ++k) 
    { 
     if (list[k] < p) left.push_back(list[k]); 
     else  right.push_back(list[k]); 
    } 

    int j = left.size(); 

    if (j > i) p = r_select2(left, i); 
    else if (j < i) p = r_select2(right, i - j - 1); 

    return p; 
} 

Allerdings mag ich den Algorithmus in-situ (in-place) implementieren und nicht verwenden zusätzliche Sub-Arrays. Ich glaube, dass dies eine einfache/triviale Aufgabe sein sollte. Aber irgendwo läuft meine In-situ-Version falsch. Vielleicht ist es einfach zu spät und ich muss schlafen, aber ich kann die Ursache nicht, warum die folgende Version fehlschlägt:

int r_select(vector<int>& list, int begin, int end, int i) 
{ 
    i = i + begin; 
    int p = list[begin]; 

    if (begin < end) 
    { 
     int j = begin; 
     for (int k = begin + 1; k < end; ++k) 
     { 
     if (list[k] < p) 
     { 
      ++j; 
      swap(list[j], list[k]); 
     } 
     } 

     swap(list[begin], list[j]); 

     if (j > i) p = r_select(list, begin, j, i); 
     else if (j < i) p = r_select(list, j + 1, end, i - j); 
    } 

    return p; 
} 

In beiden Beispielen ist das erste Element als Drehpunkt verwendet wird, um das Design zu halten einfach. In beiden Beispielen ist i der Index des gewünschten Elements.

Irgendwelche Ideen, wo das 2. Beispiel versagt? Ist das ein einfacher Fehler?

Danke euch allen!

Answer 1

Das klingt fischig:

i = i + begin; 
... 
r_select(list, begin, j, i);