Effektives Programmieren (4): Daten sortieren mit dem Computer — Methoden, Techniken, Programme

Wie sortiere ich meine Daten am besten? Dieses Problem ist so alt wie der Computer, und entsprechend vielfältig sind die Lösungsvorschläge. Wir stellen Ihnen in mehreren Folgen die wichtigsten und bekanntesten Sortiermethoden und dazu jeweils ein entsprechendes Listing vor.

Wie oft haben Sie wohl schon ein Telefonbuch oder ein Adressenverzeichnis aufgeschlagen, um nach einem bestimmten Namen zu suchen? Eine Frage, die wohl kaum zu beantworten ist.

Es passiert alle Augenblicke, daß man etwa ein Lexikon zur Hand nimmt, um ein Fremdwort nachzuschlagen oder daß man den Fahrplan einer Buslinie nach der nächsten Abfahrtszeit durchsucht.

Stellen Sie sich jetzt einmal vor, Sie hätten ein Lexikon in der Hand, das nicht, wie üblich, in alphabetisch sortierter Form vorliegt, sondern alle Stichwörter völlig durcheinander enthält.

Sie werden wohl zugeben, daß sich die Suche nach einem bestimmten Wort nun als ziemlich hoffnungslos herausstellen wird.

Mit dieser Feststellung sind wir aber schon beim Thema.

Heutzutage wird die Verwaltung und Weiterverarbeitung großer Datenmengen fast ausschließlich von Computern vorgenommen. Alle Stichwörter eines Lexikons sind zum Beispiel in Großrechenanlagen gespeichert und werden vollelektronisch in den Satz gegeben.

Nun wird Datenverarbeitung aber nicht nur auf Großrechenanlagen durchgeführt, sondern auch durchaus auf Mikrocomputern; sei es als Kundendatei oder als elektronisches Notizbuch.

Die Notwendigkeit einer Ordnung in diesen Datenbeständen wurde schon zur Sprache gebracht. Uns soll nun in dieser Folge interessieren, was es für Methoden des Ordnens von Daten gibt.

Wir werden uns also im Laufe dieser Reihe mit den verschiedensten Sortieralgorithmen beschäftigen; angefangen beim Sortieren durch direktes Einfügen (straight insertion) bis hin zum schnellsten Algorithmus, der zur Zeit existiert, dem Sortieren durch Zerlegen (Quicksort).

Jede Sortiermethode soll dabei bis ins Detail erklärt werden, und Sie werden sehr schnell erkennen, daß Sortieren nicht gleich Sortieren ist.

Haben wir ein großes Variablenfeld angelegt, so gibt es generell zwei verschiedene Methoden beim Suchen eines bestimmten Elements:

1. Durchsuchen sämtlicher Elemente
2. binäre Suche

Die erste Methode ist uns klar. Hierbei werden einfach alle Elemente des Feldes vom Anfang bis zum Ende durchgekämmt, um das gewünschte herauszufinden. Bei der Geschwindigkeit, mit der ein Computer seine Variablenfelder durchgehen kann, müssen schon gewichtige Gründe für das Sortieren sprechen.

Diese Gründe gibt es auch. Einer davon ist das Verwalten großer Datenmengen.

Sortieren von Feldern

Auch ein »Superrechner« benötigt viel Zeit, um einige Millionen Daten durchzusehen. Dieser Zeitfaktor wird noch erhöht, wenn man nur nach bestimmten Teilen einer Datei suchen möchte, also nach bestimmten Buchstabenfolgen oder Zahlenkombinationen.

Gehen wir jetzt einmal davon aus, ein Feld wäre sortiert. Der Computer kann jetzt binär suchen, was selbst bei vielen tausend Elementen nur eine kurze Zeit benötigt. Unter binärer Suche versteht man folgendes: Wenn der Computer zum Beispiel nach einer bestimmten Zahl sucht, so geht er erst einmal zur Mitte des gesamten Feldes. Jetzt kann er anhand eines einfachen Größenvergleichs herausfinden ob die gesuchte Zahl in der einen oder in der anderen Hälfte des Feldes liegen muß. Hat er das herausgefunden, so wird diese Feldhälfte wiederum in der Mitte geteilt, und wieder wird festgestellt, in welcher Hälfte des Feldes die Zahl zu finden sein muß. Dies geht immer so weiter, bis nur noch zwei Zahlen übrigbleiben, von denen eine die gesuchte ist.

Diese Methode der binären Suche ist sehr effektiv und erlaubt selbst bei großen Datenmengen eine geringe Suchzeit. Ein kleines Rechenbeispiel:

Wir haben 100 Elemente und wollen eines davon binär suchen. Durch unser Suchsystem sinkt die Anzahl der zu durchsuchenden Elemente auf folgende Art und Weise: 100:50:25:13:8:4:2:1.

