Simple Sorts Flashcards
Insertion -, Selection - and Bubble sort
Wat is Bubble Sort?
Bubble Sort is een sorteeralgoritme dat bekend staat om zijn traagheid, maar conceptueel het eenvoudigste is van de sorteeralgoritmen. Het is een goed beginpunt voor het verkennen van sorteertechnieken.
Wat zijn de basisregels van Bubble Sort?
Vergelijk twee elementen.
Wissel ze als degene links groter is.
Ga één positie naar rechts.
Wat gebeurt er na de eerste ronde van Bubble Sort?
Na de eerste ronde staat grootste element aan het einde van de rij. Dit komt omdat de grootste elke keer dat hij wordt vergeleken, naar rechts ‘bubbelt’ tot hij het einde bereikt.
Wat is de complexiteit van Bubble Sort?
Bubble Sort heeft een tijdcomplexiteit van O(N^2), wat betekent dat de tijd die nodig is om te sorteren kwadratisch toeneemt met het aantal elementen.
Wat is een invariant in de context van Bubble Sort?
Een invariant is een conditie die gedurende het algoritme onveranderd blijft. Bij Bubble Sort is de invariant dat de items rechts van de huidige positie gesorteerd zijn.
Wat is Selection Sort?
Selection Sort verbetert de Bubble Sort door het aantal benodigde wisselingen te verminderen van O(N^2) naar O(N). Helaas blijft het aantal vergelijkingen O(N^2).
Wat is het voordeel van Selection Sort bij grote records?
Bij grote records die fysiek in het geheugen moeten worden verplaatst, is de wisseltijd veel belangrijker dan de vergelijktijd. Selection Sort biedt in dergelijke gevallen een significante verbetering.
Wat zijn de basisregels van Selection Sort?
Selecteer kleinste element.
Wissel deze met de elem aan het linkse uiteinde.
Herhaal dit proces voor de rest van de elem.
Wat gebeurt er tijdens de eerste ronde van Selection Sort?
tijdens de eerste ronde selecteer je de kortste speler en wissel je deze met de speler op positie 0. De gesorteerde spelers verzamelen zich aan de linkerkant.
Wat gebeurt er tijdens de volgende rondes van Selection Sort?
Bij elke volgende ronde begin je een positie verder naar rechts en herhaal je het proces. De gesorteerde spelers blijven aan de linkerkant staan.
Wat is het verschil in wisselingen tussen Bubble Sort en Selection Sort?
Bubble Sort maakt O(N^2) wisselingen, terwijl Selection Sort slechts O(N) wisselingen maakt, wat het efficiënter maakt bij grote gegevenssets.
Wat is de tijdcomplexiteit van Selection Sort?
Selection Sort heeft een tijdcomplexiteit van O(N^2), net als Bubble Sort, maar het is sneller omdat er minder wisselingen zijn.
Wat is een invariant in de context van Selection Sort?
Een invariant is een conditie die gedurende het algoritme onveranderd blijft. Bij Selection Sort zijn de items links van de huidige positie altijd gesorteerd.
Hoeveel vergelijkingen en wisselingen vinden plaats tijdens Selection Sort?
oor N spelers zijn er in totaal N*(N-1)/2 vergelijkingen en slechts N wisselingen, waardoor het sneller is bij grote sets gegevens.
Wat zijn de voordelen van minder wisselingen bij Selection Sort?
Minder wisselingen betekenen minder overhead bij het verplaatsen van grote records in het geheugen, waardoor het algoritme efficiënter is.
Wat is Insertion Sort?
Insertion Sort is een sorteeralgoritme dat elementen een voor een in de juiste positie in een deels gesorteerde lijst plaatst.
Hoe presteert Insertion Sort vergeleken met Bubble Sort en Selection Sort?
Insertion Sort is ongeveer twee keer zo snel als Bubble Sort en iets sneller dan Selection Sort in normale situaties.
Wat is de tijdscomplexiteit van Insertion Sort?
De tijdscomplexiteit van Insertion Sort is O(N^2), maar het is efficiënter dan Bubble Sort.
Hoe werkt het concept van gedeeltelijk sorteren in Insertion Sort?
Bij gedeeltelijk sorteren zijn de elementen links van een denkbeeldige markering gesorteerd onderling, maar mogelijk nog niet in hun definitieve positie.
: Wat gebeurt er tijdens het verschuivingsproces in Insertion Sort?
Het verschuivingsproces stopt wanneer de laatste speler die groter is dan de gemarkeerde speler is verschoven, waardoor de gemarkeerde speler op de juiste plek kan worden ingevoegd.
Hoe eindigt het sorteerproces in Insertion Sort?
Het proces wordt herhaald totdat alle onsorteerde spelers in de juiste positie in de gedeeltelijk gesorteerde groep zijn ingevoegd.
Hoe werkt het Insertion Sort algoritme in Java?
Het algoritme verwijdert een gemarkeerd item, verschuift gesorteerde items naar rechts en voegt het gemarkeerde item op de juiste plek in.
Wat is het verschil tussen Insertion Sort en andere sorteeralgoritmen zoals Bubble Sort en Selection Sort?
Insertion Sort sorteert gegevens gedeeltelijk, terwijl Bubble Sort en Selection Sort volledige groepen gegevens sorteren.
Wat zijn de nadelen van Insertion Sort bij omgekeerd gesorteerde gegevens?
Bij omgekeerd gesorteerde gegevens voert Insertion Sort elke mogelijke vergelijking en verschuiving uit, waardoor het niet sneller is dan Bubble Sort.
