Datastructuren en algoritmen

De array 5, 3, 8, 1, 4 wordt met bubblesort oplopend gesorteerd. Hoe ziet de array eruit na één doorgang (pass), waarin vanaf het begin tot het eind telkens twee buren worden vergeleken en verwisseld als het linkerelement groter is?

A1, 3, 8, 5, 4
B3, 5, 1, 4, 8
C1, 3, 4, 5, 8

Antwoord en toelichting tonen

Antwoord: B. 3, 5, 1, 4, 8

5 en 3 verwisselen geeft 3, 5, 8, 1, 4; 5 en 8 blijven staan; 8 en 1 verwisselen geeft 3, 5, 1, 8, 4; en 8 en 4 verwisselen geeft 3, 5, 1, 4, 8. Eén doorgang brengt de maximale waarde 8 helemaal naar het eind, waarmee haar positie vastligt; de volgende doorgang sorteert de overige vier elementen op dezelfde manier. 1, 3, 8, 5, 4 is de array na één doorgang van selection sort, dat het minimum naar voren verwisselt, en 1, 3, 4, 5, 8 is het volledig gesorteerde resultaat.

Dit onderwerp oefenen Naar de onderwerppagina

Meer vragen over Datastructuren en algoritmen

De array 29, 10, 14, 37, 13 wordt met selection sort oplopend gesorteerd: het minimum van het ongesorteerde deel wordt gezocht en verwisseld met het eerste element van het ongesorteerde deel. Hoe ziet de array eruit nadat deze stap twee keer is uitgevoerd?
Een array van 10 elementen wordt met insertion sort oplopend gesorteerd. Elk element vanaf het tweede wordt eruit gehaald en vergeleken met de elementen links ervan, te beginnen bij de linkerbuur, tot een element kleiner dan of gelijk aan de waarde is gevonden of het begin is bereikt. Hoeveel vergelijkingen zijn er nodig als de array al oplopend staat, en als hij aflopend staat?
Welk sorteeralgoritme heeft ook in het slechtste geval tijdcomplexiteit O(n log n) en sorteert met nauwelijks extra geheugen, zoals een werkarray?
De records (naam, score) (A, 80), (B, 70), (C, 80), (D, 70) staan in deze volgorde. In welke volgorde staan de namen als ze met een stabiel sorteeralgoritme oplopend op score worden gesorteerd?
In welk typisch geval heeft quicksort tijdcomplexiteit O(n²)?