Algoritmer

Algoritmer#

Algoritmer er en sekvens med instruksjoner som skal gjennomføres for å løse en oppgave.

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 listen liste 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() returnere True

  • … 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.

  1. Lag en tom liste out.

  2. Ta ut den største verdien og legg den inn i out.

  3. 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.

  1. Hvis hagegnomen er ved første potte, så går han et steg videre.

  2. Hvis den potten han er ved er mindre enn den forrige så bytter han plass på disse. Deretter tar han seg et steg tilbake.

  3. Hvis potten han er ved er større enn den forrige så går han et steg fremover.

  4. 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.

Contents