Bereits Kunde? Jetzt einloggen.
Lesezeit ca. 11 Min.

Sortieralgorithmen in Go vorgestellt: Sortierte Welt


Linux Magazin - epaper ⋅ Ausgabe 2/2020 vom 02.01.2020

Ob alphabetisch oder numerisch, als Bubble- oder Quicksort: Sortiert wird immer. Auch Mike Schilli zeigt sich bei seiner Vorstellung verschiedener Sortieralgorithmen in Go komplett sortiert.


Artikelbild für den Artikel "Sortieralgorithmen in Go vorgestellt: Sortierte Welt" aus der Ausgabe 2/2020 von Linux Magazin. Dieses epaper sofort kaufen oder online lesen mit der Zeitschriften-Flatrate United Kiosk NEWS.

Bildquelle: Linux Magazin, Ausgabe 2/2020

Igor Zakharevich, 123RF

Schon lange, bevor es die ersten Computer gab, beschäftigte das Sortieren von Daten die Menschheit. Der deutschstämmige US-Amerikaner Herman Hollerith erfand bereits um 1890 herum eine elektromechanische Maschine, die Lochkarten in verschiedene Ausgangsschächte sortierte, um die Auswertung der seinerzeitigen Volkszählung in den USA zu beschleunigen (Abbildung 1). Und auch heute sortieren ...
Maschinell sortiert wird also weiterhin auf Teufel komm raus. Dabei verändern Programme die Reihenfolge beliebig geformter Datenstrukturen; als Sortierkriterium dient aber meist ein einfacher Schlüssel, oft eine Ganzzahl oder eine Zeichenkette. Darum zeigt die klassische Literatur ...

Weiterlesen
epaper-Einzelheft 5,99€
NEWS 14 Tage gratis testen
Bereits gekauft?Anmelden & Lesen
Leseprobe: Abdruck mit freundlicher Genehmigung von Linux Magazin. Alle Rechte vorbehalten.

Mehr aus dieser Ausgabe

Titelbild der Ausgabe 2/2020 von Die Alleswisser. Zeitschriften als Abo oder epaper bei United Kiosk online kaufen.
Die Alleswisser
Titelbild der Ausgabe 2/2020 von News. Zeitschriften als Abo oder epaper bei United Kiosk online kaufen.
News
Titelbild der Ausgabe 2/2020 von Zahlen & Trends. Zeitschriften als Abo oder epaper bei United Kiosk online kaufen.
Zahlen & Trends
Titelbild der Ausgabe 2/2020 von Bericht von der VMworld 2019 in Barcelona: In Richtung Pazifik. Zeitschriften als Abo oder epaper bei United Kiosk online kaufen.
Bericht von der VMworld 2019 in Barcelona: In Richtung Pazifik
Titelbild der Ausgabe 2/2020 von Kernel 5.4: ExFAT in Staging, Lockdown-Modus: Neues Sperrgebiet. Zeitschriften als Abo oder epaper bei United Kiosk online kaufen.
Kernel 5.4: ExFAT in Staging, Lockdown-Modus: Neues Sperrgebiet
Titelbild der Ausgabe 2/2020 von Sicher auf Kubernetes zugreifen: Fallen vermeiden. Zeitschriften als Abo oder epaper bei United Kiosk online kaufen.
Sicher auf Kubernetes zugreifen: Fallen vermeiden
Vorheriger Artikel
C++ Core Guidelines – Folge 50: Auf Sparflamme
aus dieser Ausgabe
Nächster Artikel IT PROFI MARKT
aus dieser Ausgabe

