Informatica I

Forum van 1ste Bachelor Fysica.

Moderator: Praesidium

amy
WOZ
Posts: 483

Post#16 » Tue Aug 19, 2008 10:37 am

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...

User avatar
Fristi
WOZ
Posts: 4565

Post#17 » Tue Aug 19, 2008 11:13 am

Bubble sort:
Stel ge werkt met een array, steken n elementjes in.

Ge begint bij de eerste 2, ge vergelijkt en indien nodig wisselt ge ze om. Tot als ge het einde van de array bereikt.
Hoewel de kans groot is da u rijtje nog niet gesorteert is, gaat het grootste element wel vanachter in u array zitten.
Zodoende, als ge em nog is moet overlopen, ge begint opnieuw int begin, enkel den 2de keer laat ge het laatste element weg. Dus ge overloopt den 2de keer t.e.m n-1.
Zo verder tot als heel u array in orde is.
Vanaf het moment dat ge u array overloopt en ge moet geen wissels meer uitvoeren kan het algoritme stoppen.

Worst case is dan : O(n^2)
Best case: O( n )

Linear search:
Best case: O( 1 ): Als het eerste element in u lijst toevallig het geen is dat ge zoekt zijn er geen vergelijkingen nodig.
Worst Case: O( n ): Het element dat ge zoekt zit vanachter dus zijn er n vergelijkingen nodig.
Average Case: O( n ): Zit int midden, n / 2 -> O( n )
Fristi Ad Infinitum

WINAK WOZ 2013 - ...
WINAK Magister Fristi 2012-2013
WINAK Feest 2011-2012
WINAK Schachtentemmer 2010-2011
WINAK Scriptor 2008-2009 | 2009-2010

Return to “1ste Bachelor”

Who is online

Users browsing this forum: No registered users and 2 guests

cron