Sortieralgorithmen
Musstest du schon einmal Tausende Wörter nach dem Alphabet sortieren? Nein? Das liegt vermutlich daran, dass Computer in vielen Fällen das Sortieren übernehmen. Dazu benutzen sie Programme, zu denen man Sortieralgorithmen sagt.
Kurz gesagt vergleicht ein solcher Sortieralgorithmus zwei Werte und tauscht sie nach Bedarf aus. Du kannst dir das vorstellen, als hättest du eine Waage, mit der du genau gleich aussehende Kugeln nach ihrem Gewicht ordnen müsstest.
Je nachdem, wie du diese Aufgabe löst, kann es länger oder kürzer gehen, bis du die Kugeln geordnet hast. Je mehr Kugeln du hast, desto wichtiger ist es, ein möglichst schnelles Verfahren zu haben.
Die langsamsten Verfahren sind die, welche nach dem Zufallsprinzip funktionieren. Diese sind viel zu wenig effizient für einen Computer. Stattdessen werden ausgeklügelte Sortieralgorithmen verwendet. Zum Beispiel der Bubble Sort. Bei diesem Verfahren wird ein Element immer mit dem nächsten Element verglichen und dann getauscht, wenn das linke Element grösser als das rechte ist. So steigen grosse Zahlen wie Blasen auf.
Hier ein Beispiel dazu:
Zuerst wird die 3 mit der 2 verglichen. Da die 3 grösser ist, tauschen die beiden Zahlen ihren Platz.
Weil die 3 kleiner ist als die 4, wird hier nicht getauscht. Die 4 ist aber grösser als die 1 und die beiden Zahlen tauschen den Platz.
Jetzt beginnt ein neuer Durchlauf. Da die 2 kleiner ist als die 3, passiert hier nichts. Die 3 ist aber grösser als die 1, also werden die Zahlen getauscht.
Die 3 ist kleiner als die 4 und es ändert sich nichts mehr. Es beginnt wieder ein neuer Durchgang, bei dem nur noch die 2 und die 1 den Platz tauschen müssen.
Solche einfachen Sortieralgorithmen kann man auch mit Schülerinnen und Schülern anschauen. Auf der MIA-Scouts Webseite findest du dazu ein Informatik-Challenge.
Natürlich gibt es noch effizientere Sortieralgorithmen. Solche Algorithmen funktionieren meistens nach dem “Divide and Conquer”-Prinzip, es geht also um das Teilen der ursprünglichen Liste.
Wenn wir wieder die Kugeln als Beispiel nehmen, so würde man die Kugeln zuerst in kleinere Gruppen aufteilen und zuerst die Reihenfolge innerhalb der Gruppensortieren. Ein Divide and Conquer-Verfahren namens “Merge Sort” teilt zum Beispiel alle zu sortierenden Werte in einzelne Listen auf und fügt sie dann Schritt für Schritt wieder zusammen (merge). Schau dir doch dieses Video zu Algorithmen und dem Merge-Sort (YouTube, auf Englisch) von Crash Course Computer Science an.
Der Quick-Sort-Algorithmus benutzt einen Pivot (Angelpunkt), um zu sortieren. Es wird zuerst ein Element am richtigen Ort eingeordnet. Danach werden alle kleineren Elemente links vom Pivot positioniert und alle grösseren rechts davon. Danach werden weitere Pivots gesetzt, bis die Liste sortiert ist. Auch hier wird eine Liste in kleinere Teile zerlegt, um das Problem schneller zu lösen. Wenn es dich interessiert, findest du auf der Webseite von Hack-Deck eine Erklärung zum Quick Sort.
Insgesamt gibt es sehr viele, unterschiedlich schnelle Sortieralgorithmen. Im Video «15 Sorting Algorithms in 6 Minutes» (YouTube) findest du weitere, grafisch dargestellte Sortieralgorithmen.
Cäsar-Chiffre
Neben dem Sortieren ist eine andere wichtige Aufgabe von Computern Daten so zu versenden, dass sie nicht von Unbefugten abgefangen werden können. Das ist zum Beispiel beim Online-Banking wichtig. Eine sehr einfache Form einer solchen Verschlüsselung ist die Cäsar-Chiffre.
Die Cäsar-Chiffre ist eine Möglichkeit, um einen Text zu verschlüsseln. Dabei wird beispielsweise jeder Buchstabe im Alphabet um 3 Stellen verschoben. Aus dem «A» wird so zum Beispiel ein «D».
| A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z |
| D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | A | B | C |
In dieser Informatik-Challenge der MIA-Scouts erfährst du mehr zur Cäsar-Chiffre.
Natürlich sind heutige Verschlüsselungen nicht mehr so einfach zu lösen, wie die Cäsar-Chiffre. Oft basieren sie darauf, dass es einen öffentlichen und einen privaten Schlüssel gibt, damit werden wir uns hier aber nicht beschäftigen.
Das Fachgebiet, das sich mit Methoden zur Verschlüsselung von Nachrichten bzw. Daten beschäftigt, nennt sich Kryptografie. Wenn du mehr über die Entwicklung der Verschlüsselung von Nachrichten wissen möchtest, kannst du dieses Video von Crash Course Computer Science anschauen, das einen guten Überblick über die Kryptographie gibt (YouTube, auf Englisch).