8

PI (Fach) / Sortieren (Lektion)

Diese Lektion wurde von blace erstellt.

Lektion lernen

Diese Lektion ist leider nicht zum lernen freigegeben.

zurück  |  weiter 1 / 1

• Wie funktioniert Insertion Sort? Erläutere die Arbeitsweise an einem Beispiel. Wie hoch ist der Aufwand? Die Insertion Sort funktioniert, indem sie immer das aktuelle Element entnimmt, den freigewordenen Platz benutzt, ein anderes Element verschiebt und das herausgenommene Element wieder einfügt. Bsp. 5 1 8 3 Man startet mit der 1, diese wird entnommen, dann wird geguckt, ob die 5 größer, oder kleiner ist. Da sie größer ist wird die 5 auf das leere Feld geschoben und die 1 wieder in das Feld der 5 eingesetzt 1 5 8 3 Nun entnehmen wir die 8 und gucken uns wieder die 5 an, da diese kleiner als die 8 ist bleibt sie wo sie war und auch die 1 ist kleiner und bleibt wo sie ist, also wird die 8 einfach wieder an ihre Stelle eingefügt 1 5 8 3 Nun entnehmen wir die 3 und gucken uns die 8 an, die 8 ist größer und wird auf das leere fehlt verschoben. Die 5 ist auch größer und wird also auch auf das neu leer gewordenen Feld verschoben. Die 1 ist allerdings kleiner weshalb die 3 an die Stelle, wo die 5 vorher war eingesetzt wird. 1 3 5 8 Der Aufwand liegt bei O(n^2) stabil
• Wie funktioniert Selection Sort? Erläutere die Arbeitsweise an einem Beispiel. Wie hoch ist der Aufwand? Die Selection Sort funktioniert, indem sie immer das Maximum findet, dieses ans Ende setzt und dann diesen prozess mit einer kleineren Folge (ohne das zuvor bewegte Maximum) wiederholt. Bsp. 5 1 8 3 Untersucht jedes Element darauf, ob es das Maximum ist, in diesem Fall ist es die 8 und tauscht dieses dann mit dem letzten Element in der Liste 5 1 3 8 Nun sucht man erneut aber ohne die 8, also ist die 5 das Maximum und tauscht mit der 3 3 1 5 8 erneute suche, die 3 ist das Maximum 1 3 5 8 Aufwand um das Maximum zu finden ist O(j) Aufwand insgesamt ist O(n^2) instabil
• Wie funktioniert Bubble Sort? Erläutere die Arbeitsweise an einem Beispiel. Wie hoch ist der Aufwand? Bei der Bubble Sort, werden benachbarte Elemente verglichen und getauscht, falls sie die falsche Reihenfolge haben. Dies wird so lange durchgeführt bis keine Vertauschungen mehr passieren. Bsp. 5 1 8 3 Wir untersuchen also erstmal die 5 und die 1 und tauchen diese, da sie die falsche Reihenfolge haben 1 5 8 3 Dann werden die 5 und die 8 untersucht, diese haben aber die richtige Reihenfolge und bleiben daher so wie sie sind. nun werden die 8 und die 3 untersucht und getauscht 1 5 3 8 Jetzt geht die Bubble Sort wieder an den Anfang der Liste und geht sie erneut durch 1 und 5 sind richtig, 5 und 3 werden getauscht 1 3 5 8 5 und 8 sind richtig, 1 und 3 sind richtig keine Vertauschungen mehr Aufwand: best case vorsortiert: O(n) worst case rückwärts sortiert: O(n^2) average case: O(n^2) stabil
• Wie funktioniert Merge Sort? Erläutere die Arbeitsweise an einem Beispiel. Wie hoch ist der Aufwand? Die Merge Sort arbeitet indem sie immer eine Folge mit mehr als einem Element in zwei Hälften teilt und diese sortiert und dann wieder zusammenfügt. Bsp. 5 1 8 3 5 1 || 8 3 5 || 1 1 5 8 || 3 3 8 1 5 || 3 8 Die ersten beiden der beiden Folgen werden verglichen 1 ist kleiner 1 erneuter Vergleich 3 ist kleiner als 5 1 3 erneuter vergleich 5 ist kleiner als 8 1 3 5 8 Aufwand: Folge kann log2(n) mal zerlegt werden pro Zerlegung alle elemente mischen: O(n) gesamt: O(n log n) Nachteil: Mischen erfordert Platz für 2n Elemente Stabil
• Wie funktioniert Quick Sort? Erläutere die Arbeitsweise an einem Beispiel. Wie hoch ist der Aufwand? Bei der Quick Sort wird eine Folge mit nur einem Element immer als sortiert angesheen. Sollte eien Folge mehr Elemente haben so wird ein Element entnommen (das Pivot Element), eine neue Folge aus den kleineren Elementen gebildet und diese Folge wird sortiert, sowie eine Folge aus den größeren Elementen gebildet und diese sortiert. Dann wird die Folge mit den kleineren Elementen vor und die andere hinter das Pivot Element gesetzt. Bsp: 8 2 1 5 9 Quicksort(0,4) 1 ist das pivot Element an der Stelle 2 p=Z(0,4,2) nun wird die Liste so sortiert, dass Links vom PPivot Element kleinere und rechts größere Elemente sind 2 8 1 5 9 2 1 8 5 9 2 1 5 8 9 Nun werden die zwei neuen Folgen erstellt QuickSort(0,1) QuickSort(3,4) 2 1 p=Z(0,1,0) 1 2 8 9 p=Z(3,4,3) 8 9 Aufwand: best case Teilfoglen sind immer gleich lang: O(n log n) worst case eine Teilfolge ist immer leer, bei Vorsortierung und wenn das erste Element das Pivot Element ist: O(n^2) average: O(n log n) instabil
• Was ist das Pivot-Element bei Quick Sort und auf welche Weisen kann es jeweils gewählt werden? Das Pivot Element ist das Element, vor und hinter welchem sortiert und eingefügt wird. Dieses kann unterschiedlich gewählt werden. Entweder ist es das erste oder letzte Element das mittlere Element ein zufälliges Element (dies schließt standartfälle aus) und die Laufzeit ist nicht reproduzierbar Kann gewählt werden mittels der 3-Median-Strategier p=median(a[bottom], a[top-1], a[(bottom+top)/2]) median(a,b,c) = a falls b<=a<=c oder c<=a<=b b falls a <= b <= c oder c <= b<=a c falls a <=c <=b oder b<=c<=a
• Wann ist ein Sortierverfahren stabil? Welche stabilen Verfahren haben wir in der Veranstaltung kennengelernt? Ein Sortierverfahren ist stabil, wenn Elemente mit gleichem Suchschlüssel auch nach der sortierung noch in der gleichen Reihen folge sind wie vorher. Merge Sort ist stabil Bubble Sort ist stabil Insertion Sort ist stabil
• Welche Sortieralgorithmen kennst Du? Erläutere mindestens einen davon. Insertion Sort Selection Sort Bubble Sort Merge Sort Quick Sort Einen erklären

zurück  |  weiter 1 / 1