Ein weiteres sehr häufiges Problem in der Informatik ist es, bestimmte Datensätze in einer Datenbank zu sortieren. Auch dies hört sich erst mal sehr einfach an, da es uns Menschen sehr leicht fällt, eine bestimmte Sortierung herzustellen. Bei großen Datenmengen wie z.B. der Adressdatenbank des deutschen Einwohnermeldeamts (ca. 80 Millionen Einträge) sieht man allerdings schnell, dass das für einen Menschen viel zu komplex wäre.
Auch hier beschränken wir uns zunächst mal auf einfachere Sortierprobleme. Statt einer gesamten Datenbank betrachten wir "nur" einen Array, und anstatt von Adressdaten, die wir auf nach meherern Kriterien sortieren wollen (zuerst nach Nachname, dann nach Vorname, dann nach Adresse o.ä.), beschränken wir uns zunächst mal auf Zahlen.
Lest den Artikel Sortierproblem auf inf-schule.de. Notiert eure Antworten zu den Fragen im Artikel im Gruppendokument.
- Aufgabe 1 aus dem Artikel müsst ihr nicht beantworten, die war in der letzten Lektion schon dran.
Lest den Artikel Entwicklung von Sortieralgorithmen auf inf-schule.de. Notiert eure Antworten zu den Fragen im Artikel im Gruppendokument.
- Bearbeitet auch sowohl von Version 1 als auch von Version 2 jeweils Aufgabe 1 aus dem Artikel (Antworten → Gruppendokument!).
- Lest euch das Fachkonzept Fachkonzept: Struktogramm durch.
- Versucht euren Algorithmus als Struktogramm darzustellen!
Lest den Artikel SelectionSort auf inf-schule.de. Notiert eure Antworten zu den Fragen im Artikel im Gruppendokument.
- Bearbeitet nur Aufgabe 1 aus dem Artikel! (Antworten → Gruppendokument!)
- Lest trotzdem noch den Abschnitt "Ablaufmodellierung".
- Lest das Fachkonzept: SelectionSort und vergleicht das Struktogramm und den JavaCode.
- Probiert den Code auch aus!
Lest den Artikel InsertionSort auf inf-schule.de. Notiert eure Antworten zu den Fragen im Artikel im Gruppendokument.
- Bearbeitet alle drei Aufgaben aus dem Artikel! (Antworten → Gruppendokument!)
- Überprüft eure Struktogramme und Implementierungen des Algorithmus am Fachkonzept: InsertionSort.
Diskutiert im Gruppendokument, welche Vor- und Nachteile die beiden Sortieralgorithmen haben. Geht dabei auf folgende Aspekte ein:
- Anzahl von Vergleichen / Vertauschungen
- Was passiert, wenn man nur wenige Elemente in eine bereits sortierte Liste einfügen möchte?