| | |
| Titel: | Sortieralgorithmen | |
| Startseite english | ||
| ||
| |<< Anfang < Zurück Index Weiter > Ende >>| | |  |
Quick Sort (Sortieren durch Zerlegen)
Beschreibung
- Das Verfahren arbeitet nach dem Divide & Conquer-Prinzip.
- Aus einer zu sortierenden Teilfolge wird ein Element ausgewählt.
- Die Folge wird so umsortiert, daß das ausgewählte Element an seine insgesamt (bezogen auf den Sortiervorgang der vollständigen Datenfolge) richtige endgültige Position zu liegen kommt.
- Nach dem Umordnen dürfen links vom ausgewählten Element nur mehr kleinere Elemente stehen und rechts nur mehr größere.
- Dann wird für die Folgen links und rechts vom ausgewählten Element das Verfahren rekursiv aufgerufen.
- Das korrekte Umordnen wird dadurch erreicht, daß von links her Elemente gesucht werden, die in die rechte Hälfte gehören, und von rechts her solche, die in die linke Hälfte gehören. Dann werden diese falsch plazierten Elemente vertauscht. Das Umordnen endet, wenn die beiden Suchvorgänge an der endgültigen Position des ausgewählten Elements zusammenstoßen.
Programmcode
procedure QuickSort ( var f : TArray;
HighIndex : integer ) : string;
procedure rQuickSort ( links,
rechts : integer);
// rekursiver Teil des
QuickSorts
// Als Trennelement wird das
jeweils mittlere Element der Teilfolge ausgewählt.
var i, j, x :
integer;
begin
if links <
rechts
then
begin
i :=
links;
j :=
rechts;
x := f[(i+j) div 2];
// Wert des Trennelements
repeat
while f[i] < x do
inc(i);
while f[j] > x do
dec(j);
if i < j then swap
(f[i], f[j]);
until i >=
j;
rQuickSort (links, j-1
);
rQuickSort (j+1 ,
rechts);
end;
end; //
rQuicksort
begin //
QuickSort
rQuickSort (0,
HighIndex);
end; //
QuickSort
Zurück zu Themenseiten:
StudyPaper.com/Startseite/Computer/Informatik
StudyPaper.com/Startseite/Wissenschaft/Wirtschaftswissenschaften
StudyPaper.com/Startseite
Das Setzen von Verweisen (Links) auf diese Seite ist gestattet und bedarf keine vorherige Absprache.
