Implementazioni di algoritmi/Quicksort
Quicksort è un ottimo algoritmo di ordinamento ricorsivo in place che, come merge sort, si basa sul paradigma divide et impera. La base del suo funzionamento è l'utilizzo ricorsivo della procedura partition: preso un elemento da una struttura dati (es. array) si pongono gli elementi minori a sinistra rispetto a questo e gli elementi maggiori a destra.
Seguono alcuni esempi di implementazione in vari linguaggi.
void sort(int array[], int begin, int end) {
int pivot, l, r;
if (end > begin) {
pivot = array[begin];
l = begin + 1;
r = end+1;
while(l < r)
if (array[l] < pivot)
l++;
else {
r--;
swap(array[l], array[r]);
}
l--;
swap(array[begin], array[l]);
sort(array, begin, l);
sort(array, r, end);
}
}
//attenzione, il programma non è completo!
#include <algorithm>
#include <iterator>
#include <functional>
template <typename T>
void sort(T begin, T end) {
if (begin != end) {
T middle = partition (begin, end, bind2nd(
less<iterator_traits<T>::value_type>(), *begin));
sort (begin, middle);
sort (max(begin + 1, middle), end);
}
}
sort :: (Ord a) => [a] -> [a]
sort [] = []
sort (pivot:rest) = sort [y | y <- rest, y < pivot]
++ [pivot] ++
sort [y | y <- rest, y >=pivot]
Questo esempio mostra un quicksort generico, piuttosto che uno che funzioni con gli interi o con le stringhe.
import java.util.Comparator;
import java.util.Random;
public class Quicksort {
public static final Random RND = new Random();
private void swap(Object[] array, int i, int j) {
Object tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
private int partition(Object[] array, int begin, int end, Comparator cmp) {
int index = begin + RND.nextInt(end - begin + 1);
Object pivot = array[index];
swap(array, index, end);
for (int i = index = begin; i < end; ++ i) {
if (cmp.compare(array[i], pivot) <= 0) {
swap(array, index++, i);
}
}
swap(array, index, end);
return (index);
}
private void qsort(Object[] array, int begin, int end, Comparator cmp) {
if (end > begin) {
int index = partition(array, begin, end, cmp);
qsort(array, begin, index - 1, cmp);
qsort(array, index + 1, end, cmp);
}
}
public void sort(Object[] array, Comparator cmp) {
qsort(array, 0, array.length - 1, cmp);
}
}
// ATTENZIONE NON FUNZIONA! ATTENZIONE NON FUNZIONA! ATTENZIONE NON FUNZIONA!
// ATTENZIONE NON FUNZIONA! ATTENZIONE NON FUNZIONA! ATTENZIONE NON FUNZIONA!
Ecco un algoritmo funzionante solo con numeri interi :
// ATTENZIONE : per l'avvio fin deve essere pari a v.length-1
public void QuickSort( int [] v , int in , int fin ){
if( fin<=in )return;
int pos=partiziona( v,in,fin );
/*
* Ricorsione...(Quindi algoritmo non in-place , in quanto deve
* allocare memoria fino alla risoluzione del problema)
*/
QuickSort( v,in,pos-1 ); //Sotto porzione sinistra
QuickSort( v,pos+1,fin ); //Sotto porzione destra
}
public int partiziona( int[]v , int in , int fin ){
// L'elemento pivot è il primo (posizione 0)
int i=in+1,j=fin;
while( i<=j ){
while( (i<=fin) && (v[i]<=v[in]) ) i++;
while( v[j]>v[in] ) j--;
if( i<=j ){
// Scambia
int t=v[i];
v[i]=v[j];
v[j]=t;
}
}
// Scambia
int tt=v[in];
v[in]=v[i-1];
v[i-1]=tt;
return i-1;
}
DEFINE sort == [small][]
[uncons [>] split]
[[swap] dip cons concat] binrec .
(defun qsort (lst cmp / x y l e g)
(if lst
(progn
(setq x (nth (/ (length lst) 2) lst))
(foreach y lst
(cond
((equal y x)
(setq e (cons y e)))
((apply cmp (list y x))
(setq l (cons y l)))
(T (setq g (cons y g)))
)
)
(append (qsort l cmp) e (qsort g cmp))
)
)
)
procedure pQuickSort(var A: array of integer; iLo, iHi: integer);
var Lo, Hi, Pivot, T: Integer;
begin
Lo := iLo; Hi := iHi;
Pivot := A[Hi]; {Pivot is right}
repeat
while A[Lo] < Pivot do Inc(Lo);
while A[Hi] > Pivot do Dec(Hi);
if Lo <= Hi then begin
T := A[Lo]; A[Lo] := A[Hi]; A[Hi] := T;
Inc(Lo); Dec(Hi);
end;
until Lo > Hi;
if Hi > iLo then pQuickSort(A, iLo, Hi); {Sort left Part}
if Lo < iHi then pQuickSort(A, Lo, iHi); {Sort right Part}
end;
begin
pQuickSort(A, Low(A), High(A)); {First Call of the whole}
{Implemented by Markus Gronotte in Pascal}
end;
sub qsort {
@_ or return ();
my $p = shift;
(qsort(grep $_ < $p, @_), $p, qsort(grep $_ >= $p, @_));
}
multi quicksort () { () }
multi quicksort (*$x, *@xs) {
my @pre = @xs.grep:{ $_ < $x };
my @post = @xs.grep:{ $_ >= $x };
(@pre.quicksort, $x, @post.quicksort);
}
Ordinamento in place:
def partition(array, begin, end, cmp):
pivot=array[end]
ii=begin
for jj in xrange(begin, end):
if cmp(array[jj], pivot):
array[ii], array[jj] = array[jj], array[ii]
ii+=1
array[ii], array[end] = pivot, array[ii]
return ii
def sort(array, cmp=lambda x, y: x < y, begin=0, end=None):
if end is None: end = len(array)
if begin < end:
i = partition(array, begin, end-1, cmp)
sort(array, cmp, begin, i)
sort(array, cmp, i+1, end)
Algoritmo funzionale:
def quicksort(lista):
if len(lista)<=1: return lista
pivot=lista[0]
return (quicksort([e for e in lista[1:] if e < pivot]) +
[pivot] +
quicksort([e for e in lista[1:] if e >= pivot]))
append([], L, L).
append([H | L1], L2, [H | Result]) :- append(L1, L2, Result).
partition([], _, [], []).
partition([H | T], X, [H | Left], Right) :- H =< X, partition(T, X, Left, Right).
partition([H | T], X, Left, [H | Right]) :- H > X, partition(T, X, Left, Right).
qsort([],[]).
qsort([H | Tail], Sorted) :-
partition(Tail, H, Left, Right),
qsort(Left, SortedLeft),
qsort(Right, SortedRight),
append(SortedLeft, [H | SortedRight], Sorted).
def qsort(list)
return [] if list.size == 0
x, *xs = *list
less, more = xs.partition{|y| y < x}
qsort(less) + [x] + qsort(more)
end
'''fun''' quicksort lt lst =
'''let''' val rec sort =
fn [] => []
| (x::xs) =>
'''let'''
val (left,right) = List.partition (fn y => lt (y, x)) xs
'''in''' sort left @ x :: sort right
'''end'''
'''in''' sort lst
'''end'''
function quickSort(a,ini,u)
lo= ini
hi= u
pivot= a[hi]
repeat
while a[lo] < pivot do lo=lo+1 end
while a[hi] > pivot do hi=hi-1 end
if lo <= hi then
t= a[lo]
a[lo]= a[hi]
a[hi]= t
lo=lo+1
hi=hi-1
end
until lo > hi;
if hi > ini then quickSort(a, ini, hi) end
if lo < u then quickSort(a, lo, u) end
return a
end
Altri progetti
modifica
Wikipedia contiene una voce su questo algoritmo
Wikimedia Commons contiene immagini o altri file su quicksort
