Algoritmer#
Algoritmer er en sekvens med instruksjoner som skal gjennomføres for å løse en oppgave.
Linear search#
Å sjekke om et objekt er i en liste, string eller tuppel er enkelt med in
-nøkkelordet.
liste = ["🌼", "🌸", "🌹", "🌻"]
if "🌹" in liste:
print(True)
True
Det som brukes under panseret i Python 🐍 er en algoritme som heter Linear search.
Hvis man skal finne objektet
x
går man gjennom hvert objektobjekt
i listen.Hvis man møter på et
objekt
som er liktx
, returnerer manTrue
og slutter å leteHvis man har gått igjennom hele listen uten hell, så returnerer man
False
Lag en pseudokode og/eller en implementasjon av denne algoritmen i Python før du ser på løsningsforslagene.
Pseudokode: Linear search
En pseudokode for Linear search kan se ut på følgende måte:
FUNCTION linear_search(x, liste)
FOR object IN liste
IF x EQUALS object RETURN True
RETURN False
Python 🐍: Linear search
En implementasjon av Linear search i Python kan se ut på følgende måte:
def linear_search(x, liste):
for object in liste:
if x == object: return True
return False
liste = ["🌼", "🌸", "🌹", "🌻"]
print(linear_search("🌹", liste))
print(linear_search("🌷", liste))
True
False
Linear search er treigt! 🐌
Linear search er utrolig treigt hvis man må gjøre dette på en stor liste mange ganger… i verste fall må man jo sjekke hvert eneste element i listen!
Løsningen for dette er å være lur med å bruke andre datatyper som Mengder eller Ordbøker der det passer. Objekter i en mengde eller ordbok er lagret på en annen måte som gjør at man ikke trenger å lete gjennom alle objekter i rekkefølgen.
Det er omtrent like raskt å lete etter et objekt i en liten mengde med under ti tall, som i en massiv mengde med millarder av tall. Sånn er det ikke med lister.
Sorteringsalgoritmer#
Sorteringsalgoritmer er algoritmer som sorterer lister fra minst til størst. Det høres kanskje banalt ut, men det er en av de viktigste tingene i informatikken. Jeg digger sorteringsalgoritmer.
Bubble sort 🫧#
Bubble sort er en relativt enkel algoritme (i forhold til andre sorteringsalgoritmer).
Gå gjennom hvert objekt med indeks
n
i listenliste
helt til den nest siste indeksen.For hvert objekt, sammenlign objektet med indeks
n
med det neste objektet.Hvis det neste objektet er mindre enn det vi er på, bytt plassen deres i listen.
Hvis du når slutten av listen og har byttet plass minst én gang, så går du gjennom listen igjen.
Hvis du når slutten av listen og ikke har byttet plass noen ganger, så er listen ferdig sortert.
Forsøk å implementere dette selv, men ikke bli lei deg om du må sjekke løsningsforslaget under 🙂
Python 🐍: Bubble sort
En implementasjon av Bubble sort i Python kan se ut på følgende måte:
def bubble_sort(liste):
# Lager en kopi av listen slik at vi ikke endrer på den opprinnelige listen in-place.
liste = liste.copy()
# For å holde styr på om det er byttet (starter som sant for å starte while-løkken)
byttet = True
# Stopper når det ikke har blitt byttet
while byttet:
# Starter med å si at det ikke har blitt byttet.
byttet = False
# Hver indeks til den nest siste indeksen (for å unngå IndexError når vi sjekker neste objekt)
for n in range(len(liste) - 1):
# Hvis neste objekt er mindre enn det vi er på
if liste[n + 1] < liste[n]:
# Setter inn neste objekt ved indeksen vi er på
liste.insert(n, liste[n + 1])
# Fjerner objektet som nå har blitt flyttet et hakk
liste.pop(n + 2)
# Når det har skjedd et bytte, blir bytte = True og løkken fortsetter
byttet = True
return liste
print(bubble_sort([6, 12, 3, 5, 9, 3, 4, 1]))
[1, 3, 3, 4, 5, 6, 9, 12]
Oppgaver#
Oppgave 1 ✔️
I denne oppgaven skal vi sjekke om en liste er sortert.
Lag en funksjon er_sortert()
som tar inn en liste liste
og sjekker om den er sortert i stigende rekkefølge.
Hvis listen er sortert skal
er_sortert()
returnereTrue
… og hvis ikke skal den returnere
False
er_sortert([1, 2, 3]) -> True
er_sortert([1, 3, 2]) -> False
Du får lov til å bruke sorted()
-funksjonen for å sjekke.
Oppgave 2 🥴
Sorteringsalgoritmen Bogo sort er en slags spøk blant informatikere. Den innebærer å stokke om på en liste helt til den er sortert riktig.
Lag en funksjon bogo_sort()
som bruker er_sortert()
-funksjonen fra forrige oppgave til å returnere en sortert liste.
Hint: Stokking
Man kan stokke om på en liste med shuffle()
fra random
-pakken.
from random import shuffle
liste = [1, 2, 3, 4, 5]
shuffle(liste)
print(liste)
[4, 2, 1, 3, 5]
Oppgave 3 📏
Lag en funksjon nest_størst()
som går gjennom en liste og returnerer den nest største verdien i listen.
Oppgave 4 📦
En enkel, men ganske dårlig, sorteringsalgoritme kan beskrives på følgende måte.
Lag en tom liste
out
.Ta ut den største verdien og legg den inn i
out
.Når den opprinnelige listen er tom, returner
out
.
Implementer algoritmen som en funksjon max_sort()
i Python.
Løsningsforslag
Legg merke til at jeg kjører liste.copy()
for å unngå at listen som puttes inn faktisk blir tømt.
def max_sort(liste):
liste = liste.copy()
out = []
while len(liste) > 0:
størst = max(liste)
liste.remove(størst)
out.append(størst)
return out
Oppgave 5 🪴
Sorteringsalgoritmen Gnome sort er beskrevet på følgende måte.
En hagegnom skal sortere en rad med blomsterpotter i stigende rekkefølge.
Hvis hagegnomen er ved første potte, så går han et steg videre.
Hvis den potten han er ved er mindre enn den forrige så bytter han plass på disse. Deretter tar han seg et steg tilbake.
Hvis potten han er ved er større enn den forrige så går han et steg fremover.
Når gnomen tar steget videre fra den siste potten (og da ikke har en potte ved siden av seg) så stopper han. … og vipps! Alle pottene er sortert 🪴
Implementér Gnome sort som en funksjon gnome_sort()
i Python. Den skal ta en liste liste
og returnere en sortert versjon av listen.