Hoofdstuk 6 Programmeren in Pascal6.5 Sorteren.
Bekijk de volgende lijst met namen
|
|
New Genereert nieuwe data en initialiseert. De optie 'new' wisselt tussen random en aflopend. Size Wisselt tussen 10 en 100 balkjes. Genereert ook nieuwe data en initialiseert. Draw Tekent de balkjes opnieuw. Run Start het automatisch sorteren (klik op 'Step' om te pauzeren en 'Run' om weer verder te gaan). Step Voert één stap van het sorteerproces uit. |
In het volgende voorbeeld demonstreren we het met de namen uit paragraaf 6.5.1.
Daarbij begin je met het laatste en één-na-laatste woord of getal, en daarna vergelijk je het één-na-laatste en het twee-na-laatste woord of getal, en zo ga je steeds verder naar voren.
Als voorbeeld gaan we bij bovenstaande rij de woorden van achteren naar voren doorlopen, en zonodig steeds twee buur-woorden verwisselen.
Het vierde en vijfde woord staan in de juiste volgorde, die laten we dus staan.
Het derde en vierde woord staan in de verkeerde volgorde, die wisselen we dus om.
Het resultaat van deze Verwissel(3, 4)-bewerking zie je in de bovenste rij hier onder.
En ook hoe het verder gaat als je verder naar voren loopt.
Als je het eerste en tweede woord vergeleken hebt, en die eventueel verwisseld hebt, begin je weer bij de laatste twee. Zo ga je steeds verder.
Bij deze aanpak wordt bij elke doorgang van achteren naar voren de kleinste waarde steeds naar voren geschoven. Na de eerste doorgang ben je er zeker van dat het eerste woord ook werkelijk vooraan staat.
Na de tweede doorgang ben je er zeker van dat het tweede woord ook werkelijk op de tweede plaats staat.
Als je de linkerkant als boven ziet (je moet de figuur eigenlijk een kwart slag rechtsom draaien), dan borrelen de lichtste waarden als het ware als luchtbelletjes naar boven, vandaar de naam bubblesort.
Je kunt zien, dat vanaf de linkerkant het gesorteerde deel van de rij toeneemt; dat gedeelte van de rij is met een kleurtje aangegeven.
Als er bij een bepaalde doorgang geen enkele verwisseling plaats vind is de rij gesorteerd, en dan is het klaar.
We zetten nu eerst in een structuurdiagram wat er in grote lijnen moet gebeuren:
Nu gaan we het eerste deelprobleem (namen invoeren) verfijnen.
We weten niet hoeveel namen er zullen worden ingevoerd, we gaan ervan uit dat er telkens een naam wordt ingevoerd. En als er op een gegeven moment, in plaats van het invoeren van een naam, direkt op enter wordt gedrukt (de naam is dan dus de lege string) nemen we aan dat er gestopt wordt met het invoeren van namen.
Dan moet dus het volgende gebeuren, in een structuurdiagram genoteerd:
Het tweede deelprobleem (sorteren) bestaat uit meer stappen als we het gaan verfijnen.
We gaan niet direkt tot in de finesses verfijnen, we doen het weer in etappes.
Eerst verfijnen we het als volgt:
Het deelprobleem: Maak een doorloop enz..... gaan we nu verder verfijnen.
In een structuurdiagram wordt dat het volgende:
Het deelprobleem: Verwissel (teller-1, teller) moeten we ook nog in stapjes verdelen.
Als je de inhoud van twee variabelen a en b wilt verwisselen, dan kan dat niet met de opdrachten:
a := b;
b := a;
Want stel je voor dat a het woord mies bevat, en b het woord aap.
Dan zal na de opdracht a := b de variabele a het woord aap bevatten, en b bevat ook nog steeds het woord aap.
En dan ben je het woord mies kwijt!
En na de volgende opdracht b := a zal de variabele b het woord aap bevatten, en a bevat ook het woord aap.
Dan zijn ze dus niet verwisseld.
Je hebt een extra hulpvariabele nodig, waarin het eerste woord wordt bewaard.
Het moet als volgt:
hulp := b;
b := a;
a := hulp;
b := a;
a := hulp;
Het laatste deelprobleem (de gesorteerde lijst) kun je vast zelf wel verfijnen.
Nu gaan we het struktuurdiagram omzetten in een programma.
Van elke deelprobleem, dat we hebben verfijnd in een nieuw struktuurdiagram, maken we een procedure.
We voegen de header toe, en de declaraties. En dan krijgen we het volgende programma:
program bubblesort;
var aantal: integer;
namen: array [1..100] of string;
procedure invoeren;
var naam: string;
i: integer;
begin
{de teller krijgt eerst de waarde 1}
i:=1;
{de variabele naam moet een (willekeurige) waarde krijgen
want als naam gelijk is aan de lege string zal de
while-lus direkt stoppen}
naam:="test";
while naam<>"" do
begin
write("Geef naam nummer ",i:2," ");
readln(naam);
namen[i]:=naam;
{voor het vervolg de letter met 1 ophogen}
i:=i+1;
end;
{als er gestopt wordt is het aantal namen gelijk aan i-1}
aantal:=i-1;
end;
procedure verwissel(var a:string; var b:string);
var hulp: string;
begin
hulp:=a;
a:=b;
b:=hulp;
end;
procedure maakdoorloop(var ietsverwisseld:boolean);
var i: integer;
begin
ietsverwisseld:=false;
for i:=aantal downto 2 do
begin
if (namen[i-1]>namen[i] ) then
begin
verwissel(namen[i-1],namen[i]);
ietsverwisseld:=true;
end;
end;
end;
procedure sorteer;
var ietsverwisseld: boolean;
begin
repeat
maakdoorloop(ietsverwisseld)
until (ietsverwisseld=false);
end;
procedure drukaf;
var i:integer;
begin
writeln;writeln;writeln("de gesorteerde lijst:");
for i:=1 to aantal do
writeln(namen[i]);
end;
begin
invoeren;
sorteer;
drukaf;
end.en als we het programma dan uitvoeren kan het volgende verschijnen:
6.5.3. Het selectionsort-algoritme
Bij de selectionsort-methode zoek je eerst het kleinste element van de rij met woorden (of getallen)
op. En dat kleinste element verwissel je dan met het eerste woord of getal van de rij.Vervolgens zoek je het kleinste element vanaf het tweede woord (of getal) op. En dat kleinste element verwissel je dan met het tweede woord of getal van de rij.
En zo ga je steeds verder.
Steeds zoek je het kleinste element op van het nog ongesorteerde deel van de rij, en dat kleinste element verwissel je dan met het éérste element van het nog ongesorteerde deel van de rij.
Op die manier vergroot je het gesorteerde deel steeds met één element.
Je bent klaar als alles-min-één gesorteerd is, want als je bij de laatste twee bent aangekomen wordt de kleinste van die twee op de één na laatste plaats gezet, en dan staat de grootste dus automatisch achteraan.
Hier onder zie je een applet (gemaakt door Robert Lafore), waarin dat gedemonstreerd wordt.
|
New Genereert nieuwe data en initialiseert. De optie 'new' wisselt tussen random en aflopend. Size Wisselt tussen 10 en 100 balkjes. Genereert ook nieuwe data en initialiseert. Draw Tekent de balkjes opnieuw. Run Start het automatisch sorteren (klik op 'Step' om te pauzeren en 'Run' om weer verder te gaan). Step Voert één stap van het sorteerproces uit. |
In het volgende voorbeeld demonstreren we het met de namen uit paragraaf 6.5.1.
Je begint als volgt:
Het resultaat van deze Verwissel(1,4)-bewerking zie je in de bovenste rij hier onder.
En ook hoe het verder gaat.
Het donker gearceerde geeft steeds de volgende gevonden kleinste waarde aan.
Het oranje gearceerde geeft steeds de het al gesorteerde deel aan.
We zetten nu eerst in een structuurdiagram wat er in grote lijnen moet gebeuren, dat is eigenlijk het zelfde als in de vorige paragraaf:
De verfijning van het eerste deelprobleem (namen invoeren) en van het laatste deelprobleem (gesorteerde lijst afdrukken) gaat net zo als in de vorige paragraaf.
Het tweede deelprobleem (sorteren) gaan we ook nu niet direkt tot in de finesses verfijnen, we doen het weer in etappes.
Eerst verfijnen we het als volgt:
Het deelprobleem Zoek de kleinste vanaf teller gaan we nu verder verfijnen.
In een structuurdiagram wordt dat het volgende:
Het deelprobleem: Verwissel de kleinste met het woord op plaats teller hebben we in de vorige paragraaf al besproken.
Nu gaan we het struktuurdiagram omzetten in een programma.
Van elke deelprobleem, dat we hebben verfijnd in een nieuw struktuurdiagram, maken we weer een procedure.
We voegen de header toe, en de declaraties. En dan krijgen we het volgende programma:
program selectionsort;
var aantal: integer;
namen: array [1..100] of string;
procedure invoeren;
var naam: string;
i: integer;
begin
{de teller krijgt eerst de waarde 1}
i:=1;
{de variabele naam moet een (willekeurige) waarde krijgen
want als naam gelijk is aan de lege string zal de
while-lus direkt stoppen}
naam:="test";
while naam<>"" do
begin
write("Geef naam nummer ",i:2," ");
readln(naam);
namen[i]:=naam;
{voor het vervolg de letter met 1 ophogen}
i:=i+1;
end;
{als er gestopt wordt is het aantal namen gelijk aan i-1}
aantal:=i-1;
end;
procedure verwissel(var a:string; var b:string);
var hulp: string;
begin
hulp:=a;
a:=b;
b:=hulp;
end;
procedure zoekkleinste(teller:integer; var nummerkleinste: integer);
var i: integer;
kleinste: string;
begin
kleinste:=namen[teller];
nummerkleinste:=teller;
for i:=teller to aantal do
begin
if (namen[i]<=kleinste ) then
begin
kleinste:=namen[i];
nummerkleinste:=i;
end;
end;
end;
procedure sorteer;
var i, nummerkleinste: integer;
begin
for i:=1 to aantal-1 do
begin
zoekkleinste(i,nummerkleinste);
verwissel(namen[i],namen[nummerkleinste]);
end;
end;
procedure drukaf;
var i:integer;
begin
writeln;writeln;writeln("de gesorteerde lijst:");
for i:=1 to aantal do
writeln(namen[i]);
end;
begin
invoeren;
sorteer;
drukaf;
end.en als we het programma dan uitvoeren kan het volgende verschijnen:
Opgaven.
Maak nu opgave 18 van hoofdstuk 6 (Pascal)
Maak nu opgave 18 van hoofdstuk 6 (Pascal)
