Föreläsning 7: Sortering

• Urvalssortering (Selection sort)
• Bubbelsortering (Bubble sort)
• Insättningssortering (Insertion sort)
• Damerna först
• Quicksort
• Mergesort (Samsortering)
• Divide and conquer
• Räknesortering (Distribution count)

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.

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

3

4

3

3

5

3

5

3

5

4

5

3

4

3:6
4:3
5:4

3

3

3

4

Stabil sortering

Anna Andersson
Anna Johansson
Bertil Andersson
Bertil Johansson

Anna Andersson
Bertil Andersson
Anna Johansson
Bertil Johansson

Sortering av större mängder data