Quicksort- Klausuraufgabe 4

Moderator: AI 2

ratatam
Erstie
Erstie
Beiträge: 14
Registriert: 30. Apr 2014 16:35

Quicksort- Klausuraufgabe 4

Beitrag 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

m_flaig
Moderator
Moderator
Beiträge: 272
Registriert: 27. Sep 2009 14:02

Re: Quicksort- Klausuraufgabe 4

Beitrag 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

stackoverflow
Neuling
Neuling
Beiträge: 8
Registriert: 19. Jun 2014 15:15

Re: Quicksort- Klausuraufgabe 4

Beitrag 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?

Benutzeravatar
import java.noob
Windoof-User
Windoof-User
Beiträge: 25
Registriert: 2. Mär 2014 12:28

Re: Quicksort- Klausuraufgabe 4

Beitrag 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

stackoverflow
Neuling
Neuling
Beiträge: 8
Registriert: 19. Jun 2014 15:15

Re: Quicksort- Klausuraufgabe 4

Beitrag von stackoverflow »

Intuitiv hätte ich das auch so gemacht, aber mit der anderen Variante kommt man ebenso zum Ziel, daher die Frage.

Benutzeravatar
aDramaQueen
Mausschubser
Mausschubser
Beiträge: 84
Registriert: 10. Jan 2014 16:34

Re: Quicksort- Klausuraufgabe 4

Beitrag 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
Bild
...Never go full retard...

stackoverflow
Neuling
Neuling
Beiträge: 8
Registriert: 19. Jun 2014 15:15

Re: Quicksort- Klausuraufgabe 4

Beitrag 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...

Antworten

Zurück zu „AI 2“