ok, volgende vragen....
het gaat over zoeken in een lijst en sorteren van een lijst.
De eerste vraag gaat over linear search. Hier maakt het toch ook niet uit of de lijst nu al dan niet la gesorteerd is hé. Hij gaat toch zowiezo mooi elk elementje af ut heel de lijst tot hij het gezochte elementje heeft gevonden. Maar dan is de tjdscomplexiteit bij linear search toch O(n²) hé? en dat is dan gelijk aan de worst-case complexiteit. Maar de best-cese complexiteit is dan toch lineair, O(n). Want dan vindt hij na 1 stap het elementje?
Dan Bubble sort...
Daar kan ik in onze cursus niet afleiden of bij deze manier van sorteren nu het eerste element willekuerig uit de lijst wordt gekozen en dat er dan wordt gekeken of het element dat er direct na komt kleiner is of niet. Als kleiner dan wisselen.
dan krijg je zoiets:
stel lijst is 3 2 4 1 5 dan 2 3 1 4 5 dan 2 3 1 4 5 dan 2 1 3 4 5 dan 2 1 3 4 5 dan 1 2 3 4 5 . Omdat het random kiest dan het zijn dat hij dus nutteloze stappen doet? of is het zo:
3 2 4 1 5 dan 2 3 1 4 5 dan 2 1 3 4 5 dan 1 2 3 4 5 . en begint hij dus steeds bij het eerste element, vergelijkt met 2de, swapt indien nodig en kijkt dan naar 3de en 4de element? En als 1ste ok, dan vergelijken tussen 2de en 3de element?
Of zie ik het gewoon helemaal fout?
Want dan weet ik de tijdscomplexiteit hier ook niet van, laat staan de best-case complexiteit...