Föreläsning 7 Sortering

Sortering är en av dom vanligaste uppgifterna för ett program. Här följer en beskrivning av de viktigaste sorteringsalgoritmerna!

Urvalssortering (Selection sort)
Bubbelsortering (Bubble sort)
Insättningssortering (Insertion sort)
Damerna först
Quicksort
Mergesort (Samsortering)
Divide and conquer
Räknesortering (Distribution count)
Animationer av sorteringsalgoritmer från visualgo.net
Quicksortdans från AlgoRythmics

Urvalssortering (Selection sort)

Vi tänker oss att vi ska sortera en lista med n tal.

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)

Totalt krävs n(n-1)/2 jämförelser och N-1 byten, helt oberoende av hur pass osorterad listan är från början. Tiden är alltså i stort sett proportionell mot kvadraten på N. Man säger att komplexiteten är O(n²).

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]

Bubbelsortering (Bubble sort)

En något smartare metod än urvalssortering är denna:

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.

Totalt krävs i värsta fall n(n-1)/2 jämförelser och lika många byten. Men om listan är nästan sorterad från början räcker det med några få genomgångar och då blir bubbel snabbare än urval.

Insättningssortering (Insertion sort)

Denna metod känns särskilt naturlig om man får värden ett efter ett (t ex om dom läses in från en fil) och man vill sortera in dom i en lista. Här sorterar vi in ett värde i taget på följande vis:

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.

Om alla värden redan finns i listan sorterar vi in ett värde i taget, med början från det andra.

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

Damerna först

Den enklaste sorteringsuppgiften är att sortera om en personlista med damerna först och den smarta algoritmen kallas damerna-först-sortering.

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

Idén kan utvecklas till Quicksort, som är den snabbaste av alla sorteringsalgoritmer.

Quicksort

Damerna-först-algoritmen med två pekfingrar används i Quicksort. Först bestämmer man vilka (små) nyckelvärden som ska kallas damer. Resten kallas herrar och så utför man algoritmen. Listan delas alltså i två segment, det första med små värden, det andra med stora värden. Nu behöver man bara sortera segmenten var för sej. Det här är en rekursiv tanke!

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, low, high):
    pivotindex = (low+high)//2
    # flytta pivot till kanten
    data[pivotindex], data[high] = data[high], data[pivotindex]  
    
    # damerna först med avseende på pivotdata
    pivotmid = partitionera(data, low-1, high, data[high]) 
    
    # flytta tillbaka pivot
    data[pivotmid], data[high] = data[high], data[pivotmid]       
    
    if pivotmid-low > 1:
        qsort(data, low, pivotmid-1)
    if high-pivotmid > 1:
        qsort(data, pivotmid+1, high)

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

Om man har flera sorterade småfiler är det lätt att samsortera dom till en fil. Det här kan man också göra med en lista om man har extrautrymme för att kopiera den till två andra hälften så långa listor. Det här ger en rekursiv tanke!

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

Komplexiteten blir O(n log N), lika snabb som quicksort men kräver extra minnesutrymme. Om första halvan av listan a ska samsorteras med andra halvan kopierar man först över allting till hjälplistan b och sorterar sedan tillbaka från b till a. Detta förfarande kallas merge och programmeras lämpligen som en egen metod.

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

Divide and conquer

En kanske inte så sympatisk härskarteknik som går ut på att så split mellan sina undersåtar för att rikta deras misstro mot varandra istället för mot härskaren kallas på engelska divide and conquer. (På svenska säger vi söndra och härska, men det passar inte lika bra här.)

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)

Om man vet att det bara finns ett litet antal nyckelvärden, (t ex om man ska sortera Sveriges befolkning efter födelseår), så är distributionsräkning oslagbart snabbt. Det kräver att talen som sorteras in i listan hämtas från en annan lista eller fil.

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.

Komplexiteten blir O(n), men fungerar alltså bara om man har få nyckelvärden i förhållande till antalet data som ska sorteras.

Om man upprepar förfarandet för varje position (siffra eller bokstav) i de data som ska sorteras får man radixsortering!

3:6
4:3
5:4

Sortering av större mängder data

Alla metoderna ovan förutsätter att de data som ska sorteras kan lagras i primärminnet. Om så inte är fallet får man ta till extern sortering men det ingår inte i den här kursen.

Hur beskriver man en algoritm?

Ur kursens betygskriterier:
För betyg A ska kraven för betyg C vara uppfyllda, och man ska dessutom kunna modifiera/kombinera algoritmer och datastrukturer för att lösa nya problem. Här ställs också höga krav på tydlighet i algoritmbeskrivningar.

Skilj på att förklara hur en algoritm fungerar och att konstruera en algoritm.

Vad är indata till algoritmen?
Vad är utdata?
Punktvis (inte löptext). Ordningen är viktig!
När avslutas algoritmen?