DATS 2300202003

Prev Up Next

Hei alle sammen!

 

Da er vi i gang med søking og sortering, og denne uken skal vi blant annet se på merge, quicksort, insertion sort, mm. 

 

Søking

I denne videoen går vi gjennom sortert søk, usortert søk, og binærsøk i sortert tabell. Vi ser også på hvordan binærsøk kan sees på som et binært tre for å søke etter enkelte elementer i listen.

 

Quicksort

Quicksort er en rekursiv sorteringsalgoritme hvor vi sorterer ett tall for hver iterasjon. Men til forskjell fra f.eks. selection sort (finn største tall og legg bakerst, finn nest største tall og legg nest bakerst, etc.) så sorterer vi ett tilfeldig tall. Hele hovedpoenget er at vi bruker det at dersom et tall er sortert, så er alle tall til høyre for tallet like stort eller større, og alle tall til venstre er mindre. Det finnes mange strategier for å finne beste pivot-verdi, men vi bruker siste i listen i denne videoen.

Insertion sort

Insertion sort går ut på å sette inn et tall i en sortert liste.

 

Merge sort

Flettesortering - eller merge sort - brukes for å rekursivt slå sammen to sorterte tabeller til en felles sortert tabell. I denne videoen går vi gjennom sortering av to lengere lister, og hvordan vi kan bruke merge sort til å sortere et array rekursivt. 

 

Bubble sort

I denne videoen går vi gjennom bubble sort - boblesortering. Hele idéen bak boblesortering er å sortere ett tall om gangen - det største. Det gjør man ved å gå fra "bunnen" av listen til "toppen", og hele tiden ta med seg det største tallet oppover. 

 

Quicksort og algoritmeanalyse av quicksort

I denne dobbelt-timen går jeg igjen igjennom quicksort. Men nå går vi grundigere til verks og tar også med algoritmeanalyse og argumenterer for at kompleksiteten til quicksort er O(n log(n)) i beste tilfellet (og gjennomsnittstilfellet), mens den er O(n^2) for verste tilfellet.