algorithm
quicksort
Ricerca…
Osservazioni
A volte Quicksort è anche conosciuto come ordinamento di partizione-scambio.
Spazio ausiliario: O(n)
Complessità temporale: peggiore O(n²)
, migliore O(nlogn)
Nozioni di base su Quicksort
Quicksort è un algoritmo di ordinamento che seleziona un elemento ("il pivot") e riordina l'array formando due partizioni in modo tale che tutti gli elementi inferiori al pivot vengano prima di esso e tutti gli elementi maggiori vengano dopo. L'algoritmo viene quindi applicato in modo ricorsivo alle partizioni finché l'elenco non viene ordinato.
1. Meccanismo di schema di partizione di Lomuto:
Questo schema sceglie un pivot che è in genere l'ultimo elemento dell'array. L'algoritmo mantiene l'indice per inserire il pivot nella variabile i e ogni volta che trova un elemento minore o uguale a pivot, questo indice viene incrementato e quell'elemento verrà posizionato prima del pivot.
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
Meccanismo di ordinamento rapido:
quicksort(A, low, high) is
if low < high then
p := partition(A, low, high)
quicksort(A, low, p – 1)
quicksort(A, p + 1, high)
Esempio di ordinamento rapido:
2. Schema di partizione Hoare:
Usa due indici che iniziano alle estremità dell'array partizionato, quindi si spostano l'uno verso l'altro, finché non rilevano un'inversione: una coppia di elementi, uno maggiore o uguale al pivot, uno minore o uguale, che sono nel torto ordine l'uno rispetto all'altro. Gli elementi invertiti vengono quindi scambiati. Quando gli indici si incontrano, l'algoritmo si arresta e restituisce l'indice finale. Lo schema di Hoare è più efficiente dello schema di partizione di Lomuto perché riduce in media tre volte meno swap e crea partizioni efficienti anche quando tutti i valori sono uguali.
quicksort(A, lo, hi) is
if lo < hi then
p := partition(A, lo, hi)
quicksort(A, lo, p)
quicksort(A, p + 1, hi)
Partizione:
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]
Implementazione 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;
}
}
Implementazione Haskell
quickSort :: Ord a => [a] -> [a]
quickSort [] = []
quickSort (x:xs) = quickSort [ y | y <- xs, y <= x ]
++ [x]
++ quickSort [ z | z <- xs, z > x ]
Implementazione java di partizione 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;
}
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])