Dies war der ungünstigste Fall, bei dem sich der zu suchende Wert immer in der Hälfte des übriggebliebenen Feldes befand.

Bei 100 Elementen haben wir also maximal sieben Zugriffe, bis der Wert gefunden wird. Nun durchsuchen wir auf die gleiche Weise 1000 Elemente.

Es gilt jetzt die absteigende Reihe:
1000:500:250:125:63:32:16:8:4:2:1.

Wie Sie sehen sind nur drei Zugriffe hinzugekommen, obwohl sich die Anzahl der Elemente verzehnfacht (!) hat.

Mit der anderen Suchmethode hätten wir im Mittel 50 beziehungsweise 500 Zugriffe gehabt, wenn man davon ausgeht, daß die Auswahl gleichverteilt erfolgt. Es lohnt sich also bei größeren Feldern durchaus, diese vorher zu sortieren, wobei wir bei allen Sortiermethoden nur ein Ziel haben werden:

Die Zeit des Sortierens muß möglichst gering bleiben!

Maßgeblich für die Zeitdauer eines Algorithmus sind folgende zwei Kriterien:

1. die Anzahl der Vergleiche
2. die Anzahl der Bewegungen

Außer diesen generellen Kriterien werden wir auch feststellen, daß es eine Rolle spielt, in welcher Form das Feld vor dem Sortieren vorlag. Insgesamt kann man die Sortiermethoden in vier grobe Klassen unterteilen:

Jede dieser Sortiermethoden hat bestimmte Vorzüge und wiederum auch spezielle Nachteile. Das hängt, wie schon erwähnt, von der anfänglichen Struktur eines Feldes ab. Wir müssen an dieser Stelle zwischen drei verschiedenen Anfangszuständen unterscheiden:

1. Das Feld ist bereits sortiert
2. das Feld ist völlig unsortiert
3. das Feld ist genau entgegengesetzt sortiert.

Manche Sortieralgorithmen sind um so schneller, je sortierter ein Feld vorliegt. Bei anderen Algorithmen kann das genau umgekehrt sein. Quicksort ist zum Beispiel am effektivsten, wenn es sich um zufällig durchmischte Felder handelt.

Direktes Einfügen

Nun aber zu unserem ersten Sortieralgorithmus, einer Sortiermethode, die Ihnen auch im täglichen Leben sicherlich am geläufigsten ist.

Es handelt sich um das Sortieren durch direktes Einfügen (straight insertion). Die hochtrabende Bezeichnung beschreibt einen eigentlich ganz einfachen Vorgang: Sie haben ein Feld aus zufällig durchmischten Elementen. Das Sortierprogramm beginnt jetzt beim zweiten Element und vergleicht dies mit dem ersten; ist es kleiner, so wird getauscht. Die ersten beiden Elemente dieses Feldes sind also schon sortiert.

Jetzt wird das dritte Element geholt und mit dem zweiten verglichen. Ist es größer, so bleibt es an seinem Platz; ansonsten wird es in die Reihe der vorherigen an den richigen Platz geschoben und eingefügt.

Das geht weiter, bis zum letzten Element, und mit einem Durchlauf werden alle Variablen in aufsteigender Reihenfolge sortiert.

Dieses Sortieren wenden Sie zum Beispiel immer beim Kartenspielen an, wobei Sie Ihr Blatt systematisch durchgehen, alle verkehrt sitzenden Karten herausnehmen und an der richtigen Stelle einordnen.

In Listing 1 sehen Sie ein Programm abgedruckt, das für alle weiteren Sortierprogramme als Rahmen dienen soll. Es hat die Aufgabe, ein Feld zu erstellen und die Ausgabe auf Drucker oder Bildschirm festzulegen. Das Feld kann wahlweise zufällig oder von Hand bestimmt werden und besteht aus Stringvariablen der Länge 3.

