Quicksort < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:01 Mo 31.01.2011 | | Autor: | bobbert |
| Aufgabe | | Sortieren Sie die Zahlenfolge 8 5 4 4 2 9 6 nach der Methode des Quicksort. Stellen Sie die Abeitsweise des Algortihmus dar, in dem Sie jeweils das Ergebnis eines rekursiven Durchlaufs in eine neue Zeile schreiben. Kreisen Sie das Pivotelement ein und markieren Sie die betrachtete Teilfolge. Notieren Sie außerdem neben der Zeile, welche Wlemente in der Zeile jeweils miteinander getauscht wurden. |
Ansatz:
[mm] \vmat{ & & &P & & \\8 &5 &4 &[u]4[/u]& 2 &9 &6\\i & & & & & &j} [/mm] //Pivot (P) frei nach Schnauze ausgewählt
[mm] \vmat{2& 5& 4& [u]4[/u]& 8& 9& 6\\ & i & & j& & &} [/mm] // Tausch : 2 , 8
[mm] \vmat{2& [u]4[/u]& 4& 5& 8& 9& 6\\ & i_j & & & & &} [/mm] //Tausch (T): 4 ,5 danach 4 mit sich selbst
[mm] \vmat{2 & [u]4[/u] \\i &j } [/mm] // [mm] \*^1) [/mm] Warum fängt der Algorithmus zuerst mit der linken Seite an und nicht der rechten?
[mm] \vmat{2 & [u]4[/u] \\ & i_j } [/mm] // T: 4 mit sich selbst
[mm] \vmat{ 5 &[u]8[/u]& 9& 6\\&i & &j} [/mm] //Pivot willkürlich gewählt
[mm] \vmat{ 5 & 6& 9& [u]8[/u] \\ & & i_j& } [/mm] //Tausch: 8, 6
[mm] \vmat{ 5& [u] 6[/u]} [/mm] //Tausch 6 mit sich selbst
[mm] \vmat{[u]9[/u] & 8 } //\*^2: [/mm] Wieso ist 8 nicht nach dem Prinzip des Algorithmus alleine? Natürlich würde dann 8 nicht in richtiger Reihenfolg sein. Dachte aber, dass das Array an der Überschneidungszahl (Ü) geteilt wird und Ü nicht in ein weiteres array gespeichert wird.
[mm] \vmat{8&[u]9[/u] } [/mm] //8 mit 9 fertig
Fragen: [mm] \*^1 [/mm] & [mm] \*^2 [/mm] (SIEHE OBEN)
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:14 Mo 31.01.2011 | | Autor: | felixf |
Moin!
> Sortieren Sie die Zahlenfolge 8 5 4 4 2 9 6 nach der
> Methode des Quicksort. Stellen Sie die Abeitsweise des
> Algortihmus dar, in dem Sie jeweils das Ergebnis eines
> rekursiven Durchlaufs in eine neue Zeile schreiben. Kreisen
> Sie das Pivotelement ein und markieren Sie die betrachtete
> Teilfolge. Notieren Sie außerdem neben der Zeile, welche
> Wlemente in der Zeile jeweils miteinander getauscht
> wurden.
> Ansatz:
>
>
> [mm]\vmat{ & & &P & & \\8 &5 &4 &[u]4[/u]& 2 &9 &6\\i & & & & & &j}[/mm]
> //Pivot (P) frei nach Schnauze ausgewählt
>
>
>
> [mm]\vmat{2& 5& 4& [u]4[/u]& 8& 9& 6\\ & i & & j& & &}[/mm] //
> Tausch : 2 , 8
>
> [mm]\vmat{2& [u]4[/u]& 4& 5& 8& 9& 6\\ & i_j & & & & &}[/mm]
> //Tausch (T): 4 ,5 danach 4 mit sich selbst
Kann es sein, dass das Pivotelement nachher die zweite Vier ist? Nach dem letzten Tauschen?
> [mm]\vmat{2 & [u]4[/u] \\i &j }[/mm] // [mm]\*^1)[/mm] Warum fängt der
> Algorithmus zuerst mit der linken Seite an und nicht der
> rechten?
Gegenfrage: warum nicht? Es ist doch voellig egal, welche Seite zuerst sortiert wird, da zwischen den beiden Seiten keine Interaktion mehr besteht.
Der Beispiel-Code auf Wikipedia faengt z.B. auch mit der linken Seite an.
> [mm]\vmat{2 & [u]4[/u] \\ & i_j }[/mm] // T: 4 mit sich selbst
>
> [mm]\vmat{ 5 &[u]8[/u]& 9& 6\\&i & &j}[/mm] //Pivot willkürlich gewählt
>
> [mm]\vmat{ 5 & 6& 9& [u]8[/u] \\ & & i_j& }[/mm] //Tausch: 8, 6
>
> [mm]\vmat{ 5& [u]6[/u]}[/mm] //Tausch 6 mit sich selbst
>
> [mm]\vmat{[u]9[/u] & 8 } //\*^2:[/mm] Wieso ist 8
> nicht nach dem Prinzip des Algorithmus alleine?
> Natürlich würde dann 8 nicht in richtiger Reihenfolg
> sein. Dachte aber, dass das Array an der
> Überschneidungszahl (Ü) geteilt wird und Ü nicht in ein
> weiteres array gespeichert wird.
Das ist schon etwas komisch, weil oben ja die zweite Vier weggelassen wurde.
Wie genau sieht der Pseudocode vom Algorithmus aus? Ohne den lassen sich hier nicht wirklich Aussagen treffen, und insbesondere kann man deine Frage so nicht beantworten.
LG Felix
|
|
|
|
