Sorteren

Inleiding

De pagina Sorteren beschrijft twee eenvoudige algoritmes om gegevens in stijgende of in dalende volgorde te rangschikken (sorteren).

Gegevens die bij elkaar horen worden meestal in lijsten (ook tabellen genaamd) opgeslagen. Denken we hier maar aan een lijst van leerlingen, een lijst van voetbalploegen, een lijst van renners… Volgende lijst houdt de gemiddelde maandtemperatuur bij geregistreerd in het jaar 2020 in De Bilt (Nederland).

Maand	Gemiddelde Temperatuur
1	6,2
2	7,2
3	6,8
4	11,1
5	13,1
6	17,5
7	17,0
8	20,4
9	15,2
10	11,3
11	8,9
12	5,5

Gegevens opgenomen in tabellen worden heel dikwijls gerangschikt. De lijsten van leerlingen en renners zullen wellicht alfabetisch worden gerangschikt op familienaam. De temperatuurgegevens werden in bovenstaande tabel gesorteerd volgens het nummer van de maand. We hadden natuurlijk ook de temperatuurgegevens in stijgende of in dalende volgorde kunnen sorteren. In dit laatste geval zouden de koudste en warmste maanden van het jaar onmiddellijk duidelijk worden. De keuze welk gegeven je sorteert hangt af van de manier waarop je de lijst wil bestuderen.

Elke programmeertaal biedt de mogelijkheid om gegevens die samenhoren in tabelvorm op te nemen. De tabel krijgt dan één naam (bijvoorbeeld temperatuur). Elk element in de tabel kan worden geadresseerd door middel van de plaats in de tabel (bijvoorbeeld temperatuur(4) verwijst naar het getal 11,1, temperatuur(9) verwijst naar het getal 15,2…). De plaats (ook index genaamd) van een element in de lijst, dat je wenst te gebruiken, wordt steeds tussen ronde haakjes geschreven.

Schermontwerp

Volgende afbeelding schetst de Graphical User Interface (GUI) die we voor het programma wensen te gebruiken:

De lijst Origineel bevat de originele gegevens die we wensen te sorteren. De tabellen SelectionSort en BubbleSort zullen de gesorteerde gegevens bevatten bekomen door enerzijds het selection sort-algoritme en anderzijds het bubble sort-algoritme. Om een bepaald algoritme uit te voeren moet op de groene bol (Sprite) bovenaan de lijst worden geklikt. De kleur van de bol wijzigt daarna naar rood. De gegevens onderaan de gesorteerde lijsten tonen de duurtijd om de gegevens in de tabel te rangschikken. 

Ontwikkeling van het Programma

De verschillende onderdelen van het programma zullen stapsgewijs worden opgebouwd.

Lijsten definiëren

 De categorie Variabelen bevat een keuzeknop Maak een lijst. Bij het indrukken van deze knop verschijnt een invulveld (Nieuwe lijstnaam) waarin de naam van de nieuwe lijst kan worden ingebracht. Zoals bij de definitie van variabelen kan men ook hier kiezen Voor alle sprites en Alleen voor deze sprite. De lijst Origineel zal natuurlijk beschikbaar moeten zijn Voor alle Sprites. De lijsten SelectionSort en BubbleSort worden beperkt tot de Sprite waartoe ze behoren.

Sprites definiëren

De groene knoppen boven de tabellen definiëren twee afzonderlijke Sprites. We kunnen deze Sprites ofwel tekenen of we kunnen deze Sprites selecteren uit de beschikbare Sprites (bijvoorbeeld Sprite Button1). De eerste knop hebben we benaamd als selectionsortKnop, de tweede knop krijgt dan de naam bubblesortKnop.

Klok variabelen

Onderaan elke gesorteerde lijst toont een variabele de werkelijke sorteertijd voor het betreffende algoritme. Hiervoor worden de variabelen t1 en t2 gereserveerd. Beide variabelen werden aangevinkt onder de lijst van variabelen. Deze variabelen slepen we naar de gewenste plaats op het speelveld. Door op de variabele te klikken kan de voorstellingswijze wijzigen.

