Make your own free website on Tripod.com

Sortieren durch Einfügen

(Insertion Sort)

Ulrich Möller
DE 02
2004-05-26

Das sortieren durch Einfügen ist eine der elemtarsten Arten etwas zu sortieren. Das Prinzip ist denkbar einfach, die zu sortierenden Daten werden in zwei Felder unterteilt. Ein Sortiertes und ein Unsortiertes. Zu Beginn besteht das sortierte Feld aus z.B. einer Zahl. Bei jedem Durchgang wird nun die erste Zahl des Unsortiertes Feldes in das Sortierte an passender Stelle eingeordnet.

6		2	10	4	12	8

2	6		10	4	12	8

2	6	10		4	12	8

2	4	6	10		12	8

2	4	6	10	12		8

2	4	6	8	10	12

Dabei rutsch die "Grenze" (rot) immer um einen Schritt weiter, bis das gesammte Feld sortiert ist.

Umsetzung in POW!

MODULE sort;

IMPORT Display, Insertionsort;

IMPORT Display;
CONST cMax = 1000; (*Feldgröße*)

TYPE TInhalt = INTEGER;
       TFeld = ARRAY cMax OF TInhalt; (*ARRAY(Feld) - Name, Lange,Datentyp*)

PROCEDURE FuegeEin* (Inhalt:TInhalt; VAR Feld:TFeld; i:INTEGER);
BEGIN
   WHILE (i>0) & (Feld[i]>Inhalt) DO
      Feld[i+1]:=Feld[i];
      i :=i-1;
   END;
Feld[i+1]:=Inhalt;
END FuegeEin;

PROCEDURE EinSort* (VAR Feld:TFeld;letztes:INTEGER);
VAR grenze: INTEGER;
BEGIN
   FOR grenze:=2 TO letztes DO
     FuegeEin(Feld[grenze], Feld, grenze-1); (*verücken der Grenze*)
   END;

REPEAT UNTIL Display.KeyPressed();
END EinSort;

END sort.

Quellen

http://thema.aboutit.de/view.php?ziel=/thema/sortierverfahren/insertionsort.html
http://www.dbg.rt.bw.schule.de/lehrer/ritters/info/sort/direin.htm
http://studis.ch/sort/insertion1.html Rolke/ Sennholz: Grund- und Leistungskurs Informatik (1996), Cornelsen Verlag Berlin
Martin Reiser/ Niklaus Wirth: Programmieren in Oberon (1994), Addison Wesley (Deutschland) GmbH
Robert Sedgewick: Algorithmen in C++ (1992), Addison Wesley (Deutschland) GmbH