Visa källa för 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

# Välj ett tal från listan att utgå från
# Ordna elementen så att alla tal större än det valda ligger ovanför och alla tal lägre än det valda ligger under
# 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

[[Category:Programmering]]
[[Category:Algoritmer]]