[Delphi] Sortieren durch binäres Einfügen

[derBenny]

Ich habe eine kleine Frage bezüglich dem Thema Sortieralgorithmen. (Delphi)

Folgendes: Wir sollen für den Informatikunterricht vier verschiedene Arten von Sortieralgorithmen programmieren und testen. Drei davon habe ich schon fertig, aber einer macht mir Probleme. Hier mal die Erklärung, die auf dem Aufgabenzettel dazu stand:

SORTIEREN DURCH BINÄRES EINFÜGEN:
Beim binären Einfügen wird die vorhandene Ordnung der Ziel-Sequenz ausgenutzt. Dabei wird in der Mitte der vorhandenen Sequenz geprüft, ob das einzusortierende Element links oder rechts zu sein hat. Es wird um so weiter halbiert, bis die Einschubstelle gefunden wurde.

...

Es geht darum, eine zufällige Anzahl (<= 10000) zufälliger Werte in der richtigen Reihenfolge in ein Array (1 - 10000) einzuordnen. Mit den drei anderen Verfahren habe ich es wie gesagt geschafft, aber das "Sortieren durch binäres Einfügen" macht mir leider Schwierigkeiten.

Das Prinzip der Intervallhalbierung verstehe ich zwar, aber ich bekomme es nicht hin, den Algorithmus in Delphi umzusetzen. Kann mir vielleicht jemand helfen?

[Jesus_666]

Klingt für mich nach Mergesort. Bei Mergesort geht es darum, daß du das Array solange rekursiv in Unterarrays teilst, bis du einzelne Elemente hast. Dann baust du das Ganze wieder zusammen. Wenn du zwei Unterarrays zusammenbaust, dann prüfst du, ob das letzte Element des einen Unterarrays kleiner ist als das erste Element des anderen und klebst sie entsprechend zusammen.
Wenn ich seit dem Sommersemester nichts veressen habe sollte das schon der ganze Algorithmus sein.


Der Algorithmus sieht in etwa so aus (Achtung, rekursiv):

Code:

array Mergesort(array A)
  WENN A nur ein Element beinhaltet
    Gebe A zurück
  SONST
    Teile A in zwei möglichst gleich große Unterarrays Au1 und Au2
    Mergesort(Au1)
    Mergesort(Au2)
    WENN (Au1[letzter] < Au2[erster])
      array Ergebnis = concat(Au1, Au2) // Hänge Au2 an Au1 an
    SONST
      array Ergebnis = concat(Au2, Au1) // Hänge Au1 an Au2 an
    Gebe Ergebnis zurück

Mit etwas Kenntnis deiner Sprache sollte es damit kein Problem sein, Mergesort zu implementieren.

[derBenny]

Danke für die Hilfe.
Das ist zwar nicht das Verfahren, dass ich gesucht habe, aber sicher auch eine gute Möglichkeit. Ich wußte gar nicht, dass man die concat-Funktion auch auf Arrays anwenden kann.

Wie auch immer, ich habe es jetzt doch geschafft, das Sortierverfahren sozusagen auf Papier zu bringen. Getestet habe ich es zwar noch nicht, weil ich keinen Compiler habe, aber es sollte theoretisch funktionieren. Für diejenigen, die es interessiert, hier der Quellcode:

Code:

// nliste (Liste nachher) und vliste (Liste vorher) sind global
var i, sortierte_werte, marke, intervallbreite, zwischenspeicher_1, zwischenspeicher_2: integer;
	begin
	for i := 1 to anzahl do // nliste auf Null setzen
		begin
		nliste[i] := 0;
		end;
	nliste[1] := vliste[1];	// Die ersten zwei Werte verteilen.
	if (vliste[2] >= vliste[1]) then nliste[2] := vliste[2];
	else
		begin
		nliste[2] := vliste[1];
		nliste[1] := vliste[2];
		end;
	sortierte_werte := 0;
	while (nliste[sortierte_werte + 1] <> 0) do // Sortierte Werte zählen
		begin
		inc(sortierte_werte);
		end;
	for i := 1 to anzahl do
		begin
		marke := Round(sortierte_werte / 2)
		intervallbreite :=  Round(sortierte_werte / 2);
		repeat
			if (vliste[i] < nliste[marke]) then
				begin
				intervallbreite := Round(intervallbreite / 2);
				marke := marke - intervallbreite;
				end;
			else
				begin
				intervallbreite := Round(intervallbreite / 2);
				marke := marke + intervallbreite;
				end;
		until ((nliste[marke] <= vliste[i]) and (nliste[marke + 1] >= vliste[i])) or (marke = 0) or (marke = 10001);
		zwischenspeicher_1 := nliste[marke]	// alten Wert zwischenspeichern
		nliste[marke] := vliste[i];	// neuen Wert einfügen
		while (nliste[zwischenspeicher_1] <> 0) do	// Werte verschieben
			begin
			zwischenspeicher_2 := nliste[marke + 1]
			nliste[marke + 1] := zwischenspeicher_1;
			zwischenspeicher_1 := zwischenspeicher_2;
			inc(marke);
			end;
		end;

[Jesus_666]

Danke für die Hilfe.
Das ist zwar nicht das Verfahren, dass ich gesucht habe, aber sicher auch eine gute Möglichkeit. Ich wußte gar nicht, dass man die concat-Funktion auch auf Arrays anwenden kann.

...

Ich wußte gar nicht, daß sie überhaupt existiert. Ich spreche kein Delphi und habe an der Stelle nur zeigen wollen, daß zwei Arrays konkateniert werden - wie genau das geht habe ich nicht gesagt. Der Metacode hat mit Pascal nichts zu tun.