Seite 1 von 1

Quicksort- Klausuraufgabe 4

Verfasst: 1. Sep 2014 14:11
von ratatam
Hallo,

falls in Aufgabe 4 der Klausur am Donnerstag eine Folge mit dem Quicksort-Algorithmus sortiert werden soll- auf welche Implementierung des Algorithmus sollen wir uns dann stützen?
In der Musterlösung von Übung 9 wird der Pivotwert mithilfe von Random() erzeugt (im Gegensatz zu alternativen Implementierungen, in denen etwa immer der Wert des Indexes in der Mitte der aktuellen Folge als Pivotwert dient). Um aber zu einem gegebenem Zeitpunkt den Zustand der Folge zeichnen zu können, muss meiner Meinung nach der Pivotwert für alle vorhergehenden und den momentanten Schritt bekannt bzw. erschließbar sein.

Grüße

Re: Quicksort- Klausuraufgabe 4

Verfasst: 1. Sep 2014 15:41
von m_flaig
Hallo,

sollte dies der Fall sein, so steht detailliert die Vorgehensweise dabei. Im Zweifelsfall halten Sie sich immer an die Implementation, wie sie in der Vorlesung vorgestellt wurde.

Viele Grüße

Re: Quicksort- Klausuraufgabe 4

Verfasst: 3. Sep 2014 11:27
von stackoverflow
Hallo,
mir ist bei der QuickSort (in-place) noch nicht ganz klar, nach welchen Kriterien die Werte an den Indizes i1/i2/i3 getauscht werden sollen. Aus den Folien bzw. dem Video geht das so hervor, dass i1 immer dann getauscht werden muss, wenn der Wert höher als der Pivot-Wert ist - soweit klar. Aber mit welchem anderen Index-Wert wird getauscht? Mit dem erstbesten, der kleiner ist, auch wenn der eigentlich gar nicht in den Arrayteil gehört? Ich versuch das mal an einem Beispiel deutlich zu machen; es gibt folgendes Array mit den Index-Pointern (in senkrechter Reihenfolge):

9 (i1)
1
0
6 (i2)
2 (i3)
4
7

Der Pivot Wert sei p=4

Im ersten Durchlauf ist S[i1] > p, also muss getauscht werden. Jetzt aber mit der 6 an i2 (die dann im falschen Teilarray wäre) oder schaut sich der Algorithmus in dem Fall auch noch i3 an und tauscht die 9 mit der 2, die ja eigentlich die passende Zahl wäre?
Also kurz gesagt: Nimmt der Algorithmus die erstbeste kleinere Zahl oder nur eine passende kleinere Zahl?

Re: Quicksort- Klausuraufgabe 4

Verfasst: 3. Sep 2014 12:59
von import java.noob
Hi,

also ich würde wie folgt vorgehen
9 i1
1
0
6 i2
2 i3
4
7

9 > 4 = > I1 und I3 werden getauscht

2 i1
1
0
6 i2
9 i3
4
7

2 < 4 & 1 < 4 & 0<4 = > i1 = i1 +3

2
1
0 i1
6 i2
9 i3
4
7

Und dann mit i3 weitermachen =>9>4 i3 = i3 + 1 4=4 i2 = i2 +1 (Und hier kann man jetzt aufhören da i2 und i1 das Ende erreicht haben, ansonsten könnte man
noch mit i3 weitermachen bis er am Ende ist)

2
1
0 i1
4 i2
9 i3
6
7

Quicksort auf (2,1,0) und auf (9,6,7) und fertig

0124679

Re: Quicksort- Klausuraufgabe 4

Verfasst: 3. Sep 2014 13:26
von stackoverflow
Intuitiv hätte ich das auch so gemacht, aber mit der anderen Variante kommt man ebenso zum Ziel, daher die Frage.

Re: Quicksort- Klausuraufgabe 4

Verfasst: 3. Sep 2014 13:49
von aDramaQueen
Das ist zum Schluss dir überlassen, also eine Design-Entscheidungen. In dem Video zu Quicksort (in-place) gab's auch so ne Situation.
i1 hatte den Pivot, i2 einen Wert der zu groß war und i3 einen der zu klein war. Jetzt haste 2 Möglichkeiten die gleich gut sind:

1.) du tauschst i1 & i2 womit i2 dann vollständig wäre (so hat's auch das Video gemacht)
2.) du tauschst i1 & i3 womit dann i1 vollständig wäre

Re: Quicksort- Klausuraufgabe 4

Verfasst: 3. Sep 2014 15:00
von stackoverflow
Okay, wenn es nur um das Resultat geht ist es natürlich egal, wie man es macht :) .
Sofern dann nicht in der Aufgabe steht "Zeichnen Sie die Liste nach dem 4. Durchlauf" oder sowas. Da müsste man schon wissen, wie man genau vorgehen muss...