Problem bei der erklärung von Quick/Heapsort

Computer: Software & Programmierung Programmierung allgemein
#1

Hi,

ich muss den QUick und den Heapsort EINFACH(!!!) NICHT programmierern erklären…ich tu mir dabei aber gewaltig(!) schwer, es kommen dan so konstrukte wie:
Beschreibung des Quicksort-Algorithmus

Quicksort unterteilt die Menge M der Zahlen zuerst in 2 Teilmengen M1 und M2, an einer beliebigen Zahl P aus der Menge M
M1 P
Dieser Schritt wird für jede Teilmenge so oft wiederholt, bis eine Teilmenge nur noch aus einer Zahl besteht.

Beispiel:
5, 3, 2, 1, 7, 4, 6, 9, 8 die unterstrichene Zahl ist die „mittlere“ Zahl P anhand der die 2 Gruppen gebildet werden.

  1. Gruppe (in 1. Stufe): 5, 3, 2, 1, 7, 4, 6
  2. Gruppe (in 1. Stufe): 9, 8

Erzeugung der Gruppen in 2. Stufe
Gruppe 1: 5, 3, 2, 1, 7, 4, 6

  1. Gruppe (2. Stufe): 1
    Ende dieses Zweigs, da die Teilmenge nur noch aus einer Zahl besteht.
  2. Gruppe (2. Stufe): 5, 3, 2, 7, 4, 6
    Gruppe 2: 9, 8
  3. Gruppe (2. Stufe): 8
  4. Gruppe (2. Stufe): 9
     Ende dieses Zweigs, da jede Teilmenge nur noch aus einer Zahl besteht.

Gruppe 1: 5, 3, 2, 7, 4, 6

  1. Gruppe (3. Stufe): 2
    Ende dieses Zweigs, da die Teilmenge nur noch aus einer Zahl besteht.
  2. Gruppe (3. Stufe): 5, 3, 7, 4, 6

…
…

…

herraus, was leider KEIN A… raffen wird.

schlimm wirds beim Heapsort, da ich den selbt nicht 100 Prozentig gerafft habe, geht der heapsort also von der wurzel zum nächsten zweig und immer so weiter runter, oder geht er von der wurzel bis zu den äussersten Blättern zum vergleich?!..

wäre ganz lieb, wenn ihr mir für beide ne gaaannnzzzz simple erklärung liefern könnt und bitte verweist nicht auf die google.de hp´s, die hab ich zu genüge abgeklappert um ne EINFACHE erklärung für beide zu finden-erfolglos…

Dankeschöön, grüsse

#2

Quicksort - bei der Erklärung gehe ich nicht auf irgendwelche Programmiertechnische Feinheiten ein - dafür gibts hunderte Seiten im Web.

Bei Quicksort nimmst du dir als erstes ein zufälliges Element deiner Folge her - das ist dein Pivotelement.

5 3 2 1 7 4 6 9 8

Jetzt mußt du sicherstellen das vor dem Pivotelement nur Zahlen stehen die KLEINER sind als das Pivotelement und das hinter dem Pivotelement nur Zahlen stehen die GRÖSSER sind als das Pivotelement. Bist du mit dem Umschichten fertig, steht das Pivotelement also sicher an der richtigen Stelle in der sortierten Folge.

Um das zu erreichen sammelst du alle Elemente die kleiner als das Pivotelement sind in einer Menge M(k):
5 3 2 1 4
genauso sammelst du alle Elemente die größer (bzw. größer gleich) sind als das Pivotelement M(g):
7 9 8

Deine neue Folge schaut so aus: M(k) Pivotelement M(g):

5 3 2 1 4 6 7 9 8

6 steht jetzt sicher an der richtigen Stelle, und braucht in sukzessiven Operationen nicht mehr beachtet werden.

Mit den beiden neuen Mengen (5, 3, 2, 1, 4) und (7, 9, 8) verfährst du genauso, das ist der rekursive Teil des Algorithmus - du wählst ein beliebiges Pivotelement aus, bildest neue Mengen (kleiner als Pivotelement, größer als Pivotelement), schreibst die Mengen in der Form M(k) Pivotelement M(g) an, und zwar so lange bis alle neuen M(k) und M(g) nur mehr aus max. einem Element bestehen.
Bei deinen Beispiel schaut das folgendermaßen aus, alles was fett gedruckt ist, steht bereits am richtigen Platz:
5 3 2 1 4 6 7 9 8

5 3 2 1 4
1 2 5 3 4 -> Pivotelement 2, 1 ist nur mehr ein Element also auch schon fix

7 9 8
7 8 9 -> Pivotelement 9

1 2 5 3 4 6 7 8 9

5 3 4
3 5 4 -> Pivotelement 3

7 8
7 8 -> Pivotelement 8, 7 ist nur mehr ein Element also auch schon fix

1 2 3 5 4 6 7 8 9

5 4
4 5 -> Pivotelement 4, 7 ist nur mehr ein Element also auch schon fix

1 2 3 4 5 6 7 8 9

schlimm wirds beim Heapsort, da ich den selbt nicht 100
Prozentig gerafft habe, geht der heapsort also von der wurzel
zum nächsten zweig und immer so weiter runter, oder geht er
von der wurzel bis zu den äussersten Blättern zum
vergleich?!..

Heapsort:
Zur Erinnerung:
In einem Heap ist der Wert der Nachfolgerknoten jedes Knotens immer kleiner als der Wert des Knotens selbst.

Heapsort läuft folgendermaßen ab:

  1. Du konstruierst aus deiner Eingabefolge einen Heap.
    Solange der Heap nicht leer ist, führst du folgende Operationen aus:
  1. Du entfernst die Wurzel (aus der Heapdefinition folgt, daß das der größte Wert deiner Folge sein muß) aus dem Heap und fügst sie in deine
    sortierte Liste ein. Anstelle der Wurzel setzt du das unterste Blatt des Heaps ein und löscht das eingesetzte Blatt. Du hast jetzt einen Semiheap, also einen Heap, der für alle Knoten bis auf die Wurzel die Heapbedingung erfüllt.
  2. Du ordnest den Semiheap um bis er wieder ein Heap ist. Jetzt ist der größte Wert des Heaps wieder in der Wurzel -> gehe zu Schritt 2.

Sehr gute Javaapplets zu den beiden Algorithmen gibt es unter folgender Adresse:
http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/ds_…

wäre ganz lieb, wenn ihr mir für beide ne gaaannnzzzz simple
erklärung liefern könnt und bitte verweist nicht auf die
google.de hp´s, die hab ich zu genüge abgeklappert um ne
EINFACHE erklärung für beide zu finden-erfolglos…

Dankeschöön, grüsse