Programmeren 10 - Klassiek algoritme: Bubblesort en w8woordgenerator

• Informatica
• Middelbare school
• havo, vwo
• Leerjaar 4-6

Klassieke algoritmes

We nemen vandaag een klassieke algoritme onder de loep:

Bubblesort.

• We bekijken een filmpje over Bubblesort, hoe dit werkt
• Je kunt Bubblesort zelf uitvoeren. Je hebt hier 10 speelkaarten voor nodig. Bekijk het filmpje. 
• Bubblesort maken we met een FOR-loop (beter met een WHILE-loop)

Bubblesort in Flowgorithm met een FOR-loop.

Stappenplan:

Start

• Maak een array van 4 random gehele getallen

Bubbelen

• Doorloop de array
• Je vergelijkt steeds twee waardes naast elkaar
• Is de eerste groter dan de tweede? Wissel ze dan om met een swap. In Python stond de swap op deze pagina, de oefening Exchange Program.
• Bepaal hoe vaak de array doorlopen moet worden, met een laatste keer als check

Zelfstandig werken:

• Bubblesort met een FOR-loop of (iets moeilijker) WHILE-lus

Wachtwoordgenerator in Flowgorithm, met een FOR-loop:

• Laat de gebruiker ingeven hoe lang het wachtwoord moet zijn
• Maak gebruik van de gegeven functies in Flowgorithm: random en ToChar(n). Je vind ze op de documentatiepagina van Flowgorithm
• Bekijk de ASCII-tabel, bv hier: Let op: de waardes lopen van 32 (spatie) t/m 126
• Laat in een FOR-loop steeds het volgende karakter van je wachtwoord bepalen
• Ontdek hoe je de uitvoer op 1 regel krijgt (simpele oplossing is er)
• Bekijk de code in Python, vanuit FLowgorithm via Tools -> Source code viewer

De WHILE-lus is iets anders dan de FOR-loop.

Ook in deze structuur herhaal je code.

Maar er is een voorwaarde aan verbonden.

Zolang de voorwaarde geldt, wordt de code doorlopen.

Iedere keer aan het begin van de WHILE-lus wordt de voorwaarde weer gecheckt.

Als de voorwaarde niet meer geldt, wordt de WHILE-lus verlaten.

GEVAAR: De oneindige loop/lus

Bekijk de programma's op deze pagina, en bepaal de uitvoer. Nummer 3 bevat een oneindige loop. Hoe kun je dat zien?

Kijk of je Binary Search kunt maken. De opdracht staat hier

Bubblesort: Eerst het algoritme uitschrijven op papier:

• Als de rij gesorteerd is: stop
• Zolang de rij niet gesorteerd is, doe:
• Doorloop de rij
• Vergelijk 2 getallen naast elkaar en verwissel ze zonodig. Let op dat je niet uit de rij loopt
• Aan het eind van de rij: De hoogste waarde is naar achteren gebubbeld, die hoef je niet meer te vergelijken bij volgende doorlopen
• Moest je swappen? Ga dan door met een rij die 1 kleiner is

Bubble1: Eerst opschonen

1e versie pseudocode:

Zolang ongesorteerd = True

for i = 1 to einderij-1 do

als rij[i] > rij[i+1] 

swap 

{eindfor}

einderij = einderij-1

{nu heb je de waarde ongesorteerd ongemoeid gelaten. Waar verander je die (anders een oneindige loop)}

2e versie pseudocode:

Zolang gesorteerd = False

gesorteerd = True

for i = 1 to einderij-1 do

als rij[i] > rij[i+1] 

swap 

gesorteerd = False {er is een keer geswapt, dus je rij is nog steeds niet gesorteerd}

{eindfor}

einderij = einderij-1 {laatste element zit op zijn plaats, dus de rij die je moet sorteren is 1 plek korter}

C:\Users\User\OneDrive\Informatica\Programmeren\Algoritmes en programmeerconcepten\Flowgorithm\Flowgorithm lesmateriaal\Conditie\OpbouwBubblesortSake