Sist endret: 17.08.2010

Løsningsforslag - Sorteringsmetoder

Innleveringsfrist: 14.10.2011 10:00

Du er logget inn og får derfor se om du har svart riktig/feil på de enkelte oppgavene.
LF-svar er markert med grønt og feil svar er markert med rødt.

Hvis dere er uenige i fasit, oppfordres dere til å diskutere dette på algdats nyhetsgruppe. Denne nyhetsgruppen har også et webgrensesnitt.

Oppgave 1

a) Hva er kjøretiden til den mest effektive algoritmen som kan finne ut om alle elementene i en usortert liste med n elementer er unike? (20 %)

Θ(1)
O(log(n))
O(n)
O(n*log(n))
O(n²)
O(n²*log(n))
O(2ⁿ)
O(n!)

Din kommentar:
LF-forklaring:	Sorter listen først med en O(n*log(n)) algoritme. Søk deretter sekvensielt gjennom listen på leting etter etterfølgende elementer med samme verdi.

I de følgende deloppgavene ser vi bort fra (ukjente) konstantledd i kjøretiden til sorteringsalgoritmene, rund av til nærmeste alternativ der det er nødvendig. Samtidig forutsetter vi at et sekvensielt søk alltid søker igjennom hele listen.

b) Hvor mange ganger må man utføre et søk i en usortert liste på n = 10³ elementer for at det skal lønne seg å først sortere den og deretter søke vha. binærsøk, fremfor å foreta sekvensielle søk? Vi antar at sorteringsalgoritmen som blir brukt er mergesort (7.5 %)

2
4
6
8
10
12
14

Din kommentar:
LF-forklaring:	Sekvensielt søk er k * n. Binærsøk er nlog2(n) + klog2(n). Oppgaven går derfor ut på å finne ut når nlog2(n) + klog2(n) = k * n. Løst mhp. k får vi da k = -n*log2(n)/(log2(n)-n). For n = 1e3 så blir k = 10,07 ~= 10. (vi runder av til nærmeste svaralternativ)

c) Hvis vi har n = 10⁵ elementer? (7.5 %)

4
8
12
16
20
24
28

Din kommentar:
LF-forklaring:	For n = 1e5 så blir k = 16,6 ~= 16. (vi runder av til nærmeste svaralternativ)

Oppgave 2

a) Dersom man ønsker et lavt minneforbruk foretrekker man: (2.5 %)

Bubblesort
Mergesort
Heapsort
Det spiller ingen rolle

Din kommentar:
LF-forklaring:	Heapsort er en 'in place' sorteringsalgoritme, og bruker asymptotisk mindre minne enn mergesort. Den er også raskere enn bubblesort.

b) Dersom vi vet at vi behandler heltall, vil en sortering basert på sammenlikning kunne oppnå O(n) kjøretid: (2.5 %)

Sant
Usant

Din kommentar:
LF-forklaring:	Sortering basert på sammenlikning er Ω(n*lg(n)) uansett. Det spiller ingen rolle hva man vet om input så lenge man ikke eksplisitt benytter seg av det.

c) Dersom man allerede har laget en heap av tallene som skal sorteres, kan man sortere med Heapsort i O(n) kjøretid: (2.5 %)

Sant
Usant

Din kommentar:
LF-forklaring:	Heap-konstruksjon er O(n). Det er selve sorteringen som tar O(n*lg(n)) tid.

d) Quicksort forbruker O(1) ekstra minne i tillegg til det som trengs for å lagre tallene som skal sorteres: (2.5 %)

Sant
Usant

Din kommentar:
LF-forklaring:	Man må lagre indeksene for hvert rekursive kall

e) Mergesort forbruker O(lg(n)) ekstra minne i tillegg til det som trengs for å lagre tallene som skal sorteres: (2.5 %)

Sant
Usant

Din kommentar:
LF-forklaring:	Mergesort bruker O(n) ekstra minne, fordi Merge-rutinen må ha en like stor liste for å flette listene inn i.

f) Dersom du vet n tall i [0, n-1](med duplikater) skal sorteres, vil counting sort være en god algoritme: (2.5 %)

Sant
Usant

Din kommentar:
LF-forklaring:	Countingsort får da kjøretid O(n+k), men k=n så: O(2n) = O(n)

g) Grunnen til at Radix-sort må startes på minst-signifikante-siffer, er at de senere sorteringene får større innvirkning på endelig rekkefølge: (2.5 %)

