Kap 2.3 – Sökning och sortering

Mål med lektionen

När du har arbetat klart med denna lektion ska du:

• Förstå hur man söker efter ett värde i en lista.
• Känna till skillnaden mellan linjär och binär sökning.
• Känna till hur enkla sorteringsalgoritmer fungerar på en övergripande nivå.
• Kunna sortera listor med Pythons inbyggda metoder sort() och sorted().
• Förstå när olika typer av sökning och sortering är användbara, utan krav på att skriva egna sök- eller sorteringsalgoritmer från grunden.

Så här lär du dig bäst

Börja med att testa exempel med små listor och skriv gärna ut varje steg. Analysera hur många steg som krävs vid olika metoder. Målet är att känna till hur några vanliga sök- och sorteringsalgoritmer fungerar, men i egna program ska du i första hand använda Pythons inbyggda verktyg.

Sökning i listor

Sökning betyder att programmet letar efter ett värde i en samling data. Resultatet kan till exempel vara indexet där värdet finns, eller -1 om värdet saknas.

Linjär sökning

Linjär sökning går igenom varje element i listan tills rätt värde hittas.

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

    return -1

names = ["Anna", "Bo", "Sara"]
print(linear_search(names, "Bo"))  # 1

Fördel: fungerar alltid. Nackdel: kan bli långsam för stora listor.

Steg för steg: så fungerar koden

1. def linear_search(lst, target): skapar en funktion som tar emot två saker: en lista och värdet vi letar efter.
2. for i in range(len(lst)): går igenom listans index från 0 till sista positionen. Om listan har tre element blir indexen 0, 1 och 2.
3. if lst[i] == target: jämför elementet på den aktuella positionen med det vi söker efter.
4. Om värdet hittas körs return i. Funktionen skickar då tillbaka indexet och avslutas direkt.
5. Om loopen hinner gå igenom hela listan utan träff körs return -1. Det betyder att värdet inte finns i listan.

I exemplet är listan ["Anna", "Bo", "Sara"] och vi söker efter "Bo". Programmet jämför först "Anna" på index 0. Det är fel. Sedan jämför det "Bo" på index 1. Det är rätt, därför returnerar funktionen 1.

Binär sökning

Binär sökning är mycket snabbare, men kräver att listan är sorterad.

Viktigt: Binär sökning fungerar inte korrekt på en osorterad lista. Om listan inte är sorterad ska du antingen sortera den först eller använda linjä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

numbers = [3, 6, 9, 12, 15]
print(binary_search(numbers, 12))  # 3

Binär sökning halverar sökområdet varje gång, vilket gör metoden effektiv för stora sorterade listor.

Steg för steg: så fungerar binär sökning

1. Listan måste först vara sorterad. I exemplet är listan [3, 6, 9, 12, 15].
2. low = 0 betyder att sökområdet börjar vid första indexet i listan.
3. high = len(lst) - 1 betyder att sökområdet slutar vid sista indexet.
4. while low <= high: fortsätter söka så länge det finns ett möjligt område kvar.
5. mid = (low + high) // 2 räknar ut mittenpositionen i det aktuella sökområdet.
6. Om lst[mid] == target är värdet hittat och funktionen returnerar indexet mid.
7. Om lst[mid] < target ligger målet till höger, eftersom listan är sorterad. Då flyttas low till mid + 1.
8. Annars ligger målet till vänster. Då flyttas high till mid - 1.
9. Om sökområdet tar slut utan träff returneras -1.

I exemplet söker programmet efter 12. Först tittar det på mittenvärdet 9. Eftersom 12 är större än 9 behöver programmet bara söka i högra delen av listan. Där hittar det 12 på index 3.

När ska du använda vilken sökning?

• Använd linjär sökning när listan är liten eller inte sorterad.
• Använd binär sökning när listan redan är sorterad och du behöver söka snabbt.
• I vanliga Pythonprogram använder du ofta inbyggda verktyg först, men egna algoritmer hjälper dig att förstå vad som händer bakom kulisserna.

Sortering av listor

Inbyggd sortering

Python gör det enkelt att sortera listor:

sort() och sorted() använder Pythons inbyggda sortering. Den är snabb, stabil och optimerad för många vanliga typer av data. I riktiga program ska du därför nästan alltid använda sort() eller sorted() i stället för att skriva en egen sorteringsalgoritm från grunden. Läs mer i Pythons Sorting HOWTO.

Skillnaden är att sort() ändrar listan direkt, medan sorted() skapar en ny sorterad lista och lämnar originalet oförändrat.

numbers = [5, 3, 9, 1]
numbers.sort()  # Ändrar listan direkt
print(numbers)  # [1, 3, 5, 9]

names = ["Zara", "Adam", "Lilly"]
sorted_names = sorted(names)  # Skapar ny lista
print(sorted_names)

Egen sortering: bubble sort

Bubble sort används mest i undervisning. Den visar principen för jämförelse och byte, som återkommer i många sorteringsalgoritmer.

I riktiga projekt använder du nästan alltid Pythons inbyggda sort() eller sorted(). Bubble sort är med här för att visa hur en sorteringsalgoritm kan byggas upp steg för steg.

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

print(bubble_sort([9, 3, 7, 1]))  # [1, 3, 7, 9]

Öva själv

1. Använd .sort() för att sortera en lista med användarnamn.
2. Använd sorted() för att skapa en sorterad kopia utan att ändra originallistan.
3. Skapa ett program som frågar efter 5 tal, sorterar dem med sort() eller sorted() och söker efter ett valfritt tal.

När du har försökt själv kan du ladda ner ett lösningsförslag: kap2-3-sokning-sortering-losningsforslag.py

Testa dina lösningar med flera olika fall:

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

Reflektion

• Vilka fördelar har inbyggda metoder jämfört med att skriva egna algoritmer?
• När är det värt att använda binär sökning istället för linjär?
• Hur kan sortering göra andra delar av ett program mer effektiva?