{"id":874,"date":"2023-05-06T10:05:08","date_gmt":"2023-05-06T08:05:08","guid":{"rendered":"https:\/\/scratch.itbib4you.be\/?page_id=874"},"modified":"2023-05-07T15:43:49","modified_gmt":"2023-05-07T13:43:49","slug":"sorteren","status":"publish","type":"page","link":"https:\/\/scratch.itbib4you.be\/index.php\/sorteren\/","title":{"rendered":"Sorteren"},"content":{"rendered":"\n
\n
LESOVERZICHT<\/a><\/div>\n<\/div>\n\n\n\n

Inleiding<\/h2>\n\n\n\n

De pagina Sorteren <\/mark>beschrijft twee eenvoudige algoritmes om gegevens in stijgende of in dalende volgorde te rangschikken (sorteren<\/mark>). <\/p>\n\n\n\n

Gegevens die bij elkaar horen worden meestal in lijsten<\/mark> (ook tabellen<\/mark> 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).<\/p>\n\n\n\n

Maand<\/th>Gemiddelde Temperatuur<\/th><\/tr><\/thead>
1<\/td>6,2<\/td><\/tr>
2<\/td>7,2<\/td><\/tr>
3<\/td>6,8<\/td><\/tr>
4<\/td>11,1<\/td><\/tr>
5<\/td>13,1<\/td><\/tr>
6<\/td>17,5<\/td><\/tr>
7<\/td>17,0<\/td><\/tr>
8<\/td>20,4<\/td><\/tr>
9<\/td>15,2<\/td><\/tr>
10<\/td>11,3<\/td><\/tr>
11<\/td>8,9<\/td><\/tr>
12<\/td>5,5<\/td><\/tr><\/tbody><\/table>
https:\/\/weerstatistieken.nl\/de-bilt\/2020\/december<\/a><\/figcaption><\/figure>\n\n\n\n

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.<\/p>\n\n\n

\n
\"temperatuurgegevens\"
temperatuurgegevens<\/figcaption><\/figure>\n<\/div>\n\n\n

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

<\/div>\n\n\n\n

Schermontwerp<\/h2>\n\n\n\n

Volgende afbeelding schetst de Graphical User Interface<\/mark> (GUI<\/mark>) die we voor het programma wensen te gebruiken:<\/p>\n\n\n

\n
\"GUI\"
Graphical User Interface (GUI)<\/figcaption><\/figure>\n<\/div>\n\n\n
<\/div>\n\n\n\n

De lijst Origineel<\/mark> bevat de originele gegevens die we wensen te sorteren. De tabellen SelectionSort<\/mark> en BubbleSort<\/mark> zullen de gesorteerde gegevens bevatten bekomen door enerzijds het selection sort<\/mark>-algoritme en anderzijds het bubble sort<\/mark>-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. <\/p>\n\n\n\n

Ontwikkeling van het Programma<\/h2>\n\n\n\n

De verschillende onderdelen van het programma zullen stapsgewijs worden opgebouwd.<\/p>\n\n\n\n

Lijsten defini\u00ebren<\/h3>\n\n\n
\n
\"Sorteren:
Nieuwe lijst defini\u00ebren<\/figcaption><\/figure>\n<\/div>\n\n\n

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

Sprites defini\u00ebren<\/h3>\n\n\n\n

De groene knoppen \"Sprite\" boven de tabellen defini\u00ebren twee afzonderlijke Sprites. We kunnen deze Sprites ofwel tekenen of we kunnen deze Sprites selecteren uit de beschikbare Sprites (bijvoorbeeld Sprite Button1<\/mark>). De eerste knop hebben we benaamd als selectionsortKnop<\/mark>, de tweede knop krijgt dan de naam bubblesortKnop<\/mark>. <\/p>\n\n\n\n

Klok variabelen<\/h3>\n\n\n\n

Onderaan elke gesorteerde lijst toont een variabele de werkelijke sorteertijd voor het betreffende algoritme. Hiervoor worden de variabelen t1<\/mark> en t2 <\/mark>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.<\/p>\n\n\n\n

De start van het programma<\/h3>\n\n\n\n

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

De pseudocode ziet er als volgt uit:<\/p>\n\n\n\n

Maak de lijst Origineel leeg\nMaak de lijst SelectionSort leeg\nMaak de lijst BubbleSort leeg\nPlaats de variabele t1 op 0\nPlaats de variabele t2 op 0\nRepeat 1000 times\n   Voeg willekeurig getal tussen 1 en 10000 toe aan de lijst Origineel\nEnd Repeat<\/code><\/pre>\n\n\n\n
Dit resulteert in volgend programma:<\/p>\n\n\n
\n
\"Start<\/figure>\n<\/div>\n\n\n
Het leegmaken van een lijst gebeurt via de instructie \"Leegmaken. Een element wordt achteraan toegevoegd aan een lijst met de instructie \"Element.<\/p>\n\n\n\n
Een sortering opstarten<\/h3>\n\n\n\n
Door een klik op het groene bolletje start het aangeklikte sorteeralgoritme (instructie \"Klikken). Nadien wijzigt de kleur van het bolletje naar  rood (instructie \"Kleur. Enkel als de lijst SelectionSort<\/mark> leeg is kunnen alle gegevens worden gekopieerd vanuit de lijst Origineel<\/mark> naar de lijst SelectionSort<\/mark>. Dit gebeurt via het script kopieerGegevens<\/mark>. Het sorteren zelf gebeurt in het script sorteerGegevens<\/mark>. De klok<\/mark>-variabele krijgt bij de opstart de waarde 0. Bij het be\u00ebindigen van het sorteerproces wordt de waarde van de klok<\/mark>-variabele gekopieerd naar de variabele t1<\/mark>. <\/p>\n\n\n\n
Het programma ziet er als volgt uit:<\/p>\n\n\n
\n
\"Indrukken<\/figure>\n<\/div>\n\n\n
Het blok kopieerGegevens<\/mark> is nu eenvoudig te begrijpen op basis van voorgaande bespreking:<\/p>\n\n\n
\n
\"Kopieer<\/figure>\n<\/div>\n\n\n
De functie \"De bepaalt de grootte van een lijst. De functie \"Een laat toe om een element uit de tabel te selecteren. <\/p>\n\n\n\n
Het selection sort algoritme<\/h3>\n\n\n\n
Algoritme<\/h4>\n\n\n
\n
\"selection<\/figure>\n<\/div>\n\n\n
Het selection sort<\/mark>-algoritme start bovenaan (variabele StartPositie<\/mark>) en zoekt de plaats (variabele PlaatsKleinste<\/mark>) 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.<\/p>\n\n\n\n
Script SorteerGegevens<\/h4>\n\n\n\n
Volgende pseudocode toont de werking van het script  sorteerGegevens<\/mark>:<\/p>\n\n\n\n
Initialiseer StartPositie op 1\nRepeat lengte van SelectionSort-1\n   Zoek de plaats van kleinste element in tabel (PlaatsKleinste) startend vanaf StartPositie\n   If PlaatsKleinste groter is dan StartPositie\n      Verwissel element op PlaatsKleinste met element op StartPositie\n   End If\nEnd Repeat<\/code><\/pre>\n\n\n\n
 zoekPlaatsKleinste<\/mark>en verwisselGegevens<\/mark> zijn afzonderlijke scripts in het programma:<\/p>\n\n\n\n
Het Scratch-programma is een vertaling van bovenstaande pseudocode:<\/p>\n\n\n
\n
\"Module<\/figure>\n<\/div>\n\n\n
script zoekPLaatsKleinste<\/h4>\n\n\n\n
Het script zoekPlaatsKleinste<\/mark> zoekt de plaats van het kleinste getal startend vanaf de StartPositie<\/mark>. De variabele PlaatsKleinste<\/mark> wordt eerst ge\u00efnitialiseerd met de plaats van de variabele StartPositie<\/mark>. 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<\/mark> aangepast. De variabele Positie<\/mark> houdt dan bij met welk element in de tabel we bezig zijn. <\/p>\n\n\n\n
Deze redenering zit vervat in volgend script:<\/p>\n\n\n
\n
\"zoekPlaatsKleinste\"<\/figure>\n<\/div>\n\n\n
Op het einde bevat de variabele PlaatsKleinste<\/mark> de plaats in de lijst waar het kleinste getal zich bevindt. Indien PlaatsKleinste<\/mark> groter is dan de StartPositie<\/mark> dan wisselen we beide getallen om.<\/p>\n\n\n\n
Script verwisselgegevens<\/h4>\n\n\n\n
Om twee getallen om te wisselen moeten we steeds het eerste getal in een tijdelijke variabele bewaren (bijvoorbeeld variabele Tijdelijk<\/mark>). Pas daarna kan de plaats van het eerste getal worden opgevuld met het tweede getal. De variabele Tijdelijk<\/mark> wordt in de volgende stap overgebracht naar de plaats van het tweede getal. <\/p>\n\n\n\n
Deze redenering zit vervat in volgend programma:<\/p>\n\n\n
\n
\"Verwissel<\/figure>\n<\/div>\n\n\n
De vervang<\/mark>-instructie \"Vervang laat toe om een element in een tabel te vervangen door een andere waarde.<\/p>\n\n\n\n
Het bubble sort algoritme<\/h3>\n\n\n\n
Algoritme<\/h4>\n\n\n
\n
\"bubble<\/figure>\n<\/div>\n\n\n
Het bubble sort<\/em><\/mark>-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).<\/p>\n\n\n\n
Als we het algoritme toepassen op bovenstaande tabel dan krijgen we volgende resultaten: <\/p>\n\n\n\n