©Prof. Dr. Andreas Solymosi

Sortierte Sequenzen erzeugen

Für das Mischen braucht man möglichst lange sortierte Teilsequenzen. Die maximale Durchschnittlänge von ca. 2n, die in einer Reihung mit gegebener Länge n erreicht werden kann, ergibt folgende Strategie:

Die ersten n Elemente werden eingelesen und in die Reihung von hinten nach vorne einsortiert. Von der Mitte an werden die Elemente gesenkt, damit eine Halde entsteht. Diesmal soll aber an der Spitze nicht das größte Element sondern das kleinste stehen (die Vergleiche im Senken werden gegenüber Halden_Sort umgekehrt).
Dieses muß (z.B. durch Rückruf) ausgegeben werden, bevor ein neues Element eingelesen und gesenkt (d.h. in die Halde einsortiert) werden kann.
Ist das eingelesene Element kleiner als das auf der Spitze, soll es gleich ausgegeben werden.
Sollte das eingelesene Element kleiner sein, als das zuvor ausgegebene, würde sie auf der Spitze der Halde landen und als nächstes ausgegeben werden. Damit wäre die aktuelle Teilsequenz beendet und eine neue angefangen. Um dies zu verhindern, soll es nicht in die aktuelle Halde einsortiert werden. Statt dessen wird sie hinten um eine Stelle verkürzt und hier eine neue Halde angefangen (wird nennen sie Ersatzhalde).
Der Prozeß setzt sich fort: Das Spitzenelement wird immer ausgegeben, bevor ein neues Element einsortiert wird. In welche Halde, hängt davon ab, ob es kleiner als die zuvor ausgegebene ist oder nicht. Im ersten Fall in die Ersatzhalde, im zweiten in die aktuelle.
Wenn die aktuelle Halde leer geworden ist, gibt es keine Elemente mehr, die nicht in die aktuelle Teilsequenz passen würden. Jetzt muß sie endgültig abgeschlossen und eine neue Teilsequenz angefangen werden: Die Reservehalde belegt jetzt die ganze Reihung, sie wird zur aktuellen erklärt. Ihr Spitzenelement ist das erste Element der neuen Sequenz.

generic
	type TElement is private;
	-- type TElement is range <>; -- nur fuer Testausgabe
	with function "<" (Links, Rechts: TElement) return Boolean;
	with procedure Lesen (X: out TElement); -- vom Eingabeband
	with function Ende return Boolean; -- end of file des Eingabebandes
	with procedure Schreiben (X: TElement); -- auf das Ausgabeband
	with procedure Ende_der_Sequenz; -- Signal nach aussen am Ende jeder Sequenz
procedure Sequenzen_erzeugen (Groesse: in Positive); -- erzeugt sortierte Sequenzen mit Hilfe zweier Haldenkanaele

