Sortierverfahren Quicksort (Handout zum Referat)

Sortierverfahren Quicksort (Handout zum )

1.) Allgemein

– rekursiver, nicht-stabiler Sortieralgorithmus (arbeitet nach dem Grundsatz Teile und herrsche)- durch C. Antony R. Hoare 1960 entwickelt

– beliebtes Sortierverfahren da in unzähligen verschiedenen Situationen einsetzbar

2.) Das Prinzip

– zu sortierende Menge wird in zwei Teilmengen aufgespaltet, die dann jede für sich sortiert werden- dabei: ausgehend von einem Mittelwert MW (dessen Bestimmung kann unterschiedlich sein!) werden alle Elemente kleiner dem MW links, und alle Elemente größer dem MW, rechts angeordnet

– dies erfolgt immer wieder solange, bis alle Elemente in sortierter Reihenfolge vorliegen

Zahlenbeispiel aus Internet:

(siehe Downloaddatei)

3. Vor- und Nachteile

+ schnelles und effizientes Sortierverfahren

+ kann mit jeder Programmiersprache ausgeführt werden

+ durch Rekursivstruktur leicht zu implementieren+ keinen zusätzlichen Speicher benötigt- ineffizient bei vorsortierten und inversen (umgekehrten) Reihenfolgen

4. Struktogramm zum gemeinsamen ergänzen

(siehe Downloaddatei)Quellen:

http://www.computer-woerterbuch.de/?id=suchen&comDB=woerterbuch&suchen=Quicksort

http://www.it-academy.cc/article/1063/Sortier+und+Suchalgorithmen.html

http://de.wikipedia.org/wiki/Quicksort

Struktogramm von:http://www.schule.de/schulen/oszhdl/gymnasium/faecher/informatik/sort-such/bilder/quicksort.gif