© Prof. Dr. Andreas Solymosi

Sortierverfahren

mit konstanter Speicherkomplexität

Der Binärbaum-Sortieralgorithmus liest die zu sortierenden Daten aus einer Reihung, ordnet sie in einen Binärbaum ein und schriebt sie schließlich nach Größe geordnet in die Reihung zurück. Er braucht also zusätzlichen Speicherplatz: Seine Speicherkomplexität wächst mit der Menge der zu sortierenden Daten linear.

1. Quadratische Verfahren

Es gibt Sortieralgorithmen mit konstanter Speicherkomplexität: Der über die Speicherung der Eingabedaten hinausgehende Speicherbedarf wächst mit der Menge der Daten nicht. Der bekannteste ist der Blasensort: 

generic
	type TElement is private;
	with function "<" (Links, Rechts: TElement) return Boolean;
	type TIndex is range <>;
	type TDaten is array (TIndex) of TElement;
procedure GBlasen_Sort (Daten: in out TDaten);
procedure GBlasen_Sort (Daten: in out TDaten) is
begin
	for I in Daten'Range loop
		for J in Daten'Range loop
			if Daten (I) < Daten (J) then -- Vergleichen
				declare -- Austauschen
					Temp: constant TElement := Daten (I);
				begin
					Daten (I) := Daten (J);
					Daten (J) := Temp;
				end;
			end if;
		end loop;
	end loop;
end GBlasen_Sort;

Durch die geschachtelte Schleife ist es einleuchtend, daß in einer Reihung der Länge n die Anzahl der Vergleiche n2 beträgt. Optimierungen dieses Verfahrens und andere, ähnliche Verfahren ergeben zwar eine leichte Verbesserung, die Zeitkomplexität dieser Algorithmen bleibt aber O(n2).

Die obige Prozedurschablone braucht als Ausprägungsparameter den Reihungstyp TDaten. Dieser muß im Benutzerprogramm definiert und bei der Ausprägung übergeben werden. Eine Entwurfsalternative ist, eine Paketschablone zu vereinbaren, die diesen Datentyp selber exportiert. Der Benutzer muß ihn dann aus der Ausprägung importieren und seine Daten in ein Objekt dieses Typs abspeichern. Weil die Größe der Reihung erst im Benutzerprogramm bekannt wird, muß er das Paket einen uneingeschränkten Reihungstyp exportieren. Wir benutzen diese Technik bei der Erläuterung des Sortieralgorithmus direktes Einfügen :

generic -- Ausschnitt aus der Datei ALLESORT.ADS
	type TElement is private;
	with function "<" (Links, Rechts: TElement) return Boolean;
package GSort is
	type TIndex is new Positive;
	type UDaten is array (TIndex range <>) of TElement;
	procedure Direktes_Einfuegen (Daten: in out UDaten);
