Sortering och sökning

Binärsökning är hur du slår upp ett ord i en ordbok: öppna i mitten, avgör om ordet ligger före eller efter, upprepa i halvan som återstår.

Varje jämförelse halverar sökområdet. Det ger $\log_2 n$ steg:

En miljard element på trettio jämförelser. Villkoret är att listan är sorterad.

Merge sort bygger på samma halveringsidé, baklänges: dela listan i två, sortera varje halva (rekursivt), och flät ihop de två sorterade halvorna. Att fläta ihop två sorterade listor är enkelt — jämför de främsta och ta den minsta.

Det ger $O(n\log n)$: $\log n$ nivåer av delning, och $n$ arbete på varje nivå.

De vanliga algoritmerna:

Stabil betyder att element med lika nyckel behåller sin inbördes ordning. Det spelar roll när man sorterar i flera steg: sortera först på förnamn, sedan på efternamn — med en stabil sortering blir personer med samma efternamn sorterade på förnamn.

Pythons sorted är Timsort, en hybrid som letar efter redan sorterade avsnitt («runs») och flätar ihop dem. På delvis sorterad data — vilket verklig data ofta är — blir den nästan linjär.

När lönar det sig att sortera först? Sortering kostar $O(n\log n)$ en gång, sedan kostar varje sökning $O(\log n)$ i stället för $O(n)$. Med $k$ sökningar:

$\underbrace{n\log n + k\log n}_{\text{sortera först}} \quad\text{mot}\quad \underbrace{kn}_{\text{linjär sökning}}$

Med $n = 10^6$: en enda sökning → sortera inte. Tusen sökningar → sortera.

Men i Python är svaret oftast en annan: behöver du bara «finns detta?» är en set ännu bättre — O(1) per fråga, ingen sortering. Sortering behövs när du vill ha ordning, intervall («alla mellan 10 och 20») eller närmaste värde.

Den klassiska buggen i binärsökning är while vanster < hoger i stället för <=, eller att uppdatera gränserna till mitt i stället för mitt ± 1. Det första missar sista elementet; det andra ger en oändlig loop. Båda är lätta att skriva och svåra att se.

def binarsok(sorterad, mal):
    v, h = 0, len(sorterad) - 1
    while v <= h:                          # <= : annars missas sista elementet
        m = (v + h) // 2
        if sorterad[m] == mal:
            return m
        if sorterad[m] < mal:
            v = m + 1                      # m + 1, inte m — annars oändlig loop
        else:
            h = m - 1
    return -1

def merge_sort(x):
    if len(x) <= 1:
        return x
    m = len(x) // 2
    return flata(merge_sort(x[:m]), merge_sort(x[m:]))

def flata(a, b):
    ut, i, j = [], 0, 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:                   # <= gör sorteringen stabil
            ut.append(a[i]); i += 1
        else:
            ut.append(b[j]); j += 1
    return ut + a[i:] + b[j:]

print(binarsok([1, 3, 5, 7, 9, 11], 9))        # 4
print(binarsok([1, 3, 5, 7, 9, 11], 4))        # -1
print(merge_sort([5, 2, 9, 1, 5, 6]))          # [1, 2, 5, 5, 6, 9]

# Stabilitet i praktiken: sortera i två steg
elever = [("Svensson", "Bo"), ("Andersson", "Cim"), ("Svensson", "Ada")]
steg1 = sorted(elever, key=lambda e: e[1])          # förnamn
steg2 = sorted(steg1, key=lambda e: e[0])           # efternamn — stabil
print(steg2)
# [('Andersson', 'Cim'), ('Svensson', 'Ada'), ('Svensson', 'Bo')]

# I praktiken: använd standardbiblioteket
import bisect
sorterad = [1, 3, 5, 7, 9]
print(bisect.bisect_left(sorterad, 5))          # 2 — index där 5 börjar
print(bisect.insort(sorterad, 6) or sorterad)   # [1, 3, 5, 6, 7, 9]