Implementazioni di algoritmi/Quicksort

Wikibooks, manuali e libri di testo liberi.

Sommario
Categoria · Copertina · Sviluppo · modifica il template

Copertina Implementazioni 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.


Indice

[modifica] C

 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!

[modifica] C++

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

[modifica] Haskell

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

[modifica] Java

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

[modifica] Joy

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

[modifica] Lisp

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

[modifica] Pascal

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;

[modifica] Perl

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

[modifica] Perl 6

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

[modifica] Python

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

[modifica] Prolog

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

[modifica] Ruby

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

[modifica] SML

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

[modifica] Lua

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

[modifica] Altri progetti

Ricavato da "http://it.wikibooks.org/wiki/Implementazioni_di_algoritmi/Quicksort"
Strumenti personali
Altre lingue