Implementazioni di algoritmi/Quicksort

Wikibooks, manuali e libri di testo liberi.
CopertinaImplementazioni di algoritmi/Copertina

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.


C[modifica]

 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!

C++[modifica]

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

Haskell[modifica]

  sort :: (Ord a)   =  [a] -  [a]
  
  sort []           = []
  sort (pivot:rest) = sort [y | y  - rest, y   pivot]
                      ++ [pivot] ++ 
                      sort [y | y  - rest, y  =pivot]

Java[modifica]

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[fin]) ) 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;
	}

Joy[modifica]

 DEFINE sort == [small][]
                [uncons [ ] split]
                [[swap] dip cons concat] binrec .

Lisp[modifica]

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

Pascal[modifica]

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;

Perl[modifica]

sub qsort {
  @_ or return ();
  my $p = shift;
  (qsort(grep $_   $p, @_), $p, qsort(grep $_  = $p, @_));
}

Perl 6[modifica]

multi quicksort () { () }
multi quicksort (*$x, *@xs) {
   my @pre  = @xs.grep:{ $_    $x };
   my @post = @xs.grep:{ $_  = $x };
   (@pre.quicksort, $x, @post.quicksort);
}

Python[modifica]

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

Prolog[modifica]

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

Ruby[modifica]

 def qsort(list)
  return [] if list.size == 0
  x, *xs = *list
  less, more = xs.partition{|y| y   x}
  qsort(less) + [x] + qsort(more)
 end

SML[modifica]

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

Lua[modifica]

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]