PDA

View Full Version : [FRAGE] - das pivotelement ist nicht immer die letzte Stelle oder?

Heavy
16-04-2002, 15:23
Ja ich weiss die Frage ist blöd, aber ich hab bis jetzt noch nie eine Folge gesehen, bei der das Pivotelement z.B. genau in der Mitte vorkommt.
Wie soll ich die Folge sortieren, wenn genau dieser Fall auftritt?

z.B. 9 0 5 8 2 6 3 1 4 2, da kann ich die letzte Stelle nicht als Pivot wählen.


Original geschrieben von eXe
das pivotelement ist doch frei wählbar hängt von der implementierung ab ob mittleres letztes oder sonst eines

wieso sollte 2 da nicht als pivotelement gehen?

edit: z.B. dann halt diese Folge 9 0 5 8 2 6 3 2 4 1

oder noch fieser: 9 8 7 6 5 4 3 2 1
eXe
16-04-2002, 15:26
das pivotelement ist doch frei wählbar hängt von der implementierung ab ob mittleres letztes oder sonst eines

wieso sollte 2 da nicht als pivotelement gehen?
Heavy
16-04-2002, 16:56
Heeelp bin am Verzweifeln!!! :(

9 0 5 8 2 6 3 2 4 1 p=4
2 0 5 8 2 6 3 9 4 1
2 0 3 8 2 6 5 9 4 1
2 0 3 2 8 6 5 9 4 1
2 0 3 2 4 6 5 9 8 1
-----------------------------------

2 0 3 2 p=2
2 0 3 2
--------------------------------------
________6 5 9 p=9??

Und wie geht's weiter? :confused:
MrBurnst
16-04-2002, 17:19
muss da ganz links nicht ein "stop"element (kleinstes Element) stehen? habe nämlich genau das gleiche problem bei <7, 1012, 13, 128, 5, 4711, 34> ...
Jeff_Mills
16-04-2002, 17:24
ja b-börnst
es muss ein stop-element<min von 1-i A[i]
ganz links stehen damit der algo funkt
Jeff_Mills
16-04-2002, 17:25
stopp-Element X < min 1-i von A[i]
X ist kleiner als das Minimum des Arrays A[]
jeuneS2
16-04-2002, 17:31
man könnte auch die Indexgrenzen überprüfen...
eXe
16-04-2002, 22:15
ach das lag das problem sorry nicht gecheckt :)

@jeuneS2: jo das hab ich mir auch mal überlegt warum das nicht so gemacht wird ;)
ded
16-04-2002, 22:39
@jeuneS2: ist viel mehr Aufwand, bei jedem Durchlauf auf die Grenzen zu überprüfen, als einfach das Stoppelement einzubauen.

@Jeff_Mills: Die Wahl des Stoppelements kommt auf die Implementation des Quicksorts an. Wenn man eine Quicksortimplementierung mit:
Zeile 5: >=
Zeile 8: <
Zeile 9: <
Zeile 12: >= (oder >, ist egal)
verwendet, muß daß Stoppelement natürlich < dem Minimum sein und nicht nur <=.
Nur wenn man eine Implementation mit:
Zeile 5: >=
Zeile 8: <=
Zeile 9: <
Zeile 12: >=
verwendet, reicht es, wenn das Stoppelement <= dem Minimum ist.