end GSort;
package body GSort is
	procedure Direktes_Einfuegen (Daten: in out UDaten) is
		Element_zum_einfuegen: TElement;
		Einfuegestelle: TIndex range Daten'Range; -- zum Suchen der Einfuegestelle
	begin -- Idee: Das Index-te Element (von der zweiten Stelle an bis nach Daten'Last) wird in die schon sortierte Teilsequenz 1 .. Index-1 
		-- eingefuegt. Die Einfuegestelle wird in der Teilsequenz 1 .. Index-1 gesucht und dabei wird jedes Element nach Daten'Last geschoben.
		for Index in TIndex'Succ (Daten'First) .. Daten'Last loop -- von der zweiten Stelle an
			Element_zum_einfuegen := Daten (Index);
			Einfuegestelle := Index; -- die Einfuegestelle wird von Daten'Last nach Daten'First in der sortierten 
				-- Teilsequenz 1 .. Index-1 gesucht:
			while Einfuegestelle > Daten'First and then 
					Element_zum_einfuegen < Daten (TIndex'Pred (Einfuegestelle)) loop
				Daten (Einfuegestelle) := Daten (TIndex'Pred (Einfuegestelle)); -- Hochschieben
				Einfuegestelle := TIndex'Pred (Einfuegestelle); -- weitergehen nach Daten'First
			end loop; -- Einfuegestelle gefunden: entweder weil Einfuegestelle = Daten'First 
				-- oder weil Element_zum_einfuegen >= Daten (Einfuegestelle - 1) 
			Daten (Einfuegestelle) := Element_zum_einfuegen;
		end loop; -- Index
	end Direktes_Einfuegen;
end GSort;

In der Datei ALLESORT.ADS befindet sich auch ein Testtreiber, in dem alle erwähnten Sortieralgorithmen ausgeprägt und aufgerufen werden.

Übung: Verbessern Sie den Blasensort indem Sie durch die geschachtelte Schleife nicht immer unbedingt n2 mal durch die Reihung laufen, sondern abbrechen, nachdem kein Austausch mehr stattgefunden hat.

Übung: Verbessern Sie das direkte Einfügen um das binäre Suchen, in dem die Suche nach der Einfügestelle in der sortierten Teilsequenz nicht sequentiell erfolgt, sondern durch wiederholtes Halbieren der Sequenz: 

while Links <= Rechts loop -- binaeres Suchen in der sortierten Teilsequenz
	Mitte := (Links + Rechts) / 2;
	if Element_zum_einfuegen < Daten (Mitte) then -- Vergleichen
		Rechts := TIndex'Pred (Mitte);
	else
		Links := TIndex'Succ (Mitte);
	end if;
end loop; -- Einfuegestelle gefunden: Links

2. Höhere Verfahren

Die höheren Sortierverfahren ermöglichen eine bessere Zeitkomplexität als O(n2). Eine der am häufigsten verwendeten Algorithmen ist der Shell-Sort . Er basiert auf der Idee einer Verbesserung vom direkten Einfügen. Dort wandern nämlich die Elemente in Einzelschritten auf ihren Platz. Hier führt man (abnehmende) Schrittweiten k1, k2, ... kt ein, und die Elemente springen Richtung Ihres zukünftigen Platzes um jeweils km Stellen. Zuerst werden also die Elemente untereinander sortiert, die k1 Stellen voneinander entfernt sind; dann diejenigen, die die Entfernung k2 zueinander haben, usw. Die letzte Schrittweite kt ist dabei immer 1, mit der die schon fast sortierte Sequenz endgültig sortiert wird:

procedure Shell_Sort (Daten: in out UDaten; Schrittweiten: in USchrittweiten) is
		-- Ausschnitt aus der Datei ALLESORT.ADS
	Einfuegestelle, K, S: TIndex;
	Element_zum_einfuegen: TElement;
	M: TIndex range Schrittweiten'Range; -- Schleifenvariable fuer die Schrittweiten
begin
	for M in Schrittweiten'Range loop -- in jedem Durchlauf ein Schrittweiten(M)-Sort
		K := Schrittweiten (M); -- aktuelle Schrittweite
		-- direktes Einfuegen mit Schrittweite K:
		for Index in Daten'First + K .. Daten'Last loop -- aussere Schleife des K-Sorts
			Element_zum_einfuegen := Daten (Index);
			Einfuegestelle := Index;
			while Einfuegestelle > Daten'First and then 
					Element_zum_einfuegen < Daten (Einfuegestelle - K) loop
				Daten (Einfuegestelle) := Daten (Einfuegestelle - K);
				Einfuegestelle := Einfuegestelle - K; -- naechstes zu vergleichendes Element
			end loop;
			Daten (Einfuegestelle) := Element_zum_einfuegen;
		end loop; -- for Index
	end loop; -- for M
end Shell_Sort;

Durch die geschickte Wahl der Schrittweiten kann der Sortieraufwand deutlich reduziert werden. Für die Schrittweiten S := (1, 3, 7, 15, 31, ...) wurde z.B. in [Kn] nachgewiesen, daß die Zeitkomplexität des Algorithmus O(n1.2) beträgt. In dieser Folge gilt: S (K + 1) = 2 * S (K) + 1 mit einer Länge von t = ë log2 nû -1, wo n die Länge der zu sortierenden Reihung ist und die Zeichen ë und û das Abschneiden von Dezimalstellen (die kleinste nicht größere ganze Zahl) bedeuten. Eine noch bessere Komplexität ergibt die Schrittweitenfolge S := (1, 4, 13, 40, 121, ... ) mit der Formel S (K + 1) = 3 * S (K) + 1 und einer Länge von t = ë log3 nû -1.

Es wurde mathematisch bewiesen, daß es keine Sortierverfahren mit linearer Zeitkomplexität geben kann, wenn auch sie mit besseren Schrittweitenfolgen beliebig angenähert werden kann.

3. Logarithmische Verfahren

Besser als O(n1+e ) für ein beliebig kleines e > 0 ist die Zeitkomplexität O(n log n). Sie kann durch die logarithmischen Verfahren erreicht werden. Der bekannteste von ihnen ist das rekursive Schnellsort. Die Idee hierbei ist, daß die Reihung in eine linke und eine rechte Hälfte geteilt wird. Durch Austausch wird dafür gesorgt, daß alle Elemente in der linken Hälfte kleiner werden, als alle Elemente in der rechten Hälfte. Anschließend können die linke Hälfte und die rechte Hälfte unabhängig voneinander auf dieselbe Weise sortiert werden, die dann zusammen eine sortierte Sequenz ergeben:

procedure Schnell_Sort (Daten: in out UDaten) is -- Ausschnitt aus der Datei ALLESORT.ADS
	procedure Sort (Links, Rechts: in TIndex) is
		Auf: TIndex range Daten'Range := Links; -- linke Grenze
		Ab: TIndex range Daten'Range := Rechts; -- rechte Grenze
		Mitte: constant TElement := Daten ((Links + Rechts) / 2); -- mittleres Element
		Temp: TElement;
	begin
		loop
			while Daten (Auf) < Mitte loop
				Auf := Auf + 1; -- suchen groesseres Element von links
			end loop;
			while Mitte < Daten (Ab) loop
				Ab := Ab - 1; -- suchen kleineres Element von rechts
			end loop;
			if Auf <= Ab then -- austauschen Auf und Ab:
				Temp := Daten (Auf);
				Daten (Auf) := Daten (Ab);
				Daten (Ab) := Temp;
				Auf := Auf + 1; -- linke und rechte Grenze verschieben:
				Ab := Ab - 1;
			end if;
		exit when Auf > Ab; -- Ueberschneidung
		end loop;
		if Links < Ab then 
			Sort (Links, Ab); -- sortiere linke Haelfte
		end if;
		if Auf < Rechts then
			Sort (Auf, Rechts); -- sortiere rechte Haelfte
		end if;
	end Sort;
begin -- der Prozedur Schnell_Sort
	Sort (Daten'First, Daten'Last); -- sortiere die ganze Sequenz
end Schnell_Sort;

Dieser Algorithmus hat die (durchschnittliche) Zeitkomplexität von O(n log n) , allerdings hat sich die Speicherkomplexität durch die rekursiven Aufrufe verschlechtert: Der notwendige Speicher im Systemstapel wächst mit der zu sortierenden Menge logarithmisch (der Speicherkomplexität des Baumsorts aus dem Kapitel 12.5.4. ist noch schlechter, nämlich linear).

Haldensort ist der eleganteste Algorithmus, der seine konstante Speicherkomplexität mit der logarithmischen Zeitkomplexität verbindet. Die Idee ist, innerhalb einer Reihung (indiziert mit Natural) einen Baum zu bilden. Die Rolle der Verweise übernehmen hier die Indizes. Der Index 1 repräsentiert die Wurzel des Baums. Für jeden Eintrag mit Index I befindet sich der linke Nachfolger am Index 2*I und der rechte Nachfolger am Index 2*I+1 - falls diese sich noch in der Reihung befinden. Im Gegensatz zum Baumsort im Kapitel 12.5.4. ist hier jedoch das größte Element an der Spitze des Baum (d.h. am Index 1) und für jeden Eintrag sind beide Nachfolger kleiner (oder gleich).

In der ersten Phase des Sortieralgorithmus wird zuerst ein solcher Baum (hier genannt: Halde) aufgebaut: Von der Mitte an nach vorne bis zum ersten Eintrag wird Schritt für Schritt dafür gesorgt, daß für jedes Element die Haldenbedingung erfüllt wird, d.h. keine der beiden Nachfolger dürfen größer sein als es. Wir sagen, daß jedes Element gesenkt wird. Schließlich entsteht in der ganzen Reihung eine Halde: Sein größtes Element befindet sich an der Spitze. In der zweiten Phase wird dieser mit dem hintersten Element ausgetauscht, kommt also auf seinen Platz. Der Baum wird hinten um eine Stelle verkürzt und das neu auf die Spitze getauschte Element wird soweit gesenkt, daß die Haldenbedingung wieder erfüllt wird. Das nächstgrößte Element geriet dadurch auf die Spitze, das wieder nach hinten getauscht werden kann. Am Ende der zweiten Phase ist die Reihung sortiert.

Im Einzelnen kann der Algorithmus folgendermaßen formuliert werden:

procedure Halden_Sort (Daten: in out UDaten) is -- Ausschnitt aus der Datei ALLESORT.ADS
	Links: TIndex range Daten'Range := Daten'First;
	Rechts: TIndex range Daten'Range := Daten'Last;
	-- Der Reihungsausschnitt Daten (A .. B) erfuellt die Haldenbedingung, wenn fuer jedes I mit 2*I+1 <= B gilt:
	-- Daten (I) > Daten (2*I) and Daten (I) > Daten (2*I+1)
	procedure Senken (Links, Rechts: in TIndex) is
		-- Die Halde Daten (Links .. Rechts) wird durch das Senken des Elements Daten (Links - 1)
		-- zur Halde Daten (Links - 1 .. Rechts) erweitert.		Index: TIndex range Daten'Range := Links - 1; -- linke Grenze der neuen Halde
		Nachfolger: TIndex range Daten'First .. 2 * Daten'Last := 2 * Index; -- linker Nachfolger
		Element_zu_senken: constant TElement := Daten (Index);
	begin
		loop
		exit when Nachfolger > Rechts; -- weil Nachfolger nicht existiert
			if Nachfolger < Rechts and then Daten (Nachfolger) < Daten (Nachfolger + 1) then 
				-- kleineren Nachfolger oder Nachfolger + 1 auswaehlen
			Nachfolger := Nachfolger + 1;
			end if;
		exit when Daten (Nachfolger) < Element_zu_senken; -- Platz gefunden
			Daten (Index) := Daten (Nachfolger); -- hochruecken
			Index := Nachfolger; -- runtergehen
			Nachfolger := 2 * Index; -- linker Nachfolger, wenn existiert
		end loop;
		Daten (Index) := Element_zu_senken; -- Element einfuegen
	end Senken;
begin -- Halden_Sort
	-- Halde aufbauen (die obere Haelfte Daten (Daten'Last/2+1 .. Daten'Last) erfuellt die Haldenbedingung immer):
	Rechts := Daten'Last;
	for Links in reverse 2 .. Rechts / 2 + 1 loop -- die untere Haelfte einzeln zur Halde hinzufuegen
		Senken (Links, Rechts);
	end loop; -- jetzt erfuellt die Reihung Daten (Daten'First .. Daten'Last) die Haldenbedingung
	-- Halde abbauen = Reihung sortieren:
	Links := Daten'First;
	for Rechts in reverse Links + 1 .. Daten'Last loop -- austauschen der aeusseren Elemente:
		declare 
			Groesstes_Element: constant TElement := Daten (Links); -- Spitzenelement der Halde
		begin
			Daten (Links) := Daten (Rechts); -- hinteres Element nach vorne
			Daten (Rechts) := Groesstes_Element; -- sortiertes Element nach hinten
		end; -- austauschen
		Senken (Links + 1, Rechts - 1); -- neues Element in der verkuerzten Halde senken
	end loop;
end Halden_Sort;

Auch der Multibehälter GSortier_Kanal in der Datei GSORTKAN.ADB wurde als ein fortschrittlicher Haldensortalgorithmus implementiert.

Übung: Ergänzen sie den Algorithmus Halden_Sort durch die Prüfung der Haldenbedingung nach jedem Austausch. Geben Sie die Sequenz nach jedem Austausch aus. Aktivieren Sie ihn in einem Testtreiber, in dem 8 Ganzzahlen sortiert werden. Identifizieren Sie in jeder ausgegebenen Sequenz die Halde und die sortierte Teilsequenz.

4. Messungen

Die Komplexität eines Algorithmus kann mathematisch analysiert oder mit einem Meßmodul gemessen werden. Im folgenden Beispiel wird die Anzahl der Vergleiche und der Austausche ermittelt. Hierzu werden die Daten dem Sortieralgorithmus nicht als Parameter übergeben, sondern im Meßmodul lokal gehalten. Der Algorithmus hat auf sie über Rückrufprozeduren Zugriff: 

-- Jede Sortierprozedur, die sich fuer die Messung qualifizieren will, muss folgenden Profil haben:
generic -- Ausschnitt aus der Datei SORTMESS.ADA
	type TElement is private;
	type TIndex is range <>;
	with function Datenlaenge return TIndex;
	with function Kleiner (Links, Rechts: TIndex) return Boolean; -- Vergleich, wird gemessen
	with procedure Austauschen (I, J: in TIndex); -- Austausch, wird gemessen
procedure GSort;
-- Messprozedur:
with GSort, Text_IO;
procedure Sort_Messung is
	-- Testdaten:
	type T is new Float; -- Datentyp der zu sortierenden Elemente, austauschbar
	Anzahl: constant := 10; -- Anzahl der zu sortierenden Elemente, austauschbar
	type TI is new Natural range 1 .. Anzahl;
	Daten: array (TI) of T := (1.1, 3.14, -32.0e5, 100.001, 1.1, 1.10, 3.141, -32.0e4, 100.0101, 1.11); 
	Vergleiche, Austausche: Natural := 0; -- Messdaten
	-- Rueckrufunterprogramme:
	function Datenlaenge return TI is
		begin return Daten'Length; end; 
	function Kleiner (Links, Rechts: TI) return Boolean is
	begin
		Vergleiche := Vergleiche + 1;
		return Daten (Links) < Daten (Rechts);
	end Kleiner;
	procedure Austauschen (I, J: in TI) is
		Temp: constant T := Daten (I);
	begin
		Daten (I) := Daten (J);
		Daten (J) := Temp;
		Austausche := Austausche + 1;
	end Austauschen;
	procedure Sort is new GSort (TElement => T, TIndex => TI,
		Datenlaenge => Datenlaenge, Kleiner => Kleiner, Austauschen => Austauschen);
begin
	Sort; -- Aufruf mit Rueckrufen
	Text_IO.Put_Line ("Messergebnisse: ");
	Text_IO.Put_Line ("Vergleiche = " & Natural'Image (Vergleiche));
	Text_IO.Put_Line ("Austausche = " & Natural'Image (Austausche));
end Sort_Messung;

Der Rumpf des Blasensorts, der nicht direkt sondern über Rückrufprozeduren auf die Daten zugreift, ist z.B.:

procedure GSort is -- Blasensort (bubble sort)
begin
	for I in TIndex range 1 .. Datenlaenge loop
		for J in TIndex range 1 .. Datenlaenge loop
			if Kleiner (I, J) then
				Austauschen (I, J);
			end if;
		end loop;
	end loop;
end GSort;

Ähnlich kann z.B. der Schnellsort verändert werden, wie dies in der Datei SORTMESS.ADA nachvollzogen werden kann.

Übung: Weisen Sie die Komplexitätsformel O(n2) durch Messungen nach: Zeigen Sie, daß eine doppelt, dreifach, ... zehnfach lange Sequenz ungefähr viermal, neunmal, ... hundertmal so viele Vergleiche bzw. Austausche braucht, um mit einem quadratischen Verfahren sortiert zu werden. Eine Verbesserung des Verfahrens (wie etwa "Schüttelsort" gegenüber "Blasensort", oder "binäres Einfügen" gegenüber "direktem Einfügen") ergibt zwar bessere Maßergebnisse, das Verhältnis wird aber nicht verändert.

Zeigen Sie auch, daß bei höheren Verfahren das Wachstum deutlich unter n2 bleibt.

© Prof. Dr. Andreas Solymosi

Rückmeldungen bitte an den Autor solymosi@tfh-berlin.de

Leitseite des Autors