Startseite   |  Site map   |  A-Z artikel   |  Artikel einreichen   |   Kontakt   |  
   
  •  
    Biologie
    Themen der Chemie
    Deutsch online artikel
    Englisch / Englische
    Franzosisch
    Geographie
    Geschichte
    Informatik
    Kunst
    Mathematik / Studium
    Musik
    Philosophie
    Physik
    Recht
    Sport
    Wirtschaft & Technik



    Biographie

    Impressum

informatik artikel (Interpretation und charakterisierung)

Radix exchange sort (sortieren durch rekursiven bitvergleich)


1. Java
2. Viren



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

 
 




Datenschutz

Top Themen / Analyse
Die erkenntnistheoretische Annahme
TCP/IP-
28-Nadeldrucker
Kommerzielle Software
Strings in Java
Chaotische Phänomene am Beispiel des Drehpedels
Anwendungen von VR
ZM4
Die fünf Formate der DVD
CGI-Skripte





Datenschutz

Zum selben thema
Netzwerk
Software
Entwicklung
Windows
Programm
Unix
Games
Sicherheit
Disk
Technologie
Bildung
Mp3
Cd
Suche
Grafik
Zahlung
Html
Internet
Hardware
Cpu
Firewall
Speicher
Mail
Banking
Video
Hacker
Design
Sprache
Dvd
Drucker
Elektronisches
Geschichte
Fehler
Website
Linux
Computer
A-Z informatik artikel:
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z #

Copyright © 2008 - : ARTIKEL32 | Alle rechte vorbehalten.
Vervielfältigung im Ganzen oder teilweise das Material auf dieser Website gegen das Urheberrecht und wird bestraft, nach dem Gesetz.