Schon lange, bevor es die ersten Computer gab, beschäftigte das Sortieren von Daten die Menschheit. Der deutschstämmige US-Amerikaner Herman Hollerith erfand bereits um 1890 herum eine elektromechanische Maschine, die Lochkarten in verschiedene Ausgangsschächte sortierte, um die Auswertung der seinerzeitigen Volkszählung in den USA zu beschleunigen (Abbildung 1). Und auch heute sortieren Computer laufend Daten – hier für eine Liste gezielt vorgeschlagener Youtube-Videos, dort für die Top-100-Charts der Musikindustrie, gestaffelt nach Verkaufszahlen, oder für eine Performance-Analyse die langsamsten Queries aus einer MySQL-Datenbank.
Maschinell sortiert wird also weiterhin auf Teufel komm raus. Dabei verändern Programme die Reihenfolge beliebig geformter Datenstrukturen; als Sortierkriterium dient aber meist ein einfacher Schlüssel, oft eine Ganzzahl oder eine Zeichenkette. Darum zeigt die klassische Literatur [1] zu Sortieralgorithmen [2] oft nur auf, wie man eine Reihe von Zahlen sortiert: Die Portierung auf eine komplexere Datenstruktur ist aber durchweg trivial und lässt sich über eine einfache Zuordnung vom Schlüssel zur Datenstruktur bewältigen.

Blasen steigen auf

Als einfachsten Sortieralgorithmus lernen Programmieranfänger oft den Bubblesort mit seinen zwei For-Schleifen kennen. Mittels der ersten Schleife hangelt der In- dex »i« sich von links nach rechts durch die Elemente eines Arrays. Zu jedem untersuchten Element startet eine weitere For-Schleife, die alle folgenden Elemente abklappert und damit sicherstellt, dass das untersuchte Element der ersten Schleife kleiner ist als alle folgenden. Findet das Verfahren ein kleineres Element weiter rechts, vertauscht es dieses kurzerhand mit dem untersuchten. So stellt die erste Schleife sicher, dass jedes bearbeitete Element kleiner ausfällt als alle darauffolgenden. Am Ende, wenn die erste Schleife am rechten Rand anschlägt, ist das Array dann aufsteigend sortiert (Abbildung 2).
Listing 1 zeigt in der ersten For-Schleife ab Zeile 11 den Operator »range«, der zu jedem Element des Array-Slice »items« den bei 0 startenden Index und das Element selbst zurückliefert. Letzteres ignoriert der Schleifenkopf, indem er es der Pseudovariablen »_« zuweist, da ihn nur der Index interessiert.
Die zweite For-Schleife ab Zeile 12 startet beim Element direkt rechts davon, der Index »j« fängt bei »i+1« an zu laufen. Findet sich auf der Indexposition »j« ein Element, das größer ist, als das von »i« referenzierte, vertauscht das Programm beide kurzerhand mit dem in Go so praktischen Konstrukt »a,b = b,a«. Mit »go build bubble.go« kompiliert, zeigt das Programm die sortierte Farbenliste (Listing 2).
Der Bubble-Sort ist leicht zu verstehen, braucht aber verhältnismäßig viele – O(n²) – Schritte zur Sortierung.

Abbildung 2: Die zwei Schleifenvariablen »i« und »j« in Bubblesort hangeln sich durch das Array und vertauschen unsortierte Elemente.


Schlauere Verfahren wie Mergesort oder Quicksort bieten oft eine bessere Performance. Bei kleinen Datenmengen, etwa bei Arrays mit bis zu fünf Elementen, arbeitet Bubblesort aber gut genug. Es sortiert die Einträge im Original-Array ohne externe Speicherbedürfnisse, ist stabil (die Reihenfolge gleicher Elemente bleibt unverändert) und läuft vor allem bei fast vollständig sortierten Eingangsdaten blitzschnell.

Countingsort

Bei Bewerbungsgesprächen kommt manchmal die Frage nach schnellen Suchalgorithmen auf, und bevor der Applikant reflexartig „Quicksort“ hervorsprudelt, sollte er sorgfältig abwägen, ob nicht besondere Rahmenbedingungen des ihm gestellten Problems auch trickreichere Verfahren zulassen. Besteht der zu sortierende Korpus zum Beispiel nur aus wenigen verschiedenen Schlüsseln, dann ist der Countingsort-Algorithmus [3] eventuell noch schneller (Abbildung 3).

Abbildung 1: Lochkartensortiermaschine von IBM aus dem Jahr 1949.


National Institute of Standards and Technology Digital Collections, Gaithersburg, MD 20899

