Tutorial: Sortier-Algorithmen I+II

[Daniel]

Hallo,

bei der Partitionierung geht es ja darum, sich ein Element aus der Datenmenge zu greifen und anschliessend die Datenmenge so zu sortieren, dass alle Elemente, die kleiner als das gewählte Element sind, links davon liegen und alle Elemente, die grösser als das gewählte Element sind, rechts davon liegen.

Der Quicksort arbeitet um so effizienter, je näher das gewählte Elemente an der Mitte der Datenmenge liegt.

Wenn Du nur ein einzelnes Element herausgreifst und wir mal davon ausgehen, dass Du eine unsortierte Datenmenge vorliegen hast, so ist es völlig unerheblich, welches Element Du herausgreifst. Die Wahrscheinlichkeit ein geeignetes Element zu finden, ist für das erste, letzte und mittlere Element gleich gross.

Eine Technik, den Vorgang zu optimieren, wäre der "Median von Dreien", nach der Du Dir drei Elemente herausgreifst und deren mittleres Element auswählst.


Grüße,
Daniel