De start van het programma

Wanneer op het groene vlaggetje wordt geklikt worden alle lijsten leeggemaakt en worden de variabelen t1 en t2 op nul geplaatst. Nadien wordt de lijst Origineel gevuld met de te sorteren gegevens (in ons voorbeeld duizend willekeurige gegevens gelegen tussen 1 en 10000).

De pseudocode ziet er als volgt uit:

Maak de lijst Origineel leeg
Maak de lijst SelectionSort leeg
Maak de lijst BubbleSort leeg
Plaats de variabele t1 op 0
Plaats de variabele t2 op 0
Repeat 1000 times
   Voeg willekeurig getal tussen 1 en 10000 toe aan de lijst Origineel
End Repeat

Dit resulteert in volgend programma:

Het leegmaken van een lijst gebeurt via de instructie . Een element wordt achteraan toegevoegd aan een lijst met de instructie .

Een sortering opstarten

Door een klik op het groene bolletje start het aangeklikte sorteeralgoritme (instructie ). Nadien wijzigt de kleur van het bolletje naar rood (instructie . Enkel als de lijst SelectionSort leeg is kunnen alle gegevens worden gekopieerd vanuit de lijst Origineel naar de lijst SelectionSort. Dit gebeurt via het script kopieerGegevens. Het sorteren zelf gebeurt in het script sorteerGegevens. De klok-variabele krijgt bij de opstart de waarde 0. Bij het beëindigen van het sorteerproces wordt de waarde van de klok-variabele gekopieerd naar de variabele t1.

Het programma ziet er als volgt uit:

Het blok kopieerGegevens is nu eenvoudig te begrijpen op basis van voorgaande bespreking:

De functie bepaalt de grootte van een lijst. De functie laat toe om een element uit de tabel te selecteren.

Het selection sort algoritme

Algoritme

Het selection sort-algoritme start bovenaan (variabele StartPositie) en zoekt de plaats (variabele PlaatsKleinste) van het kleinste getal in de lijst. De waarde van het kleinste getal (5,5) wordt dan omgewisseld met de waarde op de eerste plaats (6,2) in de tabel. Het kleinste getal staat dan zeker al bovenaan. Daarna wordt er gestart vanaf de tweede plaats (7,2) in de lijst en wordt andermaal de plaats gezocht van het kleinste getal (6,2). Dit getal wordt dan andermaal omgewisseld met het getal op de tweede plaats… Zo wordt voortdurend het kleinste getal naar de juiste plaats gebracht in de tabel. Indien er geen kleiner getal te vinden is dan het startgetal (bijvoorbeeld 6,8 op plaats 3) dan gebeurt er natuurlijk geen omwisseling. Het algoritme eindigt als we het voorlaatste getal als startgetal hebben gebruikt en een vergelijking hebben gemaakt met het laatste getal in de reeks.

Script SorteerGegevens

Volgende pseudocode toont de werking van het script sorteerGegevens:

Initialiseer StartPositie op 1
Repeat lengte van SelectionSort-1
   Zoek de plaats van kleinste element in tabel (PlaatsKleinste) startend vanaf StartPositie
   If PlaatsKleinste groter is dan StartPositie
      Verwissel element op PlaatsKleinste met element op StartPositie
   End If
End Repeat

zoekPlaatsKleinsteen verwisselGegevens zijn afzonderlijke scripts in het programma:

Het Scratch-programma is een vertaling van bovenstaande pseudocode:

script zoekPLaatsKleinste

Het script zoekPlaatsKleinste zoekt de plaats van het kleinste getal startend vanaf de StartPositie. De variabele PlaatsKleinste wordt eerst geïnitialiseerd met de plaats van de variabele StartPositie. Op deze plaats bevindt zich het voorlopig kleinste getal. Alle volgende elementen worden nu overlopen. Als er een kleiner getal voorkomt dan het voorlopig kleinste getal dan wordt de variabele PlaatsKleinste aangepast. De variabele Positie houdt dan bij met welk element in de tabel we bezig zijn.

Deze redenering zit vervat in volgend script:

Op het einde bevat de variabele PlaatsKleinste de plaats in de lijst waar het kleinste getal zich bevindt. Indien PlaatsKleinste groter is dan de StartPositie dan wisselen we beide getallen om.

Script verwisselgegevens

Om twee getallen om te wisselen moeten we steeds het eerste getal in een tijdelijke variabele bewaren (bijvoorbeeld variabele Tijdelijk). Pas daarna kan de plaats van het eerste getal worden opgevuld met het tweede getal. De variabele Tijdelijk wordt in de volgende stap overgebracht naar de plaats van het tweede getal.

Deze redenering zit vervat in volgend programma:

De vervang-instructie laat toe om een element in een tabel te vervangen door een andere waarde.

Het bubble sort algoritme

Algoritme

Het bubble sort-algoritme vergelijkt steeds twee opeenvolgende elementen in de lijst. Indien het volgende element kleiner is dan het voorgaande element dan worden beide elementen omgewisseld. Dit vergelijkingsproces eindigt natuurlijk bij het einde van de lijst (voorlaatste element in vergelijking met het laatste element). Dit proces herhaalt zich meerdere malen zolang de tabel niet is gesorteerd (zolang er omwisselingen tussen opeenvolgende elementen zijn gebeurd).

Als we het algoritme toepassen op bovenstaande tabel dan krijgen we volgende resultaten:

• het tweede element (7,2) is groter dan het eerste element (6,2): deze gegevens worden niet omgewisseld;
• Het derde element (6,8) is kleiner dan het tweede element (7,2): deze gegevens worden wel omgewisseld;
• Het volgende element (11,1) is groter dan het derde element (7,2): deze gegevens worden niet omgewisseld…

Het opstarten van het bubble sort-algoritme verloopt op dezelfde manier als besproken bij het selection sort-algoritme: het klikken op de groene Sprite kopieert de gegevens van de tabel Origineel naar de tabel BubbleSort.

Script Sorteergegevens

Indien er geen omwisselingen meer gebeuren bij het doorlopen van de lijst dan eindigt het algoritme. Hiervoor maken we gebruik van een variabele Gesorteerd. Het script vergelijkGegevens zet deze variabele op Neen bij het omwisselen van twee getallen. Indien er geen omwisselingen gebeuren dan behoudt deze variabele de oorspronkelijke waarde Ja. De lus eindigt als de variabele Gesorteerd nog steeds op Ja staat. De variabele Gesorteerd wordt aangeduid als een Booleaanse variabele. Een Booleaanse variabele kan slechts twee mogelijke waarden (Ja en Neen of True en False) aannemen.

Script vergelijkGegevens

Het script vergelijkGegevens zet de variabele Gesorteerd eerst op Ja. Nadien vergelijken we elk element in de tabel (variabele Positie) met het volgende element in de tabel. Indien het volgende element kleiner is dan het eerste element dan worden beide elementen omgewisseld en wordt de variabele Gesorteerd op Neen geplaatst.

De pseudocode is nu gemakkelijk te begrijpen:

Plaats Gesorteerd op Ja
Plaats Positie op 1
Repeat until Positie = Lengte van de tabel BubbleSort
   Indien element op plaats Positie+1 < element op plaats Positie
      Wissel beide elementen om
      Plaats Gesorteerd op Neen
   End If
   Verhoog Positie met 1
End Repeat

Het Scratch-programma ziet er dan als volgt uit:

Het script verwisselGegevens is identiek met de procedure voorgesteld bij de bespreking van het selection sort-algoritme.

Snelheid

De kloktijden, aangeduid door de variabelen t1 en t2, tonen de snelheid van het sorteerproces. Bovenstaande schermafdruk duidt aan dat het selection sort-algoritme tot heel wat betere resultaten leidt dan het bubble sort-algoritme.