Quicksort

Quicksort är en sorteringsalgoritm för att på ett effektivt och snabbt sätt sortera en större mängd data i storleksordning. Den uppfanns 1960 av Tony Hoare i dåvarande Sovjetunionen vid Moskvas universitet. Sedan dess har enormt många implementationer av quicksort gjorts.

Principen bygger på följande steg

1. Välj ett tal från listan att utgå från
2. Ordna elementen så att alla tal större än det valda ligger ovanför och alla tal lägre än det valda ligger under
3. Sortera subsetten rekursivt på samma vis

Quicksort är en jämförande sorteringsmetod.

Pseudokod

function quicksort(array)
    if length(array) < 2
        return array // en array med 0-1 element är redan sorterad
    pivot = array[n/2]; // välj en sorteringspunkt, kan vara vilket som egentligen
    new array lesser[n], greater[n] // skapa två arrayer som kan hålla resultaten
    int i,j = 0
    for each i in array
        if i < pivot 
            lesser[j++] = array[i] // elementet tillhör lesser
        else
            greater[k++] = array[i] // elementet tillhör greater
    quicksort(lesser) // Rekursivt sortera mindre element
    quicksort(greater) // Rekursivt sortera större element
    // När all rekursion är klar kommer exkveringen fortsätta här
    int j=0
    new sorted_array[n]
    for each i in lesser
        sorted_array[j++] = lesser[i]
    sorted_array[j++] = pivot
    for each i in greater
        sorted_array[j++] = greater[i]
return sorted_array