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.
• Kunna sortera en lista med både inbyggda metoder och egen kod.
• Förstå när olika typer av sökning och sortering är användbara.

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. Pröva att lösa samma uppgift med både inbyggda funktioner och egna algoritmer för att få både förståelse och kontroll.

Sökning i listor

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", "Cleo"]
print(linear_search(names, "Bo"))  # 1

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

Binär sökning

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

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.

Sortering av listor

Inbyggd sortering

Python gör det enkelt att sortera listor:

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.

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. Skriv en funktion som söker efter ett namn i en lista med linjär sökning.
2. Använd .sort() för att sortera en lista med användarnamn.
3. Implementera en egen bubble sort och jämför resultatet med inbyggd sortering.
4. Skapa ett program som frågar efter 5 tal, sorterar dem och söker efter ett valfritt tal.

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?