Sökning och sortering

Mål

Efter lektionen ska du kunna...

• känna till hur sökning i listor fungerar
• förklara principen bakom linjär och binär sökning
• sortera listor med sort() och sorted()
• förstå grundidén i bubble sort utan att behöva skriva den själv

Viktigt

Du ska känna till principerna

Du behöver inte kunna skriva egna sökalgoritmer från grunden.

Du behöver inte kunna skriva egna sorteringsalgoritmer från grunden.

Du ska känna till några typer och förstå hur de fungerar.

I egna Pythonprogram använder du oftast inbyggda verktyg.

Sökning

Vad letar vi efter?

Programmet har en lista.

Programmet har ett mål, till exempel "Bo".

Resultatet kan vara indexet där målet finns.

Om värdet saknas kan funktionen returnera -1.

Linjär sökning

Gå igenom ett i taget

def linear_search(lst, target):
    for i in range(len(lst)):
        if lst[i] == target:
            return i

    return -1

Exempel

Sök efter "Bo"

names = ["Anna", "Bo", "Sara"]

linear_search(names, "Bo")

Stegvis

Jämförelserna

i = 0 → names[0] == "Bo"? → "Anna" == "Bo" → nej
i = 1 → names[1] == "Bo"? → "Bo" == "Bo"   → ja
return 1

Sökningen stannar direkt när värdet hittas.

Linjär sökning

Fördel och nackdel

• fördel: fungerar på osorterade listor
• fördel: enkel att förstå
• nackdel: kan behöva kontrollera hela listan

Binär sökning

Snabbare men kräver sortering

Listan måste vara sorterad.

Algoritmen tittar på mitten.

Sedan kastas halva sökområdet bort.

Det upprepas tills värdet hittas eller området tar slut.

Kod

Binär sökning

def binary_search(lst, target):
    low = 0
    high = len(lst) - 1

    while low <= high:
        mid = (low + high) // 2

        if lst[mid] == target:
            return mid
        elif lst[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1

Exempel

Sök efter 12

numbers = [3, 6, 9, 12, 15]

low = 0
high = 4
mid = (0 + 4) // 2  # 2
numbers[2]          # 9

12 är större än 9, så vänstra delen kan ignoreras.

Stegvis

Binär sökning halverar

[3, 6, 9, 12, 15]
       ↑
      9 är för lågt

[12, 15]
 ↑
12 hittas på index 3

Val

Vilken sökning passar?

• linjär sökning: liten eller osorterad lista
• binär sökning: sorterad lista och många sökningar
• inbyggda Pythonverktyg används ofta i riktiga program

Sortering

Ordna listans värden

Sortering gör data lättare att läsa.

Sortering kan göra sökning mer effektiv.

Python har färdiga metoder för detta.

sort

sort() ändrar originalet

numbers = [5, 3, 9, 1]
numbers.sort()

[1, 3, 5, 9]

sorted

sorted() skapar en ny lista

names = ["Zara", "Adam", "Lilly"]
sorted_names = sorted(names)

names        # ["Zara", "Adam", "Lilly"]
sorted_names # ["Adam", "Lilly", "Zara"]

Jämförelse

sort() eller sorted()?

• sort(): ändrar listan direkt
• sorted(): returnerar en ny sorterad lista
• använd sorted() när originalordningen ska vara kvar

Bubble sort

Förstå principen

Bubble sort används mest i undervisning.

Den jämför två grannar.

Om de ligger i fel ordning byter de plats.

I riktiga program använder du oftast sort() eller sorted().

Kod

Bubble sort

def bubble_sort(lst):
    for i in range(len(lst)):
        for j in range(0, len(lst) - i - 1):
            if lst[j] > lst[j + 1]:
                lst[j], lst[j + 1] = lst[j + 1], lst[j]

    return lst

Stegvis

Första varvet

[9, 3, 7, 1]
 9 > 3 → byt  → [3, 9, 7, 1]
 9 > 7 → byt  → [3, 7, 9, 1]
 9 > 1 → byt  → [3, 7, 1, 9]

Det största värdet har bubblat längst bak.

Öva själv

Tre uppgifter

1. Sortera användarnamn med .sort().
2. Skapa en sorterad kopia med sorted().
3. Fråga efter fem tal, sortera dem och sök efter ett tal.

Testfall

Testa flera situationer

• värdet finns först
• värdet finns sist
• värdet finns inte alls
• listan är redan sorterad
• listan är i omvänd ordning

Sammanfattning

Kom ihåg

• Du ska förstå principen bakom linjär och binär sökning.
• Binär sökning kräver sorterad lista.
• sort() ändrar originalet.
• sorted() skapar en ny lista.
• Bubble sort visar jämförelse och byte, men används mest för förståelse.