Objektorientierte Programmierung und Modellierung (Fach) / Suchen und Sortieren (Lektion)
In dieser Lektion befinden sich 6 Karteikarten
WS 15/16
Diese Lektion wurde von RouHim erstellt.
- Wie funktioniert die lineare Suche und was sind Vor/Nachteile? Die lineare Suche geht Element für Element vor und schaut ob das gesuchte Element in der Menge/Liste enthalten ist. Vorteile: Einfach zu programmieren / verstehen Nachteile: Langsam
- Wie funktioniert die binäre Suche und was sind Vor/Nachteile? Die binäre Suche setzt vorraus das die Menge/Liste vollständig sortiert ist. Funktionsweise: Das mittlere Element der Liste wird herausgesucht Ist das gesucht Element größer oder kleiner als das mittlere Element?Je nachdem nur noch mit linker oder rechter Liste weitermachen Anschließend wieder auf der linken oder rechten Liste das Mittlere Element finden und größer oder kleiner testen, und so weiter.... bis Element gefunden wurde. Die Laufzeit verhält sich immer logarithmisch.
- Wie funktioniert Selection Sort (Sortieren durch Auswahl)? Findet pro Durchlauf das kleinste Element Setzt dieses an die erste noch unsortierte Stelle Bsp.: [8,6,13,1,3][1,8,6,13,3][1,3,8,6,13][1,3,6,8,13][1,3,6,8,13][1,3,6,8,13]
- Wie funktioniert Bubble Sort (Sortieren durch Aufsteigen)? Die ersten zwei Nachbarwerte werden verglichen Wenn falsche Reihenfolge, wird getauscht Jetzt eine Stelle weiter gehen und wieder die Nachbarn vergleichen Somit ist nach dem ersten Durchlauf die höchste Zahl hinten (aufgestiegen wie eine Luaftblase :D) [8,6,2,1][6,2,1,8][2,1,6,8][1,2,6,8][1,2,6,8]
- Wie funktioniert Insertion Sort (Sortieren durch Einfügen)? Sortieren wie Spielkarten auf der Hand Man beginnt beim ersten unsortieren Element Nun prüft man dieses mit den bereits sortierten Elementen, aber von rechts nach links, an welche Stelle es kommt.(Wenn es noch keine gibt, vergleich der beiden ersten Elemente) [9,15,7,3,1][9,15,7,3,1][7,9,15,3,1][3,7,9,15,1][1,3,7,9,15]
- Wie funktioniert Merge Sort (Sortieren durch Mischen)? Liste wird in viele kleine Listen unterteilt Diese Teillisten werden sortiert Anschließend im Reisverschlussverfahren wieder zu größeren Listen zusammenfügen Solange bis eine sortierte Gesamtliste entsteht. Es gibt also eine Aufteilungsphase & Eine Mischphase.