sorteringsalgoritmer sammenligning eksamensoppgaver

Hva er boblesortering?

En enkel sorteringsalgoritme som gjentatte ganger går gjennom listen og bytter naboelementer hvis de er i feil rekkefølge.

Boblesortering er effektiv for...

Små datasett - den har dårligere ytelse på store datasett.

Hva er innsettingssortering?

En algoritme som bygger opp den sorterte listen ett element av gangen ved å sette inn hvert nytt element på riktig sted.

Innsettingssortering har en beste tilfelle kompleksitet på...

$\displaystyle O(n)$ når listen er nesten sortert.

Hvilken algoritme bruker kvikksortering?

Den bruker en 'pivot' for å dele opp listen i mindre deler.

Kvikksortering er vanligvis raskere enn...

Boblesortering og innsettingssortering, spesielt for store datasett.

Sammenligning: boblesortering vs. innsettingssortering

- Boblesortering: $\displaystyle O(n^2)$ i gjennomsnitt. - Innsettingssortering: $\displaystyle O(n^2)$ i verste tilfelle, $\displaystyle O(n)$ i beste tilfelle.

Hva er utvalgssortering?

En algoritme som finner det minste elementet i listen og plasserer det først, gjentar prosessen for de gjenværende elementene.

Utvalgssortering er nyttig for...

Små datasett og når minnekompleksitet er viktig, da den har $\displaystyle O(1)$ ekstra plassbehov.

Hva er tidskompleksiteten til kvikksortering?

$\displaystyle O(n imes ext{log}(n))$ i gjennomsnitt, men $\displaystyle O(n^2)$ i verste tilfelle.

Hvilken sorteringsalgoritme er stabil?

Innsettingssortering er stabil, noe som betyr at den bevarer rekkefølgen på likverdige elementer.

Boblesortering er stabil: sann eller usann?

Sann - den bevarer rekkefølgen av like elementer.

Fyll ut: Utvalgssortering har en tidskompleksitet på ____.

$\displaystyle O(n^2)$ for alle tilfeller.

Når er innsettingssortering mest effektiv?

Når listen allerede er nesten sortert, på grunn av $\displaystyle O(n)$ kompleksitet.

Sammenligning: innsettingssortering vs. utvalgssortering

- Innsettingssortering: raskere ved små endringer. - Utvalgssortering: alltid $\displaystyle O(n^2)$.

Hvordan implementeres boblesortering?

Iterer over listen, bytt naboelementer hvis de er i feil rekkefølge, gjenta til listen er sortert.

Tidskompleksitet for boblesortering?

O(n²). Dette skyldes at hver verdi sammenlignes med alle andre verdier i listen, noe som gir kvadratisk vekst.

Romkompleksitet for innsettingssortering?

O(1). Innsettingssortering bruker bare en konstant mengde ekstra minne uavhengig av inputstørrelsen.

Er mergesort stabil?

Ja, mergesort er en stabil sorteringsalgoritme. Den beholder rekkefølgen av like elementer.

Sammenlign effektiviteten til quicksort og heapsort.

Quicksort har i gjennomsnitt O(n log n), mens heapsort alltid har O(n log n). Quicksort er ofte raskere i praksis.

Fullfør setningen: Tidskompleksiteten til quicksort er vanligvis ...

... O(n log n) men kan være O(n²) i verste fall.

Hvilken sorteringsalgoritme er best for store datasett?

Mergesort er ofte best for store datasett, spesielt når dataene er lagret på disk.

Tidskompleksitet for utvalgssortering?

O(n²). Dette skyldes at den alltid må finne det minste elementet for hver iterasjon.

Er quicksort en in-place algoritme?

Ja, quicksort er in-place, noe som betyr at den sorterer listen uten å bruke ekstra plass for å lagre kopier.

Sammenlign romkompleksiteten til mergesort og quicksort.

Mergesort har O(n) romkompleksitet, mens quicksort har O(log n) i beste fall, og O(n) i verste fall.

Hvilken algoritme er best for nesten sorterte lister?

Innsettingssortering er best for nesten sorterte lister, med en tidskompleksitet nær O(n).

Tidskompleksiteten til radixsort?

O(nk), der n er antall elementer og k er det maksimale antallet sifre i det største tallet.

Er bubblesort effektiv?

Nei, bubblesort er ineffektiv for store lister, med O(n²) tidskompleksitet.

Hva er Quicksort?

Quicksort er en effektiv sorteringsalgoritme som bruker 'divide and conquer' prinsippet. Den velger et pivot-element og deler listen i to sublister, som sorteres rekursivt.

Verdien av pivot i Quicksort?

Pivot kan være: - Det første elementet - Det siste elementet - Et tilfeldig valgt element - Medianen av tre elementer

Hva er Merge-sort?

Merge-sort er en stabil sorteringsalgoritme som bruker 'divide and conquer'. Den deler listen i halvparten, sorterer hver halvdel, og slår dem sammen.

True or False: Merge-sort er alltid raskere enn Quicksort.

False. Merge-sort har en stabil tidskompleksitet på $\displaystyle O(n imes ext{log} n)$, mens Quicksort i gjennomsnitt også er $\displaystyle O(n imes ext{log} n)$, men kan være $\displaystyle O(n^2)$ i verste fall.

Hva er heap-sort?

Heap-sort er en sorteringsalgoritme basert på en binær heap. Den bygger en max-heap fra listen og fjerner det største elementet gjentatte ganger for å sortere.

Forklar tidskompleksiteten til Heapsort.

$\displaystyle O(n imes ext{log} n)$ i alle tilfeller, fordi det krever $\displaystyle O(n)$ tid for å bygge heapen og $\displaystyle O( ext{log} n)$ for hver fjerning.

Fill in the blank: Tidskompleksiteten til Quicksort i gjennomsnitt er _____ .

$\displaystyle O(n imes ext{log} n)$

Hva er Timsort?

Timsort er en hybrid sorteringsalgoritme som kombinerer Merge-sort og Insertion-sort. Den er optimalisert for real-world data og brukes i Python og Java.

Sammenlign Quicksort og Merge-sort.

Quicksort: - Raskere i praksis - Ikke stabil Merge-sort: - Stabil - Alltid $\displaystyle O(n imes ext{log} n)$

Hva er Radix-sort?

Radix-sort er en ikke-sammenlignende sorteringsalgoritme som sorterer heltall ved å gruppere dem etter individuelle sifre, noe som gir lineær tidkompleksitet i beste tilfelle.

Hvor brukes Heapsort?

Heapsort brukes i situasjoner der stabilitet ikke er kritisk, for eksempel i systemer med begrensede ressurser og der minnebruk er viktig.

Forklar 'divide and conquer' metoden.

'Divide and conquer' deler et problem i mindre delproblemer, løser delene individuelt, og kombinerer resultatene for å gi løsningen på det opprinnelige problemet.