Anmerkung: In dieser Jahrgangsstufe geht es vor allem um die Programmierung mit Java. Zum Erlernen eignet sich unter anderem das Programm BlueJ.
Inhaltsverzeichnis
[Anzeigen]
[Verbergen]
Sortierverfahren
Allgemeines
Das Sortieren von Daten nach bestimmten Kriterien gehört zu den wichtigsten Problemen der Informatik. Bei großen Datenmengen ist es sehr wichtig, dass effiziente Algorithmen zur Verfügung stehen, die möglichst wenig Zeit zum Sortieren benötigen. Im Folgenden werden „einfachere“ Algorithmen betrachtet, die recht verständlich zu impletieren sind, aber eine relativ lange Laufzeit haben.
Die drei Algorithmen Insertsort (Sortieren durch Einfügen), Selectionsort (Sortieren durch Auswählen) und Bubblesort (Sortieren durch Vertauschen) werden beschrieben und an einem Beispiel erläutert. Auf weitere Algorithmen wie Mergesort oder Quicksort werden dagegen nicht besprochen.
Selectionsort, Insertsort, Bubblesort
Selectionsort
Grundlagen
Selectionsort arbeitet nach dem Prinzip, das kleinste Element des Feldes zu suchen, und dieses dann mit dem ersten Element des zu betrachteten Teils zu tauschen.
Zu Beginn sucht man im ganzen Feld nach dem kleinsten Element und tauscht es mit dem ersten Element. Danach sucht man im Restfeld ohne erstes Element nach dem kleinsten Element und tauscht mit dem zweiten Element bzw. mit dem ersten Element des zu betrachtenden Teils. Dies wiederholt man, bis das zweitgrößte Element an den korrekten Platz Platz gebracht wurde.
Beispiel
Insertsort
Grundlagen
Insertsort arbeitet nach dem Prinzip, das Feld in einen sortierten und einen unsortierten Teil zu teilen und dann das erste Element des unsortierten Teils an die richtige Stelle im sortierten Teil zu schieben. Zunächst besteht der sortierte Teil aus dem ersten Element. Das erste Element des unsortierten Teils ist damit das zweite. Dieses wird solange mit dem vorherigen vertauscht, solange es kleiner als dieses ist oder das Element noch nicht das erste Element des Feldes ist.
Somit vergrößert sich der sortierte Teil jeweils um eins, während sich der unsortierte um eins verringert. Dies wird wiederholt, bis der unsortierte Teil null wird und somit das ganze Feld sortiert vorliegt.
Beispiel
Bubblesort
Grundlagen
Der Sortieralgorithmus Bubblesort (Blasensortierung) arbeitet nach dem Prinzip, dass das Feld durchlaufen wird und dabei so getauscht wird, dass das größte bzw. kleinste Element an der richtigen Stelle steht. Nachfolgend wird die aufsteigende Variante beschrieben, so dass das größte Element nach oben wandert.
Man beginnt dazu am Anfang des Feldes und tauscht benachbarte Elemente aus, wenn das rechte Element kleiner als sein Vorgänger ist. Somit steht das größte Element nach einem Durchlauf am Ende des Feldes. Diese Sortierung wird wiederholt, ohne dass dabei der letzte bereits sortierte Feldteil betrachtet wird. Damit erhält man ein sortiertes Feld.
Beispiel mit dem Feld der Abfolge „5, 37, 13, 21, 2, 13“
1. Durchlauf
2. Durchlauf
3. Durchlauf
4. Durchlauf
5. Durchlauf