10 rem erstellen eines feldes zum
20 rem sortieren.
30 rem das erstellen kann zufaellig
40 rem oder geziehlt (durch eingabe)
50 rem erfolgen.
60 rem
70 rem sortieralgorithmen erhalten die
80 rem zeilennummern von 10000 bis 50000
90 rem sie benoetigen jeweils diesen
99 rem vorspann zur ausfuehrung.
100 rem herstellung eines arrays:
110 rem arrayvariable      - a$
120 rem schleifenvariablen - x, y, z
130 rem hilfsvariablen     - b$, c$, d$
140 rem dreiecktausch mit  - s$
150 print"{clr}":clr
160 print"soll von {rvon}h{rvof}and oder {rvon}z{rvof}ufaellig erstellt":print
170 input"werden ";x$
180 if x$<>"h"and x$<>"z"then 150
190 if x$="h"then gosub 220:gosub 1000:goto 210
200 gosub 220:gosub 2000
210 goto 4000: rem weitermachen
220 rem anzahl der elemente bestimmen
230 print:input"anzahl der elemente ";a
240 if a>10000 then print:print"zu viele elemente": goto 230
250 if a<10 then print:print"zu wenige elemente":goto 230
255 dim a$(a)
260 input"{down}{down}{rvon}d{rvof}rucker oder {rvon}b{rvof}ildschirm ";y$
270 if y$<>"d"and y$<>"b"then 260
280 if y$="d"then d=4:goto 300
290 d=3
300 return
1000 rem eingabe von hand
1010 print"{clr}"
1020 print:print"sie muessen jetzt"a" elemente eingeben!":print:print
1030 print"jedes element besteht aus 3 zeichen.":print:print
1040 for x=1 to a
1050 print x". ";:input"element";a$(x)
1060 if len(a$(x))<>3 then 1050
1070 next x
1080 return
2000 rem zufaellige eingabe
2010 print"{clr}"
2020 print:print"es werden jetzt"a" elemente zufaellig":print:print"ausgewaehlt"
2030 print:print"jedes element besteht aus 3 zeichen.":print:print
2040 for x=1 to a
2050 a$(x)=""
2060 for y=1 to 3:a$(x)=a$(x)+chr$(int(rnd(ti)*25)+65):next y
2070 next x
2080 return
3000 rem zwischenausgabe der elemente
3010 for i=1 to a-9 step 10
3020 for j=i to i+9:print#1,a$(j)" ";:next j
3030 print#1:next i
3040 return
4000 rem weitermachen
4005 open 1,d
4010 print"{clr}ausgabe des erstellten feldes"
4020 print
4030 gosub 3000
4040 rem sortierung startet
4050 rem

In Listing 2 sehen Sie den Abschluß des Sortierprogramms. Alle Algorithmen sind nur mit diesen Rahmenprogrammen lauffähig.

50000 rem endebehandlung
50010 print#1
50020 gosub 3000
50030 print#1,a;" elemente"
50040 print#1:print#1:close 1
50050 end

Listing 3 schließlich zeigt ein Programm für das Sortieren durch direktes Einfügen. Wie Sie aus dem Listing erkennen können, ist es wichtig, daß das erste Element des Feldes nicht, oder als das absolut kleinste Element definiert wird, da es die letzte und höchste Vergleichstufe darstellt und somit nicht mehr vertauscht werden kann, da das Programm sonst über die Grenzen des Feldes hinaus arbeiten müßte. In unserem Fall ist dieses Element (A$(0)) ein Leerstring C").

10000 rem sortieren durch direktes
10010 rem einfuegen
10020 rem
10030 rem straight insertion
10040 for x=2 to a
10050 if a$(x)>=a$(x-1) then 10120
10060 rem einfuegen des elements
10070 x$=a$(x): for y=x-1 to 1 step-1
10080 a$(y+1)=a$(y)
10090 if x$<=a$(y-1) then 10110
10100 a$(y)=x$: goto 10120
10110 next y
10120 gosub 3000: rem ausgabe
10130 next x
10140 rem ende 

Bild 1 zeigt, wie Straight Insertion arbeitet. Die Elemente, die jeweils behandelt werden, sind unterstrichen.

Aus Bild 1 können Sie aber noch mehrere Informationen über den Sortieralgorithmus erhalten. Es wird zum Beispiel deutlich, daß das Sortieren durch direktes Einfügen bei a Elementen genau a-1 Elemente durchgehen muß, um vollständig zu arbeiten.

Diese Zahl ergibt für die Berechnung der Anzahl der notwendigen Vergleiche folgende Formel:

(a²+a)/4

Wir haben in unserem Beispiel (Bild 1) mit 10 Elementen gearbeitet. Die Anzahl der Vergleiche beträgt also nach dieser Formel 28.

Für die Anzahl der Bewegungen im Variablenfeld sieht die Sache folgendermaßen aus:

(a²+9a)/4

Hier kommen wir gar auf 48 Bewegungen innerhalb unserer 10 Feldelemente.

Diese Formeln lassen an sich gar nichts Schlimmes vermuten. Wenn wir sie jedoch einmal genauer unter die Lupe nehmen, so werden wir eine bestürzende Feststellung machen: beide Formeln haben im Nenner jeweils einen Faktor a² stehen.

Anders ausgedrückt heißt das; wenn wir die Anzahl der Elemente verdoppeln, vervierfacht sich die Anzahl der Bewegungen, der Vergleiche und ebenso natürlich die Sortierdauer.

