Quicksort Median of Three

Question

Muss auf das Array = { 2 1 6 3 9 7 0 -2 10 } Quicksort mit Median of Three anwenden. Bei mir würde das Array im nächsten Schritt so aussehen { 2 1 0 -2 3 9 7 6 10 9}.

Die Lösung soll aber so aussehen { -2 1 0 2 9 7 6 3 10}.

Das versteh ich nicht ganz, wenn ich von 2 3 10 das Mittel nehme, bekomme ich 3 zurück. Die 3 wird an die letzte Stelle im Array getauscht und in Partition als Pivot  ausgewählt, da Partition bei uns so definiert ist. Median ist bei uns Anfang + Ende / 2 (abgerundet), also Position von 3.

Answer 1

Anfang + Ende / 2

0 + 8 / 2 = 4

Alternativ: (1 + 9)/2 = 5

In beiden Fällen ist 9 das Element, das in deine Median-of-Three-Berechnung einfließt.

Comments

Wie die 9 hier wieder in die Mitte kommt ist mir nicht klar, da 10 und 9 vertauscht werden, bevor Partition darauf angewendet wird. Bei mir wird dann zum Schluss die 9 mit der 10 vertauscht. Das ergibt folgendes Array (2, 1, 6, 3, 7, 0, -2, 9, 10) nach dem ersten Partition Aufruf.