Insertion.Mod
Code: Select all
MODULE Insertion;
(*
Doel: Een array met getallen sorteren volgens het insertion algoritme gebruikmakend van pointers
Auteur: Nick De Frangh
Datum: 22-11-05
*)
IMPORT
In, OutExt;
TYPE
Getallenrij = POINTER TO Getal;
Getal =
RECORD
prev: Getallenrij;
getal : REAL;
next: Getallenrij;
END;
PROCEDURE LeesRij(VAR Lijst: Getallenrij);
(*
Omschrijving : Lees een rij getallen in
Parameters :
Lijst : De lijst waarin de getallen zullen worden ingelezen
Returntype : -
Algoritme : -
*)
VAR
Tempgetal: REAL;
Tempnode: Getallenrij;
First: Getallenrij;
BEGIN
In.Open();
In.Real(Tempgetal);
First := Lijst;
IF In.Done THEN
NEW(Tempnode);
Tempnode^.getal := Tempgetal;
Tempnode^.next := NIL;
Tempnode^.prev := NIL;
First^.next := NIL;
First^.prev := NIL;
First^.getal := Tempgetal;
ELSE
Lijst := NIL;
END;
In.Real(Tempgetal);
WHILE (In.Done) DO
NEW(Tempnode);
Tempnode^.getal := Tempgetal;
Tempnode^.next := NIL;
Tempnode^.prev := NIL;
WHILE (First^.next # NIL) DO
First := First^.next;
END;
First^.next := Tempnode;
Tempnode^.prev := First;
Tempnode^.next := NIL;
In.Real(Tempgetal);
END;
END LeesRij;
PROCEDURE DrukRij(Lijst: Getallenrij);
(*
Omschrijving : Print een rij getallen af
Parameters :
Lijst : De gesorteerde lijst die afgedrukt zal worden
Returntype : -
Algoritme : -
*)
VAR
First : Getallenrij;
BEGIN
First := Lijst;
OutExt.Color(3);
OutExt.String("De Geordende lijst volgens insertion sort is: ");
OutExt.Ln;
OutExt.String("---------------------------------------------");
OutExt.Ln;
OutExt.Color(8);
WHILE Lijst # NIL DO
OutExt.RealFix(Lijst^.getal, 3, 2);
OutExt.Ln;
Lijst := Lijst^.next;
END;
END DrukRij;
PROCEDURE Insert(VAR Lijst: Getallenrij;
Node1: Getallenrij;
Node2: Getallenrij);
(*
Omschrijving : De insertion zelf uitvoeren
Parameters :
Lijst : De lijst die gesorteerd wordt
Node1: Het getal dat ingevoegd moet worden
Node2: Het getal waarvoor het getal van Node1 moet worden geplaatst
Returntype : -
Algoritme : -
*)
VAR
Tempnode: Getallenrij;
First: Getallenrij;
BEGIN
NEW(Tempnode); (* maak een node aan met de getalwaarde van de node die ingevoegd moet worden *)
Tempnode^.prev := NIL;
Tempnode^.next := NIL;
Tempnode^.getal := Node1^.getal;
First := Lijst; (* ga opzoek naar de node waarvoor de Tempnode moet worden ingevoegd *)
WHILE First # Node2 DO
First := First^.next;
END;
IF First = Lijst THEN (* het getal moet op de eerste plaats gezet worden *)
First^.prev := Tempnode;
Tempnode^.next := First;
Lijst := Tempnode;
ELSE (* het getal moet ergens anders ingevoegd worden *)
First^.prev^.next := Tempnode;
Tempnode^.prev := First^.prev;
First^.prev := Tempnode;
Tempnode^.next := First;
END;
First := Lijst; (* ga opzoek naar de node die ingevoerd moest worden en laat deze overslaan *)
WHILE First^.next # Node1 DO
First := First^.next;
END;
IF First^.next^.next = NIL THEN (* controleer of Node1 de laatste node is of niet *)
First^.next^.prev := NIL;
First^.next := NIL;
ELSE (* Als Node1 niet de laatste node is *)
First^.next^.next^.prev := Node1^.prev;
First^.next := Node1^.next;
END;
END Insert;
PROCEDURE Insertion*;
(*
Omschrijving : De insertion sort procedure starten
Parameters : -
Returntype : -
Algoritme : Insertion Sort
*)
VAR
Lijst: Getallenrij;
Tempnode1, Tempnode2: Getallenrij;
insert: BOOLEAN;
First: Getallenrij;
BEGIN
NEW(Lijst);
Lijst^.next := NIL;
LeesRij(Lijst);
IF (Lijst = NIL) THEN
OutExt.Color(1);
OutExt.String ("De lijst is leeg");
ELSIF (Lijst^.next = NIL) THEN
DrukRij(Lijst);
ELSE
Tempnode1 := Lijst^.next;
WHILE (Tempnode1 # NIL) DO
First := Lijst;
Tempnode2 := Lijst;
insert := FALSE;
REPEAT
IF (Tempnode2^.getal > Tempnode1^.getal) THEN
Insert(Lijst, Tempnode1, Tempnode2);
insert := TRUE;
END;
Tempnode2 := Tempnode2^.next;
UNTIL (Tempnode2 = Tempnode1) OR (insert);
Tempnode1 := Tempnode1^.next;
END;
DrukRij(Lijst);
END;
END Insertion;
BEGIN
OutExt.Open();
OutExt.Clear;
END Insertion.Code: Select all
(*
Auteur: Nick De Frangh
Date: 24-11-05
Werkwijze:
Ik heb mijn vorige insertion sort module gebruikt en deze volledig opnieuw geschreven door gebruik te maken van pointers.
Ik heb voor de implementatie van de pointers een dubbel gelinkte niet circulaire lijst gebruikt aangezien deze volgens mij het
makkelijkst was om te implementeren.
De insertion sort werkt op dezelfde manier als in de vorige module:
Ik neem aan dat mijn eerste getal het voorlopig kleinste is
Dan vergelijk ik alle volgende getallen met hun voorgangers
Kom ik een getal tegen dat groter is dan mijn huidige getal, dan voeg ik mijn huidige getal in voor het getal dat net groter is.
Ik loop zo heel de lijst af tot ik aan het einde ben gekomen.
Algoritme: Insertion Sort
*)
Builder.Compile \ws
OutExt.Mod
Insertion.Mod
~
Builder.Compile \f*
System.Free
Insertion.Mod
OutExt.Mod
~
OutExt.Clear
Insertion.Insertion 1.2 45.3 0.33 5.21 8.2 -3.5 2.35 7.88 5.12 6.23 2.36 55.8 -5.66 0.0 6.66 3.2 1.5 5.5~
Insertion.Insertion ~
Insertion.Insertion 1~
Insertion.Insertion 2 1 2 3~
Insertion.Insertion 1 3 6 9 4 5~
Insertion.Insertion 1.5 2.3 1.5 1.6 1.7 1.5 1.3 2.4 0 1 0~
Insertion.Insertion 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0~
Insertion.Insertion 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15~
.