In Listing 3 stehen im zu sortierenden Array »things« nur die Werte »3«, »4« und »5«. Statt nun anzufangen, dort wie wild Elemente zu vertauschen, führt der Algorithmus lediglich im Array »count« an den Indexpositionen »3«, »4« und »5« auf, wie oft die verschiedenen Werte im zu sortierenden Array vorkommen. An der Indexposition »3« steht dann später der Wert 7 (in »things« gibt es sieben Dreien) und an der Indexposition »4« eine 5 (für die fünf Vierer in »things«), und so weiter.

Statische Arrays erweitert

Da die Suchroutine am Anfang nicht weiß, welche Schlüssel im zu sortierenden Array auftauchen, legt sie zunächst ein leeres Array »count« an. Will dann die For-Schleife ab Zeile 14 einen Eintrag in »count« an der Indexposition »thing« anlegen, erweitert Zeile 16 »count« mittels der eingebauten Funktion »append()« auf die geforderte Größe.

Abbildung 3: Die drei Stufen des Countingsort: Histogramm, Indexberechnung, Endresultat.


Im Gegensatz zu typischen Skriptsprachen arbeitet Go nämlich nicht mit dynamisch wachsenden Feldern, sondern mit solchen fester Größe. Legt ein Programm einmal ein neues Array mit drei Elementen mittels »make(int, 3)« an und greift später auf ein Element außerhalb des Bereichs 0 bis 2 zu, wirft Go einen Runtime-Fehler und bricht das Programm ab. Das gilt übrigens auch für Array-Slices: Sie definieren nur ein Fenster auf ein bestehendes Feld. Ein Array lässt sich nur erweitern, indem die eingebaute Funktion »append()« ein neues erzeugt, dessen zweiter und alle folgenden Parameter neu angehängte Elemente definieren.
So macht Zeile 16 aus dem alten, nun zu kurzen Array »count« ein neues, um die Differenz aus dem gewünschten Index (in der Variablen »thing«) und dem letzten Index des bestehenden Arrays längeres Feld und weist es wieder dem ursprünglichen »count« zu. Dazu kreiert der Code mit »make()« ein kleines Array, das die Differenz auffüllt, und gibt dessen Elemente einzeln (mit »…« aufgedröselt) der Funktion »append()« zu futtern.

Abbildung 4: Beim Aufnehmen eines Blatts sortiert der Kartenspieler neue Karten ein, indem er in der Hand an der entsprechenden Stelle Platz macht.


Nach der ersten For-Schleife stehen im Array »count« ab Zeile 21 die Zähler für die eingesammelten Schlüssel. Die zweite For-Schleife ab Zeile 24 iteriert nun über die Zähler in »count« und füllt das Array »things« erst mit sieben Dreien, dann mit fünf Vieren und so weiter. Das Verfahren nutzt zwar ein externes Feld »count« zum Zählen, dessen Größe fällt aber bei wenigen verschiedenen Schlüsseln nicht ins Gewicht. Die Sortierung erfolgt in-place, modifiziert also das Original-Array. Die Anzahl der benötigten Schritte wächst linear (O(n)), das Verfahren arbeitet also bei großen Datenmengen um Größenordnungen schneller als selbst die ausgefuchsteste generische Sortierfunktion – allerdings nur wegen der ganz speziellen Form der Eingangsdaten.

Abbildung 5: Verschobene Elemente beim Insertionsort.


Insertionsort

