Quicksort Problem

[phr33k]

Hallo,
ich stehe gerade vor einem kleinem Problem mit dem Quicksort Sortieralgorithmus...

Wenn ich ein Array habe:
10, 5, 3, 8, 1, 11, 13, 4, 15
und 1 als Pivot nehme wie wird dann sortiert?

Normalerweise wird ja von links geguckt, was größer 1 ist und von rechts geguckt, was kleiner 1 ist und dann getauscht. Aber wie gehe ich vor, wenn mein Pivotelement dummerweise die kleinste Zahl des gegeben Arrays ist?

Viele Grüße
Phr33k

 

[SlaterB]

dann ist die linke Hälfte leer und die rechte enthält n-1 Elemente,

das ist in etwa der bekannte 'Worst Case' für Quicksort,
der Algorithmus sollte aber auch dann noch funktionieren

Quicksort ? Wikipedia

 

[phr33k]

Das ergibt dann Sinn... Unser toller Lehrer hat das immer so erklärt, dass die Länge der linken und der rechten Teilliste fest ist. Dann hätte ich das oben beschriebene Problem. Danke!