algorithm
Quicksort

замечания

Основы Quicksort

Quicksort - это алгоритм сортировки, который выбирает элемент («стержень») и переупорядочивает массив, образующий два раздела, так что перед ним появляются все элементы, меньшие, чем точка поворота, и все последующие элементы. Затем алгоритм применяется рекурсивно к разделам, пока список не будет отсортирован.

1. Механизм схемы разделения Ломуто:

Эта схема выбирает стержень, который обычно является последним элементом в массиве. Алгоритм поддерживает индекс, чтобы поместить ось вращения в переменную i, и каждый раз, когда он находит элемент, который меньше или равен оси вращения, этот индекс увеличивается и этот элемент будет помещен перед точкой поворота.

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

Механизм быстрой сортировки:

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

Пример быстрого сортировки:

2. Схема разбиения Хоара:

Он использует два индекса, которые начинаются на концах массива, которые разбиваются на разделы, а затем перемещаются друг к другу, пока они не обнаружат инверсию: пара элементов, одна большая или равная, чем точка опоры, одна меньшая или равная, которые ошибаются порядка друг относительно друга. Перевернутые элементы затем меняются местами. Когда индексы встречаются, алгоритм останавливается и возвращает окончательный индекс. Схема Хора более эффективна, чем схема разделения Ломуто, поскольку она в среднем делает в три раза меньше свопов и создает эффективные разделы, даже если все значения равны.

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

Раздел:

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 #

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

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

Реализация jomoto для раздела Lomuto

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;
} 

Быстрое сортирование в 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])

Печать "[1, 1, 2, 3, 6, 8, 10]"