Sant
Usant

Din kommentar:
LF-forklaring:

h) All input kan gi worst-case kjøretid for randomized-quicksort: (2.5 %)

Sant
Usant

Din kommentar:
LF-forklaring:	Om man har veldig uflaks kan man alltid velge største som pivot. Men ettersom det er veldig lav sannsynlighet for dette spiller det liten rolle.

i) Best-case kjøretid for insertionsort er O(n): (2.5 %)

Sant
Usant

Din kommentar:
LF-forklaring:	Om elementene allerede er sortert krever insertionsort bare en sjekk for hvert element i listen. Ettersom dette vil være større enn forrige vil det være ferdig plassert og algoritmen går videre.

j) Dersom du erstatter det lineære søket i insertionsort med et binærsøk får du en O(n*lg(n)) sorteringsalgoritme: (5 %)

Sant
Usant

Din kommentar:
LF-forklaring:	Vi må fortsatt flytte alle de foregående elementene nedover. Dette blir akkurat samme kjøretid som for søket.

Oppgave 3

a) Her kommer fire eksempler på binærtrær.

Hvilke av disse tilfredsstiller kravene til en max-heap? (5 %)

A og B
A og C
A og D
B og C
B og D
C og D
Alle
Ingen

Din kommentar:
LF-forklaring:	A og C er ikke max-heaper siden 8 < 9.

b) Hvis vi har en heap som ser slik ut:

Hvordan ser da listen som representerer heapen ut etter at vi har kjørt fire iterasjoner av heapsort? (5 %)

21, 14, 12, 11, 9, 8, 4
11, 8, 9, 4, 12, 14, 21
11, 9, 4, 8, 12, 14, 21
9, 8, 4, 11, 12, 14, 21

Din kommentar:
LF-forklaring:

c) Er heapsort en stabil sorteringsalgoritme? (12.5 %)

Ja
Nei

Din kommentar:
LF-forklaring:	Bevis for at HeapSort ikke er stabil: Gitt input [2a,2b,1] (som tilfeldigvis allerede er en heap), så vil HeapSort gi [1,2b,2a] som output. Elementene 2a og 2b har byttet plass, og HeapSort er derfor ikke stabil.

Oppgave 4

På Posten Norge driver Lars Jakob og sorterer brev til alle landets kanter. Som alle postarbeidere med respekt for seg selv benytter han radix-sortering for å finne ut hvor brevene skal. Han har ti bokser som han mellomlagrer brevene i (nummerert 0 til 9) til de er ferdig sortert. Brev sorteres etter postnummer. Han får inn en uvanlig stor ladning på ti brev og setter straks i gang med å sortere disse. brevene skal til (i rekkefølge)
2307, 4284, 0327, 4296, 3281, 2291, 8771, 1434, 9215, 4301.

a) Etter én iterasjon i sorteringen, hvor mange brev ligger i boks nummer 1? (5 %)

3
4
5
6

Din kommentar:
LF-forklaring:	I boksnummer 1 vil det ligge 4 brev siden 4 brev har minst signifikant tall lik 1.

b) Hvis Lars Jacob tar ut brevene etter 2 iterasjoner i sorteringen, hvilken rekkefølge vil brevene ligge i da (gitt at han tar dem ut etter stigende boksnummer)? (5 %)

2307, 4284, 0327, 4301, 8771, 1434, 3281, 9215, 2291, 4296
8771, 2291, 4284, 4296, 2307, 4301, 1434, 3281, 0327, 9215
4301, 2307, 9215, 0327, 1434, 8771, 3281, 4284, 2291, 4296
9215, 3281, 4284, 2291, 4296, 4301, 2307, 0327, 1434, 8771

Din kommentar:
LF-forklaring:	Sorteringen ,ra de to foregående iterasjonene er bevart. Det mest signifikante sifferet er ikke sortert enda.

c) Etter 3 iterasjoner i sorteringen, hvilken rekkefølge vil brevene i boks 2 ligge i? (5 %)

2291, 3281, 4284, 4296, 9215
2291, 9215, 4296, 3281, 4284.
9215, 4296, 3281, 2291, 4284.
9215, 3281, 4284, 2291, 4296.
3281, 4284, 2291, 9251, 4296.

Din kommentar:
LF-forklaring:	Sorteringen fra de to foregående iterasjonene er bevart. Det mest signifikante sifferet er ikke sortert enda.