Startseite   |  Site map   |  A-Z artikel   |  Artikel einreichen   |   Kontakt   |  
  


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
indicator Weitere Tips:
indicator Rechnerarchitekturunabhängigkeit
indicator Was ist das DNS?
indicator Paketorientierte Datenübertragung
indicator Adressen
indicator Magnetkarte und Chipkarte
indicator Das hexadezimale System:
indicator IMAP (Internet Message Access Protocol)
indicator Drahtlose Netzwerke
indicator Testen


Datenschutz
Zum selben thema
icon Netzwerk
icon Software
icon Entwicklung
icon Windows
icon Programm
icon Unix
icon Games
icon Sicherheit
icon Disk
icon Technologie
icon Bildung
icon Mp3
icon Cd
icon Suche
icon Grafik
icon Zahlung
icon Html
icon Internet
icon Hardware
icon Cpu
icon Firewall
icon Speicher
icon Mail
icon Banking
icon Video
icon Hacker
icon Design
icon Sprache
icon Dvd
icon Drucker
icon Elektronisches
icon Geschichte
icon Fehler
icon Website
icon Linux
icon 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.
dsolution