Aus Das deutschsprachige Scratch-Wiki

Sortieralgorithmen sind Algorithmen, die Listen mit Werten sortieren.

Dieses Projekt vergleicht drei klassische Sortieralgorithmen (bubble, selection, insertion) gegenüber zwei, die für Scratch optimiert wurden (loops, threads).

Wähle die Anzahl der Elemente und drücke den Stern, um das Wettrennen der Sortieralgorithmen zu beginnen.




Schau' dir dieses Projekt auf der Scratch-Webseite an...





Schau' dir dieses Projekt auf der Scratch-Webseite an...


Sortieren durch Vertauschen

Dieses Verfahren wird auch als Bubble-Sort bezeichnet. Es ist einfach und funktioniert so:

  1. In der Liste von vorne nach hinten jedes Element e(i) mit dem dahinter e(i+1) vergleichen. Wenn e(i) > e(i+1) ist, die beiden Elemente vertauschen.
  2. Den Durchlauf so oft wiederholen, bis in einem Durchlauf kein Paar mehr getauscht werden muss.

Sortieren durch Auswählen

Dieses auf Englisch Selection-Sort genannte Verfahren geht so:

  1. Das kleinste Element der Liste suchen.
  2. Dieses mit dem ersten Element e(1) vertauschen.
  3. Das kleinste Element von e(2) bis e(Länge der Liste) suchen.
  4. Dieses mit dem vordersten Element, jetzt e(2), vertauschen.
  5. Schritte 3 und 4 jeweils mit e(3), e(4) usw. bis zum vorletzten Element wiederholen.

Sortieren durch Einordnen

So arbeiten Menschen. Sortieren durch Einordnen, auf Englisch Insertion-Sort. Man bringt zunächst zwei Elemente in die richtige Reihenfolge und sortiert dann die weiteren eins nach dem anderen direkt an der richtigen Stelle ein. Das Verfahren kann man schrittweise so beschreiben:

  1. Das erste Element e(1) in eine neue Liste übertragen.
  2. Das zweite Element e(2) damit vergleichen. Wenn es kleiner ist, davor einordnen, sonst ans Ende stellen.
  3. Das jeweils nächste Element e(i+1) der Reihe nach mit den bereits in der neuen Liste stehenden vergleichen. Sobald es kleiner als das nächste aus der neuen Liste ist, davor einfügen. Wenn die ganze neue Liste ohne Einfügen durchgeprüft wurde, das Element e(i+1) am Ende anhängen.

Um ein Element vor einem bestimmten anderen in eine Liste einzufügen, braucht man kein Unterprogramm schreiben, Scratch hat diese Funktion eingebaut.

Sortieren durch zweifaches Auswählen

Dieses Verfahren, das im Beispielprogramm Loop-Sort heißt, verbessert das Sortieren durch einfaches Auswählen (siehe oben). Bei jedem Schleifendurchlauf wird nun neben dem kleinsten auch das größte Element ausgewählt. Das kleinste Element wird nach vorn gesetzt, das größte nach hinten.

Dadurch kommt man mit der Hälfte der Schleifendurchläufe aus, weil man pro Durchlauf zwei statt einem Element verarbeitet. Das Verfahren braucht trotzdem mehr als die halbe Zeit des Sortierens durch einfaches Auswählen, weil man pro Durchlauf natürlich mehr Vergleichsoperationen hat.

Sortieren mit verteilten Listen

Im Beispielprogramm heißt dieses Verfahren Thread-Sort. Es nutzt die Möglichkeit, dass in Scratch mehrere Skripte gleichzeitig laufen können und parallelisiert die Verarbeitung von zwei Listen. Das kann so funktionieren:

  1. Den Mittelwert aller Listenelemente bilden.
  2. Elemente, die kleiner als der Mittelwert sind, in Liste 1 kopieren.
  3. Die restlichen Elemente in Liste 2 kopieren.
  4. Beide Listen parallel durch Einordnen sortieren.
  5. Liste 1 in Gesamtliste übertragen.
  6. Liste 2 an Gesamtliste anhängen.

Man kann auch dieses Verfahren noch erweitern, indem man den Algorithmus schachtelt und mit vier, acht oder noch mehr Listen arbeitet. Wie sinnvoll das ist, hängt vor allem von der Anzahl der Datensätze ab.

Weiterführende Informationen

Ausführlichere und wissenschaftlicher formulierte Informationen sowie Hinweise auf weitere Quellen finden sich hier



Code zum Einbinden ins Forum:
[wiki=de:Sortieralgorithmen]Sortieralgorithmen[/wiki]
Kategorie:En-Link