Mer kompliserte algoritmer

Big O Notation

Et algoritme-konsept som ofte kommer opp er et såkalt “Big O”-notation. Det er en måte å vurdere hvor rask en algoritme er.

Denne notasjonen ignorerer konstante faktorer, altså, hvor lenge det tar å gjør en og en operasjon, men fokuserer heller på hvor kjapp algoritmen er dersom antall elementer blir veldig stort.

Du kan lese mer om Big O notation her: Big O Notation Wikipedia.

Hvis vi ser på algoritmene fra Level 1 så er alle untatt oppgave 9 og 10 av typen \(O(n)\). Det vil si at for \(n\) elementer tar det \(n\) operasjoner å gjøre algoritmen. Dette er en lineer-algoritme.

Oppgave 9 er av typen \(O(n!)\). Det vil si fakultet, som muligens er et begrep du aldri har hørt før. Det betyr enkelt nok at du multipliserer alle tallene opp til tallet. Eksempel: \(5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120\). Da kan du kanskje tenke deg hvor fort denne går i været.

Oppgave 10 er av typen \(O(n \cdot k)\), som er ganske lik \(O(n^2)\), eller kvadratisk tid. To for-loops inne i hverandre er et ganske vanlig tegn på en kvadratisk algoritme. Farten til denne kommer litt an på hvor stort søke-ordet og søke-teksten er.

Test-data for mange av algoritmene

[5, 1, 4, 2, 8]
[3, 2, 1]
[10, 7, 8, 9]
[0, -3, 2, -1, 5]
[1, 1, 1, 1]
[9, 5, 3, 5, 2]
[12, 5, 7, 3, 19, 1, 8, 14, 2, 11]
[30, 10, 25, 0, 5, 20, 15, 35, 40, 2]
[9, 4, 6, 2, 8, 1, 7, 3, 5, 0]
[100, 3, 50, 22, 75, 10, 90, 1, 60, 40]

Oppgave 1 - Bubble Sort

I Level 1 – Oppgave 9 lagde du en ekstremt enkel sorterings-algoritme som heter “Bogo”-sort. Bogo sort er forferdelig som algoritme. Den har en kjøre-tid på \(O(n!)\). Altså, med 5 elementer kan du forvente ~ \(5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120\) operasjoner. Og denne går bare opp og opp.

Bogo-sort fart

Antall ting	Antall operasjoner	Kjøretid (1 milliard / s)
4	24	~0s
5	120	~0s
6	720	~0s
10	3 628 800	3 ms
15	1 307 674 368 000	21 min
20	2 432 902 008 176 640 000	77 år

Som du ser, så går kjøretiden opp usannsynlig fort, 11-12 elementer virker realistisk at den faktisk kan fungere, men forbi det, så blir det kjempetregt.

I denne oppgaven skal vi lage en bedre algoritme som fortsatt er veldig enkel: Bubble-sort. Den fungerer slik:

Hvordan Bubble-sort fungerer

Begynn fra begynnelsen av lista (index 0)
Sjekk om index 0 er større enn index 1
Hvis ja, bytt plass på dem.
Øk index med 1 (fra 0 -> 1)
Repeat step 2 og 3, men nå med index 1 og index 2
Når du når enden (index er lengden på lista) repeter steg 1-5.
Gjør dette \(n - 1\) ganger. Altså er det 6 elementer i lista, repeter disse stegene 5 ganger.

Les mer om Bubble-sort på Wikipedia

Eksempel på sorterings-steg

Vi skal bruke listen [4, 7, 1, 2, 9] i dette eksempelet.

Steg 1Steg 2

Stegene

✅ Starter på index 0
❕ [4, 7, 1, 2, 9]
❓Er 4 større enn 7? ❌-> Øk index med 1
❓Er 7 større enn 1? ✔️-> Bytt plass og øk index med 1
❕ [4, 1, 7, 2, 9]
❓Er 7 større enn 2? ✔️-> bytt plass og øk index med 1
❕ [4, 1, 2, 7, 9]
❓Er 7 større enn 9? ❌-> Øk index med 1
✅ Nå har vi nådd enden. Begynn på nytt (neste steg)

