|
Beschreibung
. Die Daten werden mit einem rekursiven Verfahren (Divide & Conquer) anhand ihrer Bitstruktur sortiert.
. Daten mit gesetztem n-ten Bit kommen in die rechte Hälfte, die anderen in die linke; für beide Hälften wird das Verfahren rekursiv aufgerufen.
Programmcode
procedure RadixExchangeSort ( var f : TArray; HighIndex : integer ) : string;
function Bit ( z, b : integer ) : integer;
// liefert das Bit mit der Nummer b einer positiven Integerzahl
begin
result := ((z shr b) and 1) // Rausschneiden des Bits b aus der Zahl z
end;
procedure rRadixExchangeSort ( links, rechts, b : integer);
// rekursiver Teil des RadixExchangeSorts
var i, j : integer;
begin
if (links < rechts) and (b >= 0)
then begin
i := links;
j := rechts;
repeat
while (Bit (f[i], b) = 0) and (i < j) do inc (i);
while (Bit (f[j], b) = 1) and (i < j) do dec (j);
swap (f[i], f[j]);
until i = j;
// Korrigiere Spezialfall, daß alle Elemente nur in d. rechten Hälfte waren:
if Bit (f[rechts], b) = 0 then inc (j);
rRadixExchangeSort (links, j-1 , b-1);
rRadixExchangeSort (j, rechts , b-1);
end;
end; // rRadixExchangeSorts
begin // RadixExchangeSorts
rRadixExchangeSort (0, HighIndex, 30);
end; // RadixExchangeSorts
Aufwandsabschätzung
Aufwand:
. In jeder Ebene der Rekursion wird jedes Element betrachtet, d.h. n-Elemente.
. Die Rekursionstiefe hängt vom Wertebereich (signifikanten Bits) des Schlüssels ab, bei Integerzahlen im Bereich 1 - 100.000 beträgt die Rekusionstiefe ld (100.000) 17.
Daraus folgt der Aufwand , wobei N der Wertebereich ist. Da im Allgemeinen der Wertebereich wesentlich größer ist als die Anzahl der Elemente .
worst-case-Aufwand:
w.o.
Sortierdauer
|
