algorithm
Snel sorteren

Opmerkingen

Quicksort Basics

Quicksort is een sorteeralgoritme dat een element kiest ("de pivot") en de array opnieuw rangschikt die twee partities vormt, zodat alle elementen minder dan de pivot ervoor komen en alle grotere elementen erna komen. Het algoritme wordt vervolgens recursief toegepast op de partities totdat de lijst is gesorteerd.

1. Lomuto partitie schema mechanisme:

Dit schema kiest een pivot die meestal het laatste element in de array is. Het algoritme houdt de index bij om de pivot in variabele i te plaatsen en elke keer dat een element kleiner dan of gelijk aan pivot wordt gevonden, wordt deze index opgehoogd en wordt dat element voor de pivot geplaatst.

partition(A, low, high) is
pivot := A[high]
i := low
for j := low to high – 1 do
    if A[j] ≤ pivot then
        swap A[i] with A[j]
        i := i + 1
swap A[i] with A[high]
return i

Snel sorteermechanisme:

quicksort(A, low, high) is
if low < high then
    p := partition(A, low, high)
    quicksort(A, low, p – 1)
    quicksort(A, p + 1, high)

Voorbeeld van snel sorteren:

2. Hoare-partitieschema:

Het gebruikt twee indices die beginnen aan de uiteinden van de array die wordt gepartitioneerd en vervolgens naar elkaar toe bewegen totdat ze een inversie detecteren: een paar elementen, een groter of gelijk aan de spil, een kleiner of gelijk, die verkeerd zijn volgorde ten opzichte van elkaar. De omgekeerde elementen worden vervolgens verwisseld. Wanneer de indices elkaar ontmoeten, stopt het algoritme en wordt de uiteindelijke index geretourneerd. Het schema van Hoare is efficiënter dan het partitieschema van Lomuto omdat het gemiddeld drie keer minder ruilt en het maakt efficiënte partities, zelfs als alle waarden gelijk zijn.

quicksort(A, lo, hi) is
if lo < hi then
    p := partition(A, lo, hi)
    quicksort(A, lo, p)
    quicksort(A, p + 1, hi)

Partitie:

partition(A, lo, hi) is
pivot := A[lo]
i := lo - 1
j := hi + 1
loop forever
    do:
        i := i + 1
    while A[i] < pivot do
    
    do:
        j := j - 1
    while A[j] > pivot do
    
    if i >= j then
        return j
    
    swap A[i] with A[j]

C # Implementatie

public class QuickSort
{
    private static int Partition(int[] input, int low, int high)
    {
        var pivot = input[high];
        var i = low - 1;
        for (var j = low; j <= high - 1; j++)
        {
            if (input[j] <= pivot)
            {
                i++;
                var temp = input[i];
                input[i] = input[j];
                input[j] = temp;
            }
        }
        var tmp = input[i + 1];
        input[i + 1] = input[high];
        input[high] = tmp;
        return (i + 1);
    }

    private static void SortQuick(int[] input, int low, int high)
    {
        while (true)
        {
            if (low < high)
            {
                var pi = Partition(input, low, high);
                SortQuick(input, low, pi - 1);
                low = pi + 1;
                continue;
            }
            break;
        }
    }

    public static int[] Main(int[] input)
    {
        SortQuick(input, 0, input.Length - 1);
        return input;
    }
}

Haskell-implementatie

quickSort :: Ord a => [a] -> [a]
quickSort [] = []
quickSort (x:xs) = quickSort [ y | y <- xs, y <= x ] 
                   ++ [x] 
                   ++ quickSort [ z | z <- xs, z > x ]

Lomuto partitie Java-implementatie

public class Solution {

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] ar = new int[n];
    for(int i=0; i<n; i++)
      ar[i] = sc.nextInt();
     quickSort(ar, 0, ar.length-1);   
}

public static void quickSort(int[] ar, int low, int high)
 {
    if(low<high)
    {
        int p = partition(ar, low, high);
        quickSort(ar, 0 , p-1);
        quickSort(ar, p+1, high);
    }    
 }   
public static int partition(int[] ar, int l, int r)
 {
    int pivot = ar[r];
    int i =l;
    for(int j=l; j<r; j++)
     {
        if(ar[j] <= pivot)
         {
            int t = ar[j];
            ar[j] = ar[i];
            ar[i] = t;
            i++;
        }   
    } 
    int t = ar[i];
    ar[i] = ar[r];
    ar[r] = t;
 
    return i;
} 

Quicksort in Python

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) / 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quicksort(left) + middle + quicksort(right)

print quicksort([3,6,8,10,1,2,1])

Afdrukken "[1, 1, 2, 3, 6, 8, 10]"