Stegene

✅ Starter på index 0
❕ [4, 1, 2, 7, 9]
❓Er 4 større enn 1? ✔️-> Bytt plass og øk index med 1
❕ [1, 4, 2, 7, 9]
❓Er 4 større enn 2? ✔️-> Bytt plass og øk index med 1
❕ [1, 2, 4, 7, 9]
❓Er 4 større enn 7? ❌-> Øk index med 1
❓Er 7 større enn 9? ❌-> Øk index med 1
✅ Nå har vi nådd enden. Begynn på nytt (neste steg).
Listen er jo sortert nå, men i en worst case så er listen ikke ferdig sortert etter bare to steg. Det kommer til å ta opp til 4 steg (lengden på listen minus 1) å sortere.
Enten kan du legge til en sjekk som sjekker om listen er sortert etter hver repetisjon, eller bare la den fullføre.

Tips:

Du må ha en swap-algoritme. Implementer denne selv.
- Hint om swap: Du må lage en midlertidig verdi før du swapper!

Hint: Pseudo-kode (Denne koden fungerer ikke 100%, men kan hjelpe deg i gang hvis du sitter fast!)

for i in len(list):
    for j in len(list):
        if list[j] > list [j + 1]
            swap(list[j], list[j + 1])
        else 
            break

Oppgave 1b - Reflekter på “Bubble sort”

Hvor rask er denne algoritmen?
- Tenk litt på “Big O” notation her.
  - Hint: Hvor mange for-loops er inni hverandre?
Kan du gjøre denne algoritmen raskere?
Hvor rask kan en sorteringsalgoritme være?

Oppgave 2 - Selection Sort

Selection sort er en annen enkel sorteringsalgoritme. Denne har kjøretiden \(O(n^2)\) som gjør den svært ineffektiv for større lister. I stedet for å bytte elementer hele veien som i bubble sort tar denne algoritmen å finner ut hvilket element som er minst, så plasserer det på begynnelsen av listen (bytter plass med det som er der).

Hvordan Selection-sort fungerer

Begynn fra begynnelsen av lista, sett denne indexen som det “minste” elementet.
Sjekk alle elementene helt til slutten av lista, hvis du finner noe mindre hold styr på den indexen i stedet.
Når du har nådd enden av listen, bytt plass på minste og “første” index.
Øk start-indexen men 1, og repeter steg 1-3
Returner en sortert liste til slutt

Les mer om Selection-sort på Wikipedia

Eksempel på sorterings-steg

Vi skal bruke listen [4, 7, 1, 2, 9, 6] i dette eksempelet.

Steg 1Steg 2Steg 3Steg 4Steg 5

Steg 1

✅ Sett startindex til 0
❕ [4, 7, 1, 2, 9, 6]
✅ Sett index 0 til minste element
❓ Er index 1 mindre? Nei.
❓ Er index 2 mindre? Ja - > sett index 2 til minste element
❓ Er index 3 mindre? Nei
❓ Er index 4 mindre? Nei
❓ Er index 5 mindre? Nei
✅ Bytt plass på index 2 og 0
❕ [1, 7, 4, 2, 9, 6]
✅ Øk start index med 1, fra 0 til 1

Steg 2

✅ Sett startindex til 1
❕ [1, 7, 4, 2, 9, 6]
✅ Sett index 1 til minste element
❓ Er index 2 mindre? Ja - > sett index 2 til minste element
❓ Er index 3 mindre? Ja - > sett index 3 til minste element
❓ Er index 4 mindre? Nei
❓ Er index 5 mindre? Nei
✅ Bytt plass på index 3 og 1
❕ [1, 2, 4, 7, 9, 6]
✅ Øk start index med 1 fra 1 til 2

Steg 3

✅ Sett startindex til 2
❕ [1, 2, 4, 7, 9, 6]
✅ Sett index 2 til minste element
❓ Er index 3 mindre? Nei
❓ Er index 4 mindre? Nei
❓ Er index 5 mindre? Nei
✅ Bytt plass på index 2 og 2 (Ingenting skjer)
❕ [1, 2, 4, 7, 9, 6]
✅ Øk start index med 1 fra 2 til 3