procedure Sequenzen_erzeugen (Groesse: in Positive) is -- Groesse des Speicherplaztes
	subtype TIndex is Natural range 0 .. Groesse + 1; -- erster und letzter Platz technisch bedingt 
	type TReihung is array (TIndex range 1 .. Groesse) of TElement;
	Halde: TReihung;
	Element: TElement; -- das aktuelle Element
	Letztes: TElement; -- das letzte geschriebene Element
	Erstes: Boolean := True; -- noch kein Element wurde geschrieben
	Akt_Anfang: TIndex range Halde'Range := Halde'Last; -- Anfang der aktiven Halde
	Akt_Ende: TIndex := Halde'Last-1; -- Ende der aktiven Halde
	Ers_Anfang: TIndex range Halde'Range := Halde'Last; -- Anfang der Ersatzhalde
	Ers_Ende: TIndex := Halde'Last-1; -- Ende der Ersatzhalde
	-- Halde leer wenn Anfang > Ende
	function Akt_Leer return Boolean is -- aktive Halde leer
		begin return Akt_Anfang > Akt_Ende; end Akt_Leer;
	function Ers_Leer return Boolean is -- Ersatzhalde leer
		begin return Ers_Anfang > Ers_Ende; end Ers_Leer;
	function Halde_Voll (Anfang: TIndex) return Boolean is -- aktive oder Ersatzhalde (mit Anfang) voll
		begin return Anfang = Halde'First; end Halde_Voll;
	function Halde_Leer (Anfang, Ende: TIndex) return Boolean is -- nur fuer pre- und postcondition
		begin return Anfang > Ende; end Halde_Leer;
	function Ist_Halde (Anfang, Ende: in TIndex) return Boolean is -- nur fuer pre- und postcondition
	begin -- die for-Schleife erhoeht die Zeitkomplexitaet von n log n auf n**2; sie soll im Produkt auskommentiert werden:
		for I in Anfang .. Ende / 2 loop
			if Halde (2 * I) < Halde (I) then
				return False;
			end if;
		end loop;
		return True;
	end Ist_Halde;

	procedure Senken (Links, Rechts: in TIndex) is
	-- Halde (Links .. Rechts) wird durch das Senken des Elements Halde (Links - 1) zur Halde (Links - 1 .. Rechts) erweitert.
		Index: TIndex range Halde'Range := Links - 1; -- linke Grenze der neuen Halde
		Nachfolger: TIndex'Base range Halde'First .. 2 * Halde'Last := 2 * Index;
		Element_zu_senken: constant TElement := Halde (Index); -- neues Element
	begin
		-- precondition Links > Halde'First and Ist_Halde (Links, Rechts)
		loop -- variant Nachfolger > old Nachfolger
		exit when Nachfolger > Rechts; -- weil Nachfolger nicht existiert
			if Nachfolger < Rechts and then Halde (Nachfolger + 1) < Halde (Nachfolger) then -- groesseren Nachfolger oder Nachfolger+1 auswaehlen
				Nachfolger := Nachfolger + 1;
			end if;
		exit when Element_zu_senken < Halde (Nachfolger); -- Platz gefunden
			Halde (Index) := Halde (Nachfolger); -- hochruecken
			Index := Nachfolger; -- runtergehen
			Nachfolger := 2 * Index; -- linker Nachfolger, wenn existiert
		end loop;
		Halde (Index) := Element_zu_senken; -- Element einfuegen
		-- postcondition Ist_Halde (Links - 1, Rechts)
	end Senken;

	procedure Fuellen (Anfang, Ende: in out TIndex; Element: in TElement) is
	begin -- fuegt Element in die Halde (Anfang .. Ende) ein, indem sie entweder zu Halde (Anfang - 1 .. Ende) verlaengert oder das Spitzenelement ausgegeben wird 
		if Halde_voll (Anfang) then -- 
			Schreiben (Halde (Anfang));
		else -- Halde nicht voll
			Anfang := Anfang - 1; -- nach vorne verlaengern
		end if;
		Halde (Anfang) := Element; -- neues Element eintragen
		Senken (Anfang + 1, Ende);
	end Fuellen;

	procedure Entleeren (Anfang, Ende: in out TIndex) is
	begin -- gibt das Element Halde (Anfang) aus und erzeugt die Halde (Anfang .. Ende - 1), indem Halde (Ende) gesenkt wird
	-- precondition not Halde_Leer (Anfang, Ende) and Ist_Halde (Anfang + 1, Ende)
	-- nicht nach Haldenwechsel: precondition Ist_Halde (Anfang, Ende)
		Schreiben (Halde (Anfang));
		Halde (Anfang) := Halde (Ende) ; -- hinteres Element
		Ende := Ende - 1; -- Halde hinten verkuerzen
		Senken (Anfang + 1, Ende); -- in der verkuerzten Halde
	-- postcondition Ist_Halde (Anfang, Ende);
	end Entleeren;

begin -- Sequenzen_erzeugen
	while not Ende loop -- variant muss vom Benutzer durch Lesen gesichert werden
		Lesen (Element); -- Rueckruf
		if not Halde_voll (Akt_Anfang) then -- Halde noch nicht voll, aufbauen
			Fuellen (Akt_Anfang, Akt_Ende, Element);
		elsif Erstes or else not (Element < Letztes) then -- Element gehoert dieser Sequenz
			Erstes := False;
			if Element < Halde (Akt_Anfang) then -- sofort ausgeben
				Schreiben (Element);
				Letztes := Element;
			else -- wurde schon kleineres ausgegeben
				Letztes := Halde (Akt_Anfang); -- Element wird ausgegeben
				Fuellen (Akt_Anfang, Akt_Ende, Element); -- Fuellen ruft Schreiben auf, wenn Halde voll
			end if; -- nicht sofort ausgeben
		else -- Element gehoert der naechsten Sequenz, in die Ersatzhalde:
			Letztes := Halde (Akt_Anfang); -- Element wird ausgegeben
			if Akt_Leer then -- aktive Halde leer
				Ende_der_Sequenz; -- Signal nach aussen
				-- Halden tauschen:
				Akt_Ende := Ers_Ende; -- Ersatzhalde wird die aktive
				-- Akt_Anfang = ?
				Ers_Anfang := Ers_Ende + 1; -- neue Ersatzhalde wird leer
				-- Ers_Ende = ?
			end if; -- aktive Halde leer
			Entleeren (Akt_Anfang, Akt_Ende); -- in der Halde wird Platz gemacht: Entleeren ruft Schreiben auf und verkuerzt die aktive Halde
			Fuellen (Ers_Anfang, Ers_Ende, Element); -- die Ersatzhalde ist nie voll
		end if; -- naechste Sequenz
	end loop; -- Leseschleife

	-- alle Eingabedaten wurden eingelesen; zuerst aktive Halde abbauen:
	while not Akt_Leer loop -- variant Akt_Ende < old Akt_Ende
		Entleeren (Akt_Anfang, Akt_Ende);
	end loop;

	-- Ersatzhalde abbauen:
	Ende_der_Sequenz; 
	while not Ers_Leer loop -- variant Ers_Ende < old Ers_Ende
		Entleeren (Ers_Anfang, Ers_Ende);
	end loop;
	Ende_der_Sequenz; 