Nimmt ein Kartenspieler ein neues Blatt auf, sortiert er aufgenommene neue Karten einzeln in die Hand ein, indem er an der einzufügenden Stelle Platz schafft. Er rückt dazu niederwertigere Karten nach links und höherwertige Karten nach rechts. Die neue Karte fügt er in den dadurch entstehenden Zwischenraum ein (Abbildung 4). So funktioniert auch der Insertionsort, ein Verfahren [4], das in-place sortiert und kurz und bündig daherkommt, aber einige geistige Klimmzüge erfordert.
Der Algorithmus teilt das zu sortierende Array in zwei Abschnitte auf: links die bereits soweit sortierten Elemente, rechts die unsortierten. Dazu bestimmt er ein aktuell zu untersuchendes Element, beginnend mit dem zweiten des Arrays. In Abbildung 5 oben handelt es sich dabei zunächst um die Vier. Links davon steht in der bereits sortierten Liste nur die Drei; rechts davon folgt der bis dato unsortierte Teil, beginnend mit der Eins. Nun prüft eine nach links hoppelnde Schleife, wo es das aktuelle Element einzufügen gilt. Da das aktuelle Element (die Vier) größer ist als das einzige sortierte Element weiter links, gibt es nichts weiter zu tun – der Algorithmus schreitet zum nächsten aktuellen Element fort.
Im nächsten Schritt in Abbildung 5 (unten) ist die Eins das aktuelle Element, und die nach links hoppelnde Schleife prüft, wo sie es im sortierten Teil einfügen muss. Sie sieht zunächst die Vier, stellt dann fest, dass das aktuelle Element (die Eins) links davon stehen muss, und schiebt die Vier deshalb um eine Stelle nach rechts (Schritt (a)), an die Stelle des aktuellen Elements, das sie vorher in einer Variablen gesichert hat. Weiter links sieht die Schleife dann die Drei auftauchen, die ebenfalls rechts des aktuellen Elements stehen sollte, und schiebt sie an die vorige Position der Vier (Schritt (b)). Nun steht der gesicherten Eins nichts mehr im Weg, und sie kann an die erste Position des Arrays wandern (Schritt (c)). Die Folge lautet nun 1-3-4-…, und der Algorithmus setzt sich mit der Zwei als aktuelles Element fort.

Listing 4 implementiert das Ganze relativ kompakt. Die For-Schleife ab Zeile 11 bestimmt das aktuelle Element, beginnend mit »j=1«, also dem zweiten Element des bei der Indexposition 0 startenden Arrays. Die Ausgabe von Listing 4 mit den verschiedenen Sortierschritten und dem jeweils aktuellen Element »key« zeigt Abbildung 6.
Die nach links hoppelnde Prüfschleife zum Platzmachen im sortierten Teil beginnt in Zeile 15 mit »i=j-1«. Sie setzt sich fort, bis sie eben auf ein sortiertes Element trifft, das kleiner oder gleich dem aktuellen ist, oder bis sie mit »i<0« am linken Rand aus dem Array purzeln würde. In jedem Schleifendurchgang kopiert Zeile 16 ein Element im sortierten Bereich um eins nach rechts, und »i« verringert sich um Eins. Am Ende der Schleife kopiert Zeile 19 das in »key« zwischengespeicherte aktuelle Element dann an die frei gewordene Stelle, und die äußere For-Schleife geht in die nächste Runde.
Allerdings wächst die Anzahl der beim Insertionsort benötigten Schritte quadratisch mit der Anzahl der Elemente.

Der Algorithmus arbeitet also doch nicht schneller als der Bubblesort. Für zufällig strukturierte Eingangsdaten gibt es damit in der Tat schlauere Verfahren, die die Anzahl der Schritte von O(n²) auf O(n*lg(n)) reduzieren.

Abbildung 6: Der Insertionsort aus Listing 4 sortiert das Feld, indem er aus der Reihe fallende Werte von links nach rechts Stück für Stück an der richtigen Stelle einschiebt.


Abbildung 7: Die Funktion »merge()« kombiniert zwei sortierte Stapel (oben) zu einem ebenfalls sortierten Stack (unten) und wählt für den nächsten Schritt immer den oberen Stapel mit der niedrigeren Karte.


Mergesort

Bessere Verfahren nutzen oft das Prinzip „teile und herrsche“. Sie lösen also nicht gleich das ganze Problem in einem Rutsch, sondern zerlegen es in zwei einfacher zu lösende Teilprobleme, die sie dann rekursiv in Angriff nehmen.
Am Mergesort gefällt seine beinahe triviale Implementierung aus reiner Rekursion. Der Trick besteht darin, das Array zu halbieren, die zwei Hälften individuell zu sortieren und dann die zwei sortierten Stapel so miteinander zu einem neuen zu mischen, dass wieder ein sortierter Stapel herauskommt. Das individuelle Sortieren ist eigentlich gar keines: Die Sortierfunktion halbiert wiederum das Array und ruft sich anschließend selbst auf die beiden Hälften so lange selbst auf, bis ein Array mit nur einem Element daherkommt. Das deklariert die Funktion dann als sortiert und gibt es unverändert zurück.

