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)

Insertion sort (sortieren durch einfügen)


1. Java
2. Viren



Beschreibung . Die Elemente werden der Reihe nach in eine bereits sortierte Folge eingetragen.
. Dazu wird in der bereits sortierten Folge die richtige Stelle zum Einfügen von rechts her gesucht und gleichzeitig die bereits eingetragenen Elemente um eins nach rechts verschoben.
. Das neue Element wird dann an der auf diese Weise freigewordenen Position eingefügt.

Programmcode
procedure InsertionSort ( var f : TArray; HighIndex : integer ) : string;

var i, j, v : integer;
begin
for i := 1 to HighIndex // äußere Schleife
do begin

v := f[i];
j := i;
while (j>0) and (f[j-1] > v) // innere Schleife (zum Einfügen)
do begin

f[j] := f[j-1];
dec (j)

end;
f[j] := v

end;
end; // InsertionSort

Aufwandsabschätzung

mittlerer-Aufwand:
. Die äußere Schleife wird n-1 mal durchlaufen.
. Die innere Schleife wird ½ * ½ (n-1) durchlaufen. (Im Mittel erwarten wir, daß das neue Element in die Mitte des soriterten Bereichs gehört.)
Daraus folgt der Aufwand .

worst-case-Aufwand:
. Die äußere Schleife wird n-1 mal durchlaufen.
. Die innere Schleife wird ½ (n-1) durchlaufen.
Daraus folgt der Aufwand .

best-case-Aufwand:
. Die äußere Schleife wird n-1 mal durchlaufen.
. Die innere Schleife wird 1 mal durchlaufen, da jedes neue Element schon am richtigen Platz steht, d.h. das Array war schon aufsteigend sortiert.
Daraus folgt der Aufwand . Sortierdauer

 
 




Datenschutz

Top Themen / Analyse
Weitere Tips:
Rechnerarchitekturunabhängigkeit
Was ist das DNS?
Paketorientierte Datenübertragung
Adressen
Magnetkarte und Chipkarte
Das hexadezimale System:
IMAP (Internet Message Access Protocol)
Drahtlose Netzwerke
Testen





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.