algorithm
Schnelle Sorte

Bemerkungen

Quicksort-Grundlagen

Quicksort ist ein Sortieralgorithmus, der ein Element ("den Drehpunkt") auswählt und das Array so anordnet, dass es zwei Partitionen bildet, so dass alle Elemente, die weniger als der Drehpunkt sind, davor stehen und alle größeren Elemente danach folgen. Der Algorithmus wird dann rekursiv auf die Partitionen angewendet, bis die Liste sortiert ist.

1. Mechanismus des Lomuto-Partitionsschemas:

Dieses Schema wählt einen Drehpunkt aus, der normalerweise das letzte Element in der Anordnung ist. Der Algorithmus behält den Index bei, um den Drehpunkt in die Variable i zu setzen, und jedes Mal, wenn ein Element gefunden wird, das kleiner oder gleich dem Drehpunkt ist, wird dieser Index inkrementiert und dieses Element wird vor dem Drehpunkt platziert.

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

Schneller Sortiermechanismus:

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

Beispiel für eine schnelle Sortierung:

2. Hoare-Partitionsschema:

Es verwendet zwei Indizes, die an den Enden des zu partitionierenden Arrays beginnen und sich dann aufeinander zu bewegen, bis sie eine Umkehrung erkennen: ein Paar von Elementen, eines größer oder gleich dem Drehpunkt, eines weniger oder gleich, die falsch liegen Reihenfolge relativ zueinander. Die invertierten Elemente werden dann ausgetauscht. Wenn sich die Indizes treffen, stoppt der Algorithmus und gibt den endgültigen Index zurück. Das Schema von Hoare ist effizienter als das Partitionsschema von Lomuto, da es im Durchschnitt dreimal weniger Swaps durchführt und effiziente Partitionen erstellt, selbst wenn alle Werte gleich sind.

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

Partition:

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 # -Implementierung

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-Implementierung

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

Lomuto Partition Java Implementierung

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])

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