Sorteringsalgoritmer

De flesta programmeringsspråk har inbyggda sorteringsfunktioner. De använder antingen en specifik eller en kombination av flera sorteringsalgoritmer. Pythons sort()-metod använder till exempel Timsort som är en blandning av “merge sort” och “insertion sort”. Vi ska titta närmare på de vanligaste sorteringsalgoritmerna och se hur de är implementerade och vad som kan dölja sig bakom exempelvis array.sort().

#Förutsättning

Du kan grunderna i Python och du vet vad variabler, typer och funktioner innebär.

#De vanligaste sorteringsalgoritmerna

Använd er av VisuAlgo för att visualisera er hur algoritmerna fungerar och se pseudo kod.

#Bubble sort

Bubble sort är en av de enklaste sorteringsalgoritmerna, både att implementera och att förstå. Det största (eller minsta) värdet “bubblas” upp i listan följt av det näst största värdet. Varje “bubbla” går igenom hela listan en gång.

VisuAlgo bubbelsort

1. Algoritmen jämför två intilliggande värden (a, b).
2. Om värdena är i oordning byter de plats.
3. Upprepa steg 1 och 2 tills algoritmen har gått igenom hela listan. Nu borde det största talet vara sist i listan.
4. Upprepa steg 1-3. Då borde det näst högsta värdet vara näst sist i listan. Fortsätt upprepa steg 1-3 tills listan är sorterad.

Bubble sort går att implementera utan rekursion. Oftast används istället en nästad for-loop. Det går även bra med en while- och en for-loop.

def bubble_sort(items):
    """ Bubble sort """
    for i in range(len(items)):
        for j in range(len(items)-1-i):
            if items[j] > items[j+1]:
                items[j], items[j+1] = items[j+1], items[j] # Byt plats

    return items

Bubble sort dance

#Insertion sort

Insertion sort delar upp listan i en osorterad sektion och en sorterad sektion. Värdet från den osorterade sektionen sätts in i den sorterade sektionen på rätt plats. Värdena i den sorterade sektionen flyttas baserat på det nya värdet som ska placeras på rätt plats.

VisuAlgo Insertion sort

def insertion_sort(items):
    """ Insertion sort """
    for i in range(1, len(items)):
        j = i
        while j > 0 and items[j] < items[j-1]:
            items[j], items[j-1] = items[j-1], items[j]
            j -= 1

    return items

Insertion sort dance

#Quick sort

Quick sort använder sig utav ett pivot-värde. Efter valet av pivot är gjort så delar man upp listan i två delar. Den ena delen hanterar värdena som är mindre än pivot och den andra delen hanterar värdena som är större än pivot. Quick sort arbetar med fördel rekursivt där varje anrop till funktionen hanterar ett nytt pivot-värde baserat på den nya listan som skickats in. Bas-fallet är när listans längd har nått 1. Till slut så slår man samman de tre delarna.

VisuAlgo Quick sort

def quick_sort(items):
    """ Quicksort """
    if len(items) > 1:
        pivot_index = len(items) // 2
        smaller_items = []
        larger_items = []

        for i, val in enumerate(items):
            if i != pivot_index:
                if val < items[pivot_index]:
                    smaller_items.append(val)
                else:
                    larger_items.append(val)

        quick_sort(smaller_items)
        quick_sort(larger_items)
        items[:] = smaller_items + [items[pivot_index]] + larger_items

    return items

Här används // för att returnera en integer. (Enkel division / kan returnera en float). Vi ser även “enumerate()” som skapar tupler av elementen i listan och möjliggör indexering till exempel (i, val).

Quick sort dance

#Merge sort

Merge sort fungerar snarlikt quick sort. Den använder också “divide and conquer”-metoden med att dela upp listan till fler och sortera del-listorna separat, baserat på ett pivotvärde. Merge sort använder rekursion för att sortera del-listorna och när listan är nere på en längd av 1 ses den som klar.

VisuAlgo Merge sort

Merge sort dance

#Tidskomplexitet

En sak som skiljer de olika algoritmerna åt är deras tidskomplexitet. Tidskomplexitet kan ta ett eget kursmoment att förklara ingående vad det är och hur man räknar på det så artikeln förklarar enbart grunden.

Tänk dig tre kuber som står på golvet:
1. Liten: 1x1x1 meter
2. Mellan: 10x10x10 meter
3. Stor: 100x100x100 meter

#Linjär tidskomplexitet

Tänk dig nu att du ska dra ett streck längs golvet runt kuberna. Tar det 1 minut att rita runt den lilla kuben tar det ca 10 minuter att rita runt den mellanstora och ca 100 minuter att rita ett streck runt den stora. Detta kallas för "linjär tidskomplexitet". När man beskriver tidskomplexitet pratar man om Ordo och Big O. Linjär tidskomplexitet kan beskrivas med O(n).

#Kvadratisk tidskomplexitet

Nu är det dags att måla ena väggen på kuberna. Om det tar 1 minut att måla den lilla, tar det ca 100 minuter att måla den mellanstora och 10000 minuter att måla den stora.

Detta är för att den mellanstora är 10 gånger så stor som den lilla men ena väggen 10*10 gånger större. Det stora husets vägg är 100*100 gånger större. Kvadratisk tidskomplexitet kan beskrivas med O(n²)

#Kubisk tidskomplexitet

Om vi ska fylla kuberna med vatten. Tar det 1 minut att fylla den lilla kuben, tar det ca 1000 minuter att fylla den mellanstora kuben och ca 1 miljon minuter att fylla den stora.

Räknar vi på det är den mellanstora kubens volym 10*10*10 gånger större än den lilla kubens. Den stora kubens volym blir 100*100*100 gånger så stor. Kubisk tidskomplexitet kan beskrivas med O(n³).

#Konstant tidskomplexitet

Konstant tidskomplexitet är den tid det tar att till exempel ta ett kort på kuberna. Det är samma tid för alla så det kan beskrivas med O(1).

#Allmänt om tidskomplexitet

Olika algoritmer har som sagt olika tidskomplexitet, beroende på olika faktorer som påverkar dem. Några exempel på faktorer är:
* loopar
* if-satser
* mängden variabler
* antal gånger en rekursiv funktion anropar sig själv

Alla faktorer slås ihop och kan räknas ut så att man får fram tidskomplexiteten. När man räknar på faktorerna använder man oftast n med högst värde. Har man med både O(n²) och O(n³) är det då O(n³) som tas med i beräkningen.

Vi kan titta i tabellen för att se hur tidskomplexiteten snabbt kan påverka tiden för en algoritm:

Vi går inte in närmare på detta här utan nu har ni en kännedom om att det finns och används ofta i sorteringsalgoritmer för att se hur de kommer fungera med olika mängder element och vad man förvänta sig.

#Avslutningsvis

Det här var lite grunder om sorteringsalgoritmer. Hoppas ni har fått en liten förståelse vad som kan dölja sig bakom en array.sort() och liknande inbyggda funktioner.

#Revision history