Das eigentliche Hirnschmalz des Verfahrens steckt in der Funktion »merge()«, die zwei sortierte Arrays zusammenfügt. Dazu schreitet sie durch die Elemente der beiden sortierten Stapel, vergleicht die beiden aktuellen Elemente, entfernt das jeweils niedrigere und legt es auf den Ergebnisstapel. Abbildung 7 illustriert das Verfahren anhand eines Kartenspiels, das die beiden oberen Stapel zu einem ebenfalls sortierten unten liegenden kombiniert.
In Listing 5 nimmt »merge()« ab Zeile 24 ein Ganzzahl-Array »a« entgegen sowie drei Indexpositionen »p«, »q« und »r«. Die zwei Teilfelder, die »merge()« zusammenfügen soll, liegen an den Positionen »p« bis »q« sowie »q+1« bis »r«. Das Ergebnis legt die Funktion in-place im Original-Array »a« ab.

Abbildung 8: Mergesort bringt ein Feld mit sieben Ganzzahlen in die korrekte Reihenfolge.


Das setzt aber auch voraus, dass »merge()« zunächst eine Kopie des linken und des rechten Arrays in »left« und »right« anlegt. Die Funktion alloziert dazu jeweils mit »make()« den Speicher für ein Array der gewünschten Länge. Anschließend ruft sie ab der Zeile 28 die in Go eingebaute Funktion »copy()« auf und übergibt ihr die Anfangsposition des zu kopierenden Arrays mit »C<a[p:]>« »C<a[q+1:>>« („Element an Index p beziehungsweise q+1 und folgende“). Da »copy()« nur so viele Zeichen kopiert, wie in das Array passen, stimmt auch die Anzahl der tatsächlich kopierten Zeichen.
Anschließend läuft die For-Schleife ab Zeile 38 durch die zwei Arrays, entfernt dabei jeweils das kleinere aktuelle Element und bricht ihren Lauf ab, falls eines der Felder aufgebraucht ist. Die restlichen Elemente des anderen Arrays kopiert dann eine der beiden For-Schleifen ab Zeile 49 beziehungsweise 54 ins Ergebnis-Array.
Der Hauptfunktion »mergesort()« ab Zeile 15, die das Feld sowie die Indexpositionen von Anfang und Ende entgegennimmt, bleibt nur noch, das ihr übergebene Array in zwei Teile zu zerlegen, sich selbst rekursiv auf die beiden Teilfelder aufzurufen und die beiden Ergebnisse mit »merge()« zusammenzufügen. Die Rekursion wiederholt sich so lange, bis »mergesort()« ein Array mit nur einem Element erhält (dann ist »p == r« und damit die If-Bedingung falsch) und »mergesort()« einfach zurückkehrt. Abriert bildung 8 zeigt, wie der Algorithmus schrittweise ein Feld mit sieben Ganzzahlen sortiert.

Eingebaut

Im Normalfall muss allerdings in Go niemand Sortieralgorithmen von Hand kodieren. Die Sprache bietet eingebaute Sortierfunktionen für String- und Integeroder Float-Slices. Nach dem Importieren des »sort«-Pakets (Listing 6) stehen »sort.Ints()«, »sort.Float64s« sowie »sort. Strings()« bereit, die jeweils ein Slice von Ganz- oder Fließkommazahlen respektive Zeichenketten in eine aufsteigende Reihenfolge bringen, indem sie die Arrays jeweils in-place sortieren.
Wie man im Quellcode [4] auf der Go-Webseite nachlesen kann, nutzt die Sprache dazu den Quicksort-Algorithmus. Dabei handelt es sich um einen Teile-undherrsche-Mechanismus, der fast durchgehend rasend schnell arbeitet. Meist kommt er in nur O(n*log(n)) Schritten ans Ziel. In seltenen Fällen flippt er allerdings total aus und braucht dann sagenhafte O(n²) Schritte – bei einer Million Einträgen macht das den Unterschied zwischen Sekunden und Jahren.
Muss der Algorithmus mit hundertprozentiger Sicherheit terminieren, erweisen sich andere Verfahren manchmal als vorteilhafter. Um entsprechende Ausreißer abzuwehren, bauen Standardbibliotheken von Programmiersprachen aber oft Verfahren ein, die den Algorithmus leicht abändern und so die Katastrophe abwenden.

Beliebige Daten sortieren

Verwöhnte Skriptjünger reiben sich die Augen: Das strenge Typsystem von Go erfordert einiges an Mehraufwand, um ein Array von beliebigen Daten zu sortieren. So erweist es sich als unmöglich, eine Sortierroutine zu definieren, die Arrays mit Elementen eines generischen Datentyps sortiert. Vielmehr muss der Programmierer explizit festlegen, wie Go Elemente vergleicht und vertauscht.

So definiert Listing 7 eine fiktive Datenstruktur »Record«, die lediglich einen Ganzzahlenwert als Attribut enthält. Um nun ein Array mit Elementen aus »Record«-Typen zu sortieren, muss der Programmierer Go beibringen,
n wie es die Länge des Arrays mit den Datentypen ermittelt,
n wie es zwei Elemente an den Positionen »i« und »j« miteinander vergleicht
n wie es zwei verschiedene Einträge miteinander vertauscht – eben alles, was eine Sortierfunktion intern so mit den Daten macht.
Dazu gibt es im Listing die Funktionen »Len()«, »Swap()« und »Less()«, denen der Programmierer jeweils einen Receiver vom Typ »Records« zuweist, also eines Arrays von »Record«-Typen. Die Länge des Arrays bestimmt er einfach mit der eingebauten Go-Funktion »len()«. Vertauscht werden zwei Elemente mit Gos praktischer Vertauschsyntax (»a,b = b,a«). Der Vergleich zweier Elemente erfolgt mit dem Kleiner-als-Operator »<«, wie Zeile 23 zeigt. Damit Go das Array in-place mit Quicksort sortiert, ruft Zeile 28 die Funktion »sort.Sort()« auf und übergibt ihr das Array mit den Record-Elementen. Das (korrekte) Ergebnis eines Aufrufs zeigt Listing 8.
Es zeigt sich, dass eine Sprache wie Go mit strenger Typprüfung etwas mehr Programmieraufwand erfordert als eine Skriptsprache, die klaglos Strings, Integer und Floats ohne Meckern gleichermaßen sortiert, oder der man einfach eine hausgemachte Sortierfunktion für selbstdefinierte Typen mitgeben könnte. Diesen Nachteil macht Go nicht nur durch seine hohe Verarbeitungsgeschwindigkeit wett, sondern auch durch die Tatsache, dass schon der Compiler bei versehentlichen Typfehlern meckert und nicht erst das Programm zur Laufzeit.

(uba/ jlu)

Infos

[1] Donald E. Knuth, „The Art of Computer Programming, Volume 3: Searching and Sorting“, 1998
[2] Cormen, Leiserson, Rivest, Stein, „Introduction to Algorithms“, 2003
[3] Countingsort: [https:// de. wikipedia. org/ wiki/ Countingsort]
[4] Sort-Funktionen in der Go Standard Library: [https:// golang. org/ src/ sort/ sort. go]
[5] Listings zu diesem Artikel: [http:// www. linux-magazin. de/ static/ listings/ magazin/ 2020/ 02/ snapshot/]

Der Autor

Michael Schilli arbeitet als Software-Engineer in der San Francisco Bay Area in Kalifornien. In seiner seit 1997 laufenden Kolumne forscht er jeden Monat nach praktischen Anwendungen verschiedener Programmiersprachen. Unter [mschilli@perlmeister.com] beantwortet er gerne Fragen.