| | |
| Titel: | Sortieralgorithmen | |
| Startseite english | ||
| ||
| |<< Anfang < Zurück Index Weiter > Ende >>| | |  |
Radix Exchange Sort (Sortieren durch rekursiven Bitvergleich)
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
Zurück zu Themenseiten:
StudyPaper.com/Startseite/Computer/Informatik
StudyPaper.com/Startseite/Wissenschaft/Wirtschaftswissenschaften
StudyPaper.com/Startseite
Das Setzen von Verweisen (Links) auf diese Seite ist gestattet und bedarf keine vorherige Absprache.
