Algoritmer og datastrukturer

Løsningsforslag til øvingsoppgaver: Søking og sortering

Oppgave 1

Oppgave 2

1. Java-kode
2. Java-kode
3. Java-kode

4. Det er ingen ting å tjene på å bruke ternært søk i stedet for binærsøk. Dette fordi det ekstra arbeidet og testingen (overhead) som må gjøres ved hver oppdeling i tre arraysegmenter, gjør at den totale arbeidmengden blir den samme, selv om antall rekursive kall er litt mindre for et ternært søk.

Oppgave 3

1. Innstikksortering:

   8, 1, 4, 1, 5, 9, 2, 6, 5
   1, 8, 4, 1, 5, 9, 2, 6, 5
   1, 4, 8, 1, 5, 9, 2, 6, 5
   1, 1, 4, 8, 5, 9, 2, 6, 5
   1, 1, 4, 5, 8, 9, 2, 6, 5
   1, 1, 4, 5, 8, 9, 2, 6, 5
   1, 1, 2, 4, 5, 8, 9, 6, 5
   1, 1, 2, 4, 5, 6, 8, 9, 5
   1, 1, 2, 4, 5, 5, 6, 8, 9
   

2. Shell sort med inkrementer {1, 3, 5}:

   8, 1, 4, 1, 5, 9, 2, 6, 5
   8, 1, 4, 1, 5, 9, 2, 6, 5
   1, 1, 4, 2, 5, 5, 8, 6, 9
   1, 1, 2, 4, 5, 5, 6, 8, 9
   

3. Flettesortering:

   8, 1, 4, 1, 5, 9, 2, 6, 5
   1, 8, 1, 4, 5, 9, 2, 5, 6
   1, 1, 4, 8, 2, 5, 5, 6, 9
   1, 1, 2, 4, 5, 5, 6, 8, 9
   

4. Quicksort, midtre element brukes hele tiden som partisjoneringselement, merket med * (stjerne) nedenfor:

   8, 1, 4, 1, 5, 9, 2, 6, 5
               *
   2, 1, 4, 1, 5, 9, 8, 6, 5 <-- etter partisjonering
               |
   2, 1, 4, 1  |  9, 8, 6, 5
      *        |     *
   1, 2, 4, 1  |  6, 5, 8, 9 <-- etter partisjonering
   |           |        |  |
   |  2, 4, 1  |  6, 5  |  |
   |     *     |  *     |  |
   |  1, 2, 4  |  5, 6  |  | <-- etter partisjonering
   |        |  |  |  |  |  |
   |  1, 2  |  |  |  |  |  |
   |  *     |  |  |  |  |  |
   |  1, 2  |  |  |  |  |  | <-- etter partisjonering
   V        V  V  V  V  V  V
   1, 1, 2, 4, 5, 5, 6, 8, 9
   

Oppgave 4

1. Innstikksortering er O(n) når alle elementene er like, fordi den indre løkka aldri vil starte.

2. Hvis vi bruker inkrementer som f.eks. Shell's opprinnelige sekvens, eller den bedre "del på 2.2" sekvensen, er Shell sort O(n logn) når alle elementene er like. Den ytterste løkka (som itererer over sekvensen av "gaps") går O(log n) ganger, den midterste går O(n) ganger hver gang, mens den innerste aldri vil starte når elementene er like, på samme måte som for innstikksortering.

3. Flettesortering har samme kjøretid uansett hvordan verdiene i vektoren er, O(nlog(n)).

4. Quicksort er O(n²), fordi den ene "delmengden" alltid blir tom når alle elementene er like.

Oppgave 5

1. Innstikksortering er O(n) når vektoren allerede er sortert, fordi den indre løkka aldri vil kunne starte.

2. Hvis vi bruker inkrementer som f.eks. Shell's opprinnelige sekvens, eller den bedre "del på 2.2" sekvensen, er Shell sort O(n logn) når vektoren allerede er sortert. Den ytterste løkka (som itererer over sekvensen av "gaps") går O(log n) ganger, den midterste går O(n) ganger hver gang, mens den innerste aldri vil starte, på samme måte som for innstikksortering.

3. Flettesortering har samme kjøretid uansett hvordan verdiene i vektoren er, O(nlog(n)).

4. Oppførselen av Quicksort for sorterte vektorer avhenger av hvordan vi velger pivot:
   • Bruk av første element som pivot vil være katastrofalt, og gi kjøretider som er O(n²), fordi pivot alltid vil være minste element.
   • Valg av midtre element eller "midterste av tre" som pivot vil gi perfekte partisjoneringer og O(n logn)).

Oppgave 6

1. Innstikksortering er O(n²) når vektoren er omvendt sortert, fordi den indre løkka alltid vil gå helt "til bunns".

2. Oppførselen til Shell sort er her vanskelig å forutsi, det avhenger av vektorlengde og valg av inkrementer. Uansett vil det bli mere enn O(n logn), fordi den innerste løkka vil måtte gå en del ganger pga. den omvendte sorteringen.

3. Flettesortering har samme kjøretid uansett hvordan verdiene i vektoren er, O(nlog(n)).

4. Oppførselen av Quicksort for omvendt sorterte vektorer avhenger av hvordan vi velger pivot:
   • Bruk av første element som pivot vil være katastrofalt, og gi kjøretider som er O(n²), fordi pivot alltid vil være største element.
   • Valg av midtre element eller "midterste av tre" som pivot vil gi perfekte partisjoneringer og O(n logn)).

Oppgave 7