end Sequenzen_erzeugen;

Testprogramm:

with Text_IO, Sequenzen_erzeugen;
procedure Seq_Test is
	-- Testprogramm fuer das Paket Sequenzen_erzeugen
	type TDaten is new Integer;
	procedure Uebergeben (Daten: out TDaten);
	function Datenende return Boolean;
	procedure Uebernehmen (Daten: TDaten);
	procedure Umschalten; -- auf die naechste Sequenz

	procedure Ganzzahl_Sequenzen_erzeugen is new Sequenzen_erzeugen (
		TElement => TDaten,
		"<" => "<", -- fuer TDaten = Integer
		Lesen => Uebergeben,
		Ende => Datenende,
		Schreiben => Uebernehmen,
		Ende_der_Sequenz => Umschalten);

	type UEingabedaten is array (Positive range <>) of TDaten;
	Eingabedaten: constant UEingabedaten := 
		(13, -45, 32, -5, 22, 80, -32, 123, -65, 27,
		-23, 35, 37, -88, -77, -13, 37, 273, 35, 77,
		16, -35, 62, 58, -22, 47, -62, 126, 65, 21,
		-26, 55, 61, 88, -11, -16, 61, 216, 65, 11,
		-21, 15, 17, -44, -27, -11, 17, 271, 15, 97,
		19, -15, 66, 54, 22, -47, 52, -126, 35, 26,
		-16, 75, 68, 44, 11, 56, -61, -216, 95, 91,
		24, 15, 611, 188, 151, -106, 651, 266, -65, 111,
		21, -105, 157, -344, -127, 11, 107, 275, 151, 297,
		323, 38, 37, 344, 327, 333, 37, 273, 38, 97,
		109, -15, 56, 154, -22, 417, 5, 126, 35, 206,
		39, 338, 66, 84, 22, 347, 82, 26, 38, 26,
		336, 78, 68, 44, 33, 86, 363, 236, 98, 93,
		32, 40, 70, 10);
	Index: Natural range Eingabedaten'First - 1 .. Eingabedaten'Last := Eingabedaten'First - 1;
	Sequenz_Zahl: Natural := 0;
	Speicherplatzgroesse: Positive range 2 .. Positive'Last; -- wird eingelesen

	procedure Uebergeben (Daten: out TDaten) is
	begin -- variant Index > old Index
		Index := Index + 1;
		Daten := Eingabedaten (Index);
	exception
		when Constraint_Error => 
			Text_IO.Put_Line ("Lesefehler: Eingabedaten sind zu Ende");
	end Uebergeben; 
	function Datenende return Boolean is
		begin return Index = Eingabedaten'Last; end Datenende;
	procedure Uebernehmen (Daten: TDaten) is
		begin Text_IO.Put (TDaten'Image (Daten) & ", "); end Uebernehmen;
	procedure Umschalten is
	begin
		Sequenz_Zahl := Sequenz_Zahl + 1;
		Text_IO.Put_Line ("#"); -- "#" signalisiert Sequenzwechsel
	end Umschalten;

	package Int_IO is new Text_IO.Integer_IO (Integer);
begin -- Seq_Test
	Text_IO.Put ("Sortierte Sequenzen der Testfolge mit der Laenge von " & Natural'Image (Eingabedaten'Length));
	Text_IO.Put (" werden erzeugt. Bitte Speicherplatzgroesse (Ganzzahl > 1) eingeben: ");
	Int_IO.Get (Speicherplatzgroesse);

	Ganzzahl_Sequenzen_erzeugen (Speicherplatzgroesse); -- mit Rueckrufen
	Text_IO.Put_Line ("##"); -- "##" signalisiert das Ende der letzten Sequenz
	Text_IO.Put (Natural'Image (Sequenz_Zahl) & " Sequenzen mit der Durchschnittslaenge von ca. ");
	Text_IO.Put_Line (Natural'Image (Eingabedaten'Length / Sequenz_Zahl) & " wurden erzeugt.");
end Seq_Test;

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

Leitseite des Autors