DA3009 Programmeringsteknik för datorlingvister, prgdl11

Komplexitetsanalys, sökning, sortering

• Komplexitetsanalys
• Sökning
  • Linjärsökning
  • Binärsökning
• Sorteringsalgoritmer
  • Urvalssortering (Selection sort)
  • Bubbelsortering (Bubble sort)
  • Insättningssortering (Insertion sort)
  • Damerna först
  • Quicksort
  • Mergesort (Samsortering)
  • Divide and conquer
  • Räknesortering (Distribution count)

Komplexitetsanalys

Istället för att ange den exakta tidsfunktionen T(n) nöjer vi oss med att ange ordoklassen O(n).

• cF(n) anger en övre gräns för T(n) då n är stort.
• Vi behöver bara ta bara med den term som växer snabbast.
• Vi kan bortse från multiplikation med konstant.
• Det spelar ingen roll vilken logaritm vi använder.

• För små indata är analys onödig - använd den enklaste algoritmen!
• Inläsning från fil tar längre tid än åtkomst av redan inlästa värden.
• Minnesåtgång kan också vara relevant.

Sökning

• Vi söker efter något element i en lista med n element.
• Det element vi söker efter karakteriseras av en söknyckel (eng key) men kan också ha andra data.

• Vad ska hända om det sökta elementet inte finns med?
• Kan det finnas flera element med samma nyckel? Vill man isåfall hitta alla?

Linjärsökning (Sequential search)

• Sök igenom elementen i tur och ordning.
• Bryt när det sökta elementet påträffas eller när det uppenbaras att det sökta elementet inte finns med.

Här följer en funktion för linjärsökning i en lista.

def sequentialSearch(alist, item):
    for x in alist:
        if x == item:
            return True
    return False

Binärsökning

• Beräkna intervallets mittpunkt.
• Avgör om det sökta elementet finns i första eller andra halvan och fortsätt söka där.

def binarySearch(alist, item):
"""Söker i "alist" efter "item". Returnerar True om den hittas, False annars"""
    first = 0
    last = len(alist)-1
    found = False

    while first <= last and not found:
        midpoint = (first + last)/2
        if alist[midpoint] == item:
	    found = True
        else:
            if item < alist[midpoint]:
                last = midpoint-1
            else:
                first = midpoint+1
    return found

Sortering

Urvalssortering (Selection sort)

• Sök igenom listan efter minsta värdet. (N-1 jämförelser)
• Flytta det till första positionen. (Ett byte)
• Sök efter näst minsta värdet. (N-2 jämförelser)
• Flytta det till andra positionen. (Ett byte)
- - -

def urvalssortera(data):
    n = len(data)
    for i in range(n):
        minst = i
        for j in range(i+1,n):
            if data[j] < data[minst]:
                minst = j
        data[minst],data[i] = data[i], data[minst]

Urvalssorteringsanimation från Hong Kongs universitet.

Bubbelsortering (Bubble sort)

• Byt första och andra om dom står i fel ordning. (En jämförelse, ett byte)
• Byt andra och tredje om dom står i fel ordning. (En jämförelse, ett byte)
- - -
• Bubbla igenom listan gång på gång tills inga byten sker.

Bubbelsortanimation från universitetet i Oldenburg.

Insättningssortering (Insertion sort)

• Jämför med varje tidigare värde i listan.
• Om det nya värdet är mindre gör vi plats genom att flytta det tidigare värdet ett snäpp åt höger.
• Flytta fram så många värden som behövs för att sätta in nya värdet på rätt plats.
• Stoppa in det nya värdet.

Komplexiteten är i allmänhet O(N²) men den är lite snabbare än urvalssortering i praktiken eftersom en flytt är snabbare än ett byte. För att sortera in ett nytt värde i en redan sorterad lista är insättning bäst.

def insattningssortera(data):
    n = len(data)
    for i in range(1, n):
        varde = data[i]
        plats = i
        while plats > 0 and data[plats-1] > varde:
            data[plats] = data[plats-1]
            plats = plats - 1
        data[plats] = varde

Animation av insättningssortering från Indian Institute of Technology i Kanpur.

Damerna först

1. Sätt ett pekfinger i var ände av listan!
2. Rör fingrarna mot varandra tills vänstra fingret fastnat på en herre och högra fingret på en dam!
3. Låt damen och herren byta plats!
4. Upprepa från 2 tills fingrarna korsats!

Quicksort

• Bestäm vilka värden som ska kallas damer.
• Partitionera listan så att damerna kommer först.
• Sortera varje segment för sej.

def quicksort(data):
    sista = len(data) - 1
    qsort(data, 0, sista)

def qsort(data, i, j):
    pivotindex = (i+j)//2
    data[pivotindex], data[j] = data[j], data[pivotindex]
    k = partitionera(data, i-1, j, data[j])
    data[k], data[j] = data[j], data[k]
    if k-i > 1:
        qsort(data, i, k-1)
    if j-k > 1:
        qsort(data, k+1, j)

def partitionera(data, v, h, pivot):
    while True:
        v = v + 1
        while data[v] < pivot:
            v = v + 1
        h = h -1
        while h != 0 and data[h] > pivot:
            h = h -1
        data[v], data[h] = data[h], data[v]
        if v >= h: break
    data[v], data[h] = data[h], data[v]
    return v

Komplexiteten blir i allmänhet O(N log N). Det beror på att man kan dela listan på mitten log N gånger. Exakt hur snabb den är beror på hur man avgör vilka värden som ska vara damer. Om man tar det första värdet i listan och utnämner det och alla mindre värden till damer, så blir Quicksort mycket långsam för redan nästan sorterade listor! Det bästa är att ta ut tre värden - det första, det sista och något i mitten - och låta det mellersta värdet bestämma vad som är damer. Det kallas median-of-three. Man kan visa att komplexiteten då blir 1.4 N log N i genomsnitt.

Merge Sort

• Dela listan i två hälften så långa listor.
• Sortera varje halva för sej.
• Samsortera till ursprungliga listan.

def mergesort(data):
    if len(data) > 1:
        mitten = len(data)//2
        vensterHalva = data[:mitten]
        hogerHalva = data[mitten:]

        mergesort(vensterHalva)
        mergesort(hogerHalva)

        i, j, k = 0, 0, 0
    
        while i < len(vensterHalva) and j < len(hogerHalva):
            if vensterHalva[i] < hogerHalva[j]:
                data[k] = vensterHalva[i]
                i = i + 1
            else:
                data[k] = hogerHalva[j]
                j = j + 1
            k = k + 1
                
        while i < len(vensterHalva):
            data[k] = vensterHalva[i]
            i = i + 1
            k = k + 1
                    
        while j < len(hogerHalva):
            data[k] = hogerHalva[j]
            j = j + 1
            k = k + 1

Mergesortanimation från North Carolina State University.

Divide and conquer

Inom datalogi används detta uttryck för att beskriva en lösningsmetod där man delar upp ett problem i två eller flera delproblem och löser dessa var för sig. Delproblemen löses enklast med rekursion!

Quicksort och mergesort är två exempel på divide-and-conquer-principen.

Räknesortering (Distribution count)

• Läs igenom filen och räkna hur många det finns av varje nyckelvärde.
• Dela in listan i lagom stora segment för denna distribution.
• Läs filen igen och lägg in varje värde i sitt segment.