Bei einer dreifachen Anzahl müssen wir schon neunmal (!) solange warten, wie zu Beginn.

Wie schon erwähnt, besteht das Ziel des effektiven Sortierens darin, die Zeitdauer möglichst gering zu halten. In der Praxis werden wir versuchen, die Anzahl der Bewegungen und Vergleiche auf ein Mindestmaß zu drücken, und wir werden erkennen, daß sich die Proportionalität von a zu a² auf a zu log₂ (a) (Logarithmus der Basis 2) vermindern läßt, wenn man entsprechende Algorithmen einsetzt.

Bubblesort

Nachdem wir einen sehr einfachen Algorithmus bereits kennengelernt haben, soll uns nun eine weitere, recht einfache Sortiermethode interessieren. Es handelt sich hierbei um ein Sortieren durch Austauschen.

Bubblesort zählt mit zu den bekanntesten Sortieralgorithmen und arbeitet nach folgendem Prinzip:

Wir fangen mit dem gesamten Variablenfeld an. Hier nehmen wir nun das erste Element und vergleichen es mit dem zweiten. Ist es größer, so wird getauscht; ansonsten bleiben die beiden Elemente, so wie sie sind, stehen. Jetzt gehen wir eine Position weiter und vergleichen das jetzige zweite Element (das auch das vorherige erste sein kann) mit dem dritten der Reihe und tauschen gegebenfalls aus. Das geht immer so weiter, bis zum Ende des Feldes.

Sie werden sicherlich erkannt haben, daß sich auf diese Weise das allergrößte Element immer weiter nach unten bewegt hat und nach Abschluß dieses Durchgangs an lezter Stelle zu finden (also bereits richtig einsortiert) ist.

Jetzt begrenzen wir also das gesamte Feld auf alle Variablen, bis auf die letzte (a = a-1) und wiederholen den Vorgang. Als Ergebnis steht nun das zweitgrößte Element an der vorletzten Stelle und wir vermindern die Gesamtzahl wiederum um 1.

Das geht so weiter, bis die Länge des Feldes auf 1 geschrumpft ist; wir also nur noch das kleinste Element übrig haben. Damit ist der Sortiervorgang beendet.

Der Name von Bubblesort kommt übrigens von der Eigenschaft dieses Verfahrens, die größten Elemente quasi bis ans Ende des Feldes »durchzuperlen«. Dreht man das Feld um und hat man die größten Elemente am Anfang, so kann man diese Bewegungen innerhalb der Variablen durchaus mit dem Aufsteigen von Blasen (»bubbles«) vergleichen.

Listing 4 zeigt das Programm für den einfachen Bubblesort-Algorithmus, und in Bild 2 können Sie wiederum einen Beispielausdruck mit 10 Elementen sehen. Der erste Unterschied zwischen Bubblesort und unserem vorherigen Straight Insertion wird sofort klar, wenn Sie sich die beiden Ausdrucke im Vergleich betrachten.

10000 rem sortieren durch austauschen
10010 rem
10020 rem
10030 rem bubblesort
10040 for x=a-1 to 1 step-1
10050 for y=1 to x
10060 if a$(y)<=a$(y+1)then 10080
10065 rem austauschen beider elemente
10070 s$=a$(y):a$(y)=a$(y+1):a$(y+1)=s$
10080 next y
10090 gosub 3000: rem ausgabe
10100 next x

Während sich das Feld bei Straight Insertion vom Anfang her aufbaut und beim kleinsten Element zu sortieren beginnt, fängt Bubblesort beim größten Element an und bringt dieses zuerst an dessen Platz.

Die Zeitbedingungen für Bubblesort sind denen von Straight Insertion ziemlich ähnlich. Auch hier haben wir den Faktor a² als zeitbestimmenden Faktor in den Formeln.

Die Formel für die Anzahl der Vergleiche lautet jetzt:

(a²-a)/2

Um die Anzahl der Bewegungen zu berechnen dient folgende Formel:

¾*(a²-a)

Bild 3 und 4 zeigen einen Programmablaufplan der beiden Sortiermethoden, so daß eine Umstellung auf andere Programmiersprachen kein Problem darstellen sollte.

An dieser Stelle wollen wir den ersten Abschnitt unserer Folge bereits beenden. Überlegen Sie sich bis zum nächstenmal, wie man Bubblesort vielleicht noch verbessern könnte; wir bringen dann nämlich eine Version, die einige Nachteile der jetzigen nicht mehr besitzt.

Oder vielleicht fallen Ihnen inzwischen auch einige Methoden zum günstigen Sortieren von Feldern ein?

Sicherlich werden Sie die eine oder andere Möglichkeit im Laufe unserer Reihe noch finden, wenn auch unter einem vielleicht noch unbekannten Namen.