Steg 4

✅ Sett startindex til 3
❕ [1, 2, 4, 7, 9, 6]
✅ Sett index 3 til minste element
❓ Er index 4 mindre? Nei
❓ Er index 5 mindre? Ja - > sett index 5 til minste element
✅ Bytt plass på index 5 og 3
❕ [1, 2, 4, 6, 9, 7]
✅ Øk start index med 1 fra 3 til 4

Steg 5

✅ Sett startindex til 4
❕ [1, 2, 4, 7, 9, 6]
✅ Sett index 4 til minste element
❓ Er index 5 mindre? Ja - > sett index 5 til minste element
✅ Bytt plass på index 5 og 4
❕ [1, 2, 4, 6, 7, 9]
✅ Øk start index med 1 fra 4 til 5
✅ Vi har nådd enden av listen, nå stopper vi

Viktige hint

Du trenger to loops.
Den første kan være praktisk at er en while-loop, slik at start verdien er enkel å øke for hver runde
Du kan sjekke om loopen er sortert etter hver runde, men algoritmen kjører bare til indexen når enden.

Oppgave 3 - Binary Search (Binærsøk)

I denne oppgaven skal dere lage en raskere søke-algoritme enn i Level 1 – Oppgave 1. Der, selv om dere sikkert ikke visste at det heter det, lagde dere en lineær søke-algoritme. Det vil si at den kjører i \(O(n)\) tid.

Men, det går an å gjøre det bedre! Hvis listen allerede er sortert kan du finne det du leter etter med mye mindre sammenligninger, nemlig \(O(log_2(n))\) tid.

Det vil si følgende kjøretider:

Antall elementer	Antall operasjoner
\(10\)	\(3\)
\(100\)	\(7\)
\(1 000\)	\(10\)
\(1 000 000\)	\(20\)
\(1 000 000 000\)	\(30\)

Dersom dere hadde hatt en liste med en MILLIARD, \(10^9\), \(1 000 000 000\) elementer, hadde det tatt maks \(30\) operasjoner å finne et tall.

Algoritmen fungerer slik:

Algoritmen

Forutsetninger: Start med en sortert liste!

Hold styr på to grenser, left og right. left starter på 0 og right starter på listens lengde, minus 1, len(the_list) - 1.
Bruk en while-loop eller en for-loop som kjører opptil \(\lfloor log_2(n) \rfloor\) ganger. (De hakene betyr floor, altså rund ned). Denne skal stoppe når left > right.

Hoved-steg:

Finn midt-index med \(\frac{left + right}{2}\) ((left + right) / 2).
Hvis the_list[mid] er det du leter etter, returner True. Hvis ikke:
Sjekk om tallet er større eller mindre.
Hvis mindre, vet du at venstre siden av listen ikke inneholder elementet (husk, den er sortert!). Sett left = mid + 1
Hvis større, vet du at høyre siden av listen ikke inneholder elementet. Sett right = mid - 1

Hvis løkken slutter uten å ha funnet elementet, er det ikke i listen. Returner False.

Eksempel på søke-steg

Vi skal bruke listen [1, 3, 5, 7, 9, 11, 13, 15] i dette eksempelet. Vi skal søke etter tallet 13.

Steg 1Steg 2Steg 3

Steg 1

✅ Sett left til 0.
✅ Sett right til lengden - 1, altså 7.
✅ Finn midt-indexen, 3. ((0 + 7) / 2 = 3.5 (rund ned til 3))
❕ left = 0, right = 7, list[mid] = 9
❓ Er 9 lik 13? Nei…
❓ Er 9 mindre enn 13? Ja!
✅ Sett left til mid + 1
❕ left = 4, right = 7

Steg 2

✅ Finn midt-indexen, (4 + 7 / 2 = 5.5 (rund ned til 5)).
❕ left = 4, right = 7
❓ Er 11 lik 13? Nei…
❓ Er 11 mindre enn 13? Ja!
✅ Sett left til mid + 1
❕ left = 6, right = 7

Steg 3

✅ Finn midt-indexen, (6 + 7 / 2 = 6.5 (rund ned til 6)).
❕ left = 6, right = 7
❓ Er 13 lik 13? Ja! Returner True.

Oppgave 4 - Reverser ord uten split

Husk tilbake til Oppgave 11 i Level 1. Der skulle du reversere enkelt ord i en setning. Lag en algoritme som gjør det samme, men uten bruk av den innebygde .split() funksjonen.

Tips til framgangsmåte

Begynn med samme utgangspunkt som i Level 1 Oppgave 8
Lag din egen split funksjon og så bruk den i algoritmen.
Gå gjennom hele setningen med en for-loop å finn ut hvor splitte-karakteren er, f.eks. mellomrom ' '.
Lag en liste som inneholder hver del av splitten.

Oppgave 5 - Quick Sort

Les mer om quick sort: Wikipedia, Quick Sort.
Les mer om rekursjon: Wikipedia, Recursion.

Quick-sort er, som navnet sier, en kjapp sorterings-algoritme. Denne, i motsetning til selection-sort og bubble-sort er ekstremt rask, den har en kjøretid på \(O(n \cdot log_2(n))\). Som er ekstremt raskt. Den er kjent som en splitt og hersk algoritme.

Hvordan fungerer denne i praksis?

Hvordan Quick Sort fungerer

Den er en rekursiv algoritme, altså den kaller seg selv flere ganger.
I stedet for å splitte på midten som merge sort gjør velger quick sort en tilfedlig index (eller midterste hvis du foretrekker det), kjent som pivot elementet. Her kan du bruke random biblioteket. Eller hvis du føler for en utfordring, lag en funksjon for å finne tilfeldige tall selv.
Deretter, gå igjennom hele listen å lag en venstre og høyre del, der venstre inneholder alle elementer mindre enn pivot, og høyre har alle større enn pivot (inkludert pivot).
Repeter quick-sort rekursivt på venstre og høyre del.
Dersom den splittede listen har 1 element, så er den sortert, returner og sett sammen.
Disse rekursive kallene vil “automatisk” ende opp med å sortere listen.
Returner den sorterte listen.

Tips til framgangsmåte

Lag en funksjon som heter quick_sort
return dersom listen har 1 element eller mindre.
Velg en random pivot med random.choice()
Lag tomme left og right lister.
Bruk quick_sort igjen på left og right:

def quick_sort(list_in):
    # Kode for resten av quick-sort
    # bruk quick_sort inni seg selv
    left_result = quick_sort(left)
    right_result = quick_sort(right)

Bare sett sammen left og right med en for-loop
return den sammensatte listen

Oppgave 6 - Merge Sort

Les mer om merge sort: Wikipedia, Merge Sort.

Merge sort er en elegant sorteringsalgoritme som “merger”, altså setter sammen mindre lister. Denne, som quick-sort har en kjøretid på \(O(n \cdot log_2(n))\). Den er på mange måter ganske lik som quick-sort men bruker noen andre strategier for å utføre sorteringen sin. Den er en rekursiv, splitt og hersk algoritme.

Hvordan fungerer denne?

Hvordan Merge-sort fungerer

Merge-sort er rekursiv, altså den kjører seg selv igjen og igjen.
Den er en såkalt splitt og hersk algoritme (som kan være et nyttig søkeord).
Ta inn en liste i en funksjon
Splitt listen i to deler, venstre og høyre, og hiv denne inn i seg selv igjen (merge_sort funksjon).
Repeter helt til listen er ett element.
Sett sammen venstre å høyre nå.
Sette sammen fungerer ved å sammenligne første element i begge listene og velge den minste, og hive dette inn i en ny liste.
Deretter sammenlignes det neste elementet i hver halvdel.
Eksempel, dersom venstre liste hadde det minste øker du sammenligningen på den venstre listen, men ikke den høyre, og motsatt.
Returner til slutt den sorterte listen.

Tips til framgangsmåte

Her skal en merge_sort funksjon brukes som tar inn en liste.
Sjekk først om listen er mindre enn 2 elementer langt. Hvis det er ett element så er den allerede sortert, så bare return listen du hiver inn.
Split listen i to deler, venstre og høyre.
Bruk midt-punktet len(list) // 2 for å splitte i to. (// er en spesiell funksjon for integer-divisjon).
Kjør merge_sort funksjonen på hver del. Dette repeterer steg 2-4.
Etter at merge_sort har blitt kjørt på begge delene kjør begge inn i en merge funksjon som setter sammen listene.
I merge opprettes en tom liste.
Bruk en while og sammenlign hele veien første element i begge listene.
Opprett to telle-variabler, i og j, begge starter på 0.
while-loopen skal gå til enten i eller j er større enn listen den skal sammenlignes med.
Dersom venstre liste har minste element, legg inn dette elementet i den tomme listen og øk i med 1, ellers, gjør det med samme med høyre, men med j.
Etter at while stopper betyr det at en av de to liste-halvdelene er “tomme”. Gå deretter igjennom de gjenværende elementene i den “ikke-tomme” halvdelen og legg dem til den tomme listen.
Returner listen som har blitt satt sammen.
I merge_sort returner denne listen.

Eksempel på sorterings-steg

Bilde som viser steg

Her brukes listen [12, 8, 9, 3, 11, 5, 4]

Steg i tekstformat

Vi skal bruke listen [2, 7, 1, 6, 3, 8, 5, 4] i dette eksempelet.

✔️ Listen: [2, 7, 1, 6, 3, 8, 5, 4]
❓ Er listen kortere enn 2? Nei -> Splitt
✅ Splitt listen i to
❕ [2, 7, 1, 6] - [3, 8, 5, 4]
✅ Repeter merge-sort på venstre, og høyre
❕ [1, 2, 6, 7] - [3, 4, 5, 8]
✅ Kombiner de sorterte listene -> [1, 2, 3, 4, 5, 6, 7, 8]
✅ Returner listen -> Ferdig! (Se sub-steps for flere detaljer!)

Steg L (Left)

✔️ Listen: [2, 7, 1, 6]
❓ Er listen kortere enn 2? Nei -> Splitt
✅ Splitt listen i to
❕ [2, 7] - [1, 6]
✅ Repeter merge-sort på venstre, og høyre
❕ [2, 7] - [1, 6]
✅ Kombiner de sorterte listene -> [1, 2, 6, 7]
✅ Returner listen

Steg L.L (Left, Left)

✔️ Listen: [2, 7]
❓ Er listen kortere enn 2? Nei -> Splitt
✅ Splitt listen i to
❕ [2] - [7]
✅ Repeter merge-sort på venstre, og høyre
✅ Kombiner de sorterte listene -> [2, 7]
✅ Returner listen

Steg L.L.L (Left, Left, Left)

✔️ Listen: [2]
❓ Er listen kortere enn 2? Ja -> Return

Steg L.L.R (Left, Left, Right)

✔️ Listen: [7]
❓ Er listen kortere enn 2? Ja -> Return

Steg L.R (Left, Right)

✔️ Listen: [1, 6]
❓ Er listen kortere enn 2? Nei -> Splitt
✅ Splitt listen i to
❕ [1] - [6]
✅ Repeter merge-sort på venstre, og høyre
✅ Kombiner de sorterte listene -> [1, 6]
✅ Returner listen

Steg L.R.L (Left, Right, Left)

✔️ Listen: [1]
❓ Er listen kortere enn 2? Ja -> Return

Steg L.R.R (Left, Right, Right)

✔️ Listen: [6]
❓ Er listen kortere enn 2? Ja -> Return

Steg R (Right)

✔️ Listen: [3, 8, 5, 4]
❓ Er listen kortere enn 2? Nei -> Splitt
✅ Splitt listen i to
❕ [3, 8] - [5, 4]
✅ Repeter merge-sort på venstre, og høyre
❕ [3, 8] - [4, 5]
✅ Kombiner de sorterte listene -> [3, 4, 5, 8]
✅ Returner listen

Steg R.L (Right, Left)

✔️ Listen: [3, 8]
❓ Er listen kortere enn 2? Nei -> Splitt
✅ Splitt listen i to
❕ [3] - [8]
✅ Repeter merge-sort på venstre, og høyre
✅ Kombiner de sorterte listene -> [3, 8]
✅ Returner listen

Steg R.L.L (Right, Left, Left)

✔️ Listen: [3]
❓ Er listen kortere enn 2? Ja -> Return

Steg R.L.R (Right, Left, Right)

✔️ Listen: [8]
❓ Er listen kortere enn 2? Ja -> Return

Steg R.R (Right, Right)

✔️ Listen: [5, 4]
❓ Er listen kortere enn 2? Nei -> Splitt
✅ Splitt listen i to
❕ [5] - [4]
✅ Repeter merge-sort på venstre, og høyre
✅ Kombiner de sorterte listene -> [4, 5]
✅ Returner listen

Steg R.R.L (Right, Right, Left)

✔️ Listen: [5]
❓ Er listen kortere enn 2? Ja -> Return

Steg R.R.R (Right, Right, Right)

✔️ Listen: [4]
❓ Er listen kortere enn 2? Ja -> Return

➕Ekstra:

Oppgave E1a - Sortere Tekst

Her skal du implementere en sorterings-algoritme som kan sortere tekst alfabetisk. Dette kan faktisk fungere for alle algoritmene dere har gjort (utenom Counting Sort fra Level 1 - Ekstra).

Oppgaven: Velg én av algoritmene fra en tidligere oppgave, gjør den om til å kunne sortere tekst.

Hvordan sammenlignes tekst?

Tekst kan faktisk sammenlignes! Men det er kanskje ikke så innlysende hvordan. Se for deg et eksempel med disse to ordene:
apple og banana. Hvilket ord bør bli sortert først? Jo, det gir jo mening at det bør være apple, siden det begynner på a.

Vi kan se på at en sammenligning sjekker om et svar er -1, 0 eller 1. Er svaret:

-1 så er teksten “mindre”, altså bør havne tidligere
0 så er teksten helt lik.
1 så er teksten “større”, altså bør havne senere

Før du lager sorterings-algoritmen

Store og Små bokstaver?

Det er opp til deg om du vil ignorere store eller små bokstaver.

Hvis du vil at B er det samme som b kan du bruke .lower()
Eventuelt kan du implementere din egen lower() funksjon hvis du vil ha enda mer challenge.
Referer til ASCII tabellen for å finne ut hvordan du kan endre på verdier med en matte-utregning.

Tips til framgangsmåte for Tekst-sammenlignings Algoritme

Bruk en tellevariabel i = 0
Bruk en while loop til å sammenligne bokstav for bokstav, øk i med 1 hver runde
Pass på index out of bounds med å sjekke at i er mindre enn lengden til tekst 1 eller tekst 2.
Sammenlign om tekst1[i] er lik tekst2[i], hvis ikke, sjekk om bokstaven er mindre eller større. Returner -1 eller 1.
Dersom while ikke returnerer, sjekk om lengdene er like. Hvis de er like, returner 0, ellers, returner -1

Bruk deretter denne tekst-sorterings algoritmen i en sorterings-algoritme for å sortere tekst!

Hint!

Husk at nå får sammenligningen tre verdier, -1, 0, 1. Det betyr at du må endre på hvordan du setter sammen svaret i noen av sorterings-algoritmene.

Eksempel: I quick-sort må du legge til en middle del.

Oppgave E1b - Tekst eller Tall?

Endre på koden din i Oppgave E1a til å kunne sortere hele lister med tall eller hele lister med tekst. Dette kan du gjøre ved å sjekke typen til det du hiver inn.

Hva hvis listen består av både tall og tekst!?

Nei nå spør du godt du! Spør deg selv om det gir mening å sammenligne at 2 er større enn “eple”.

Lykke til! 😎