Schulzeux.de > Informatik

Quicksort Referat

Inhaltsverzeichnis

Referat zum Sortierverfahren QUICKSORT.

1. Allgemein Quicksort

= (von engl. quick – schnell, to sort – sortieren) ist ein schneller, rekursiver, nicht-stabiler Sortieralgorithmus, der nach dem Prinzip Teile und herrsche (engl. Divide and conquer) arbeitet.

Er wurde 1960 von C. Antony R. Hoare in seiner Grundform entwickelt und seitdem von vielen Forschern verbessert.

Der Algorithmus hat den Vorteil, dass er über eine sehr kurze innere Schleife verfügt (was die Ausführungsgeschwindigkeit stark erhöht) und zudem ohne zusätzlichen Speicherplatz auskommt. (mehr bei 3.)

2. Prinzipvon Quicksort

Quicksort ist ein etwas komplexerer Algorithmus der nicht so einfach zu verstehen ist.
Das erste was man wissen sollte ist, das Quicksort ein rekursiver Sortieralgorithmus ist.
Das heißt der Sortieralgorithmus ruft sich selber immer wieder mit neuen Parametern auf.

Bei Quicksort wird als 1. aus einer gegeben Zahlenmenge ein Mittelwert bestimmt (muss nicht in Mitte; oftmals beim prog. 1. Element; am besten aber: MW per kleinste + größte Zahl / 2 bestimm)

Nun geht man von links immer weiter zum Mittelwert und vergleicht jeweils das Element auf das gezeigt wird mit diesem Mittelwert.

Ist das Element größer oder gleich wie der Mittelwert:

bleibt man an dieser Position.

Das gleiche geschieht auch auf der rechten Seite des Mittelwertes nur mit dem Unterschied,

dass das Element kleiner oder gleich des Mittelwerts sein soll.

Ist das rechte Element kleiner als das Linke werden diese miteinander vertauscht und man geht auf beide Seiten eine Position weiter bis das linke Element kleiner als das rechte Element ist.

Jetzt stehen auf der linken Seite alle Elemente die kleiner oder gleich dem Mittelwert sind und rechts alle anderen Elemente.

Nun wird Quicksort noch mal aufgerufen aber nur mit dem linken Teil der Folge und dann noch mal nur mit dem rechten Teil der Folge.

(man teilt quasi immer in 2 Teile pro Mittelwert)

Verständlicher wird das ganze natürlich wieder mit einem Beispiel.

SIEHE ERSTES BLATT

(Als Rekursion, von lateinisch recurrere = zurücklaufen, bezeichnet man den Aufruf oder die Definition einer Funktion durch sich selbst)

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

-> imho entgegen wirken:
per random vermischen oder individuell anpassen

-> vllt noch 2,3 Worte zu Worst and Bestcase (eigene Idee?)

WOrstcase: Mittelwert ist kleinstes oder größtes Element

Bestcase: Mittelwert entspricht exakt der Mitte

Hilf uns und deinen Freunden, indem du diese Seite teilst, verlinkst und bewertest

4.2 / 5 Sternen (12 Bewertungen)
  • Autor: Tom Zeddies
  • Fach: Informatik
  • Stufe: 12. Klasse
  • Erstellt: 2006
  • Note: Ohne Wertung
  • Aktualisiert: 24.08.16

Schreibe jetzt deine Meinung

    Was ist 11 - 8? Ergebnis:  
Wähle dein Bild:

Mitmachen

Drag & Drop oder: Durchsuchen... Endungen: .doc(x) .xls(x) .ppt(x) .pdf .txt .rtf .jpg .gif .png .bmp

Danke für deinen Besuch bei Schulzeux.de

Zeig diese Seite deinen Freunden

Mithelfen ist ganz einfach

Du hast sicher auch noch Hausarbeiten, Vorträge etc. auf deinem PC. Veröffentliche sie in wenigen Sekunden und hilf damit tausenden Mitschülern.

Mehr Infos

Schulzeux.de auf Facebook

Schulzeux.de bei Google+