Wikibooks

Implementazioni di algoritmi/Quicksort: differenze tra le versioni

Naviga nella cronologia in modo interattivo
← Differenza precedenteDifferenza successiva →
Contenuto cancellato Contenuto aggiunto
VisualeWikitesto
mNessun oggetto della modifica
copio da it.wiki perché l'import non va, vedere in discussione per il link alla crono
Riga 2:
'''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 di programmazione|linguaggi]].
===Implementazione in [[C++]]===
<source lang="cpp">
#include <functional>
#include <algorithm>
#include <iterator>
 
Seguono alcuni esempi di implementazione in vari [[linguaggi di programmazione|linguaggi]].
template< typename BidirectionalIterator, typename Compare >
void quick_sort( BidirectionalIterator first, BidirectionalIterator last, Compare cmp ) {
if( first != last ) {
BidirectionalIterator left = first;
BidirectionalIterator right = last;
BidirectionalIterator pivot = left++;
 
===[[linguaggio C|C]]===
while( left != right ) {
{{Matematica voce|Quicksort|C|
if( cmp( *left, *pivot ) ) {
<source lang="C">
++left;
void sort(int array[], int begin, int end) {
} else {
int while( (left != right) && cmp( *pivot, *rightl, )r; )
if (end > begin) --right;{
pivot = std::iter_swap( left, right )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);
}
}
</source>
}}
//attenzione, il programma non è completo!
 
===[[C++]]===
--left;
{{Matematica voce|Quicksort|C++|
std::iter_swap( first, left );
<source lang="Cpp">
#include <algorithm>
#include <iterator>
#include <functional>
 
template <typename T>
quick_sort( first, left, cmp );
void sort(T begin, T end) {
quick_sort( right, last, cmp );
if (begin != end) {
}
T middle = partition (begin, end, bind2nd(
}
less<iterator_traits<T>::value_type>(), *begin));
 
sort (begin, middle);
template< typename BidirectionalIterator >
sort (max(begin + 1, middle), end);
inline void quick_sort( BidirectionalIterator first, BidirectionalIterator last ) {
}
quick_sort( first, last,
std::less_equal< typename std::iterator_traits< BidirectionalIterator >::value_type >()
);
}
</source>
}}
 
===Implementazione in [[JavaHaskell]] ===
 
{{Matematica voce|Quicksort|Haskell|
<code><pre><nowiki>
sort :: (Ord a) => [a] -> [a]
sort [] = []
sort (pivot:rest) = sort [y | y <- rest, y < pivot]
++ [pivot] ++
sort [y | y <- rest, y >=pivot]
</nowiki></pre></code>
}}
 
 
=== [[Linguaggio di programmazione Java|Java]] ===
 
Questo esempio mostra un quicksort generico, piuttosto che uno che funzioni con gli interi o con le stringhe.
{{Matematica voce|Quicksort|Java|
<source lang="java">
import java.util.ArrayListComparator;
import java.util.Random;
 
public class QuickSortQuicksort {
public static final Random RND = new Random();
private void swap(Object[] array, int i, int j) {
public static final int NUMBERS_TO_SORT = 25;
Object tmp = array[i];
array[i] = array[j];
public QuickSort() {
array[j] = tmp;
}
private int partition(Object[] array, int begin, int end, Comparator cmp) {
int index = begin + RND.nextInt(end - begin + 1);
public static void main(String[] args) {
Object pivot = array[index];
ArrayList<Integer> numbers = new ArrayList<Integer>();
swap(array, index, end);
Random rand = new Random();
for (int i = 0index = begin; i < NUMBERS_TO_SORTend; i++ i) {
if (cmp.compare(array[i], pivot) <= 0) {
numbers.add(rand.nextInt(NUMBERS_TO_SORT + 1));
swap(array, index++, i);
for (int number : numbers)
}
System.out.print(number + " ");
}
System.out.println("\nBefore quick sort\n\n");
swap(array, index, end);
for (int number : quicksort(numbers))
return (index);
System.out.print(number + " ");
System.out.println("\nAfter quick sort\n\n");
}
private void qsort(Object[] array, int begin, int end, Comparator cmp) {
if (end > begin) {
public static ArrayList<Integer> quicksort(ArrayList<Integer> numbers) {
int index = partition(array, begin, end, cmp);
if (numbers.size() <= 1)
qsort(array, begin, index - 1, cmp);
return numbers;
qsort(array, index + 1, int pivotend, = numbers.size(cmp) / 2;
ArrayList<Integer> lesser = new ArrayList<Integer>();
ArrayList<Integer> greater = new ArrayList<Integer>();
int sameAsPivot = 0;
for (int number : numbers) {
if (number > numbers.get(pivot))
greater.add(number);
else if (number < numbers.get(pivot))
lesser.add(number);
else
sameAsPivot++;
}
}
lesser = quicksort(lesser);
public void sort(Object[] array, Comparator cmp) {
for (int i = 0; i < sameAsPivot; i++)
qsort(array, 0, array.length - 1, cmp);
lesser.add(numbers.get(pivot));
greater = quicksort(greater);
ArrayList<Integer> sorted = new ArrayList<Integer>();
for (int number : lesser)
sorted.add(number);
for (int number: greater)
sorted.add(number);
return sorted;
}
}
// ATTENZIONE NON FUNZIONA! ATTENZIONE NON FUNZIONA! ATTENZIONE NON FUNZIONA!
// ATTENZIONE NON FUNZIONA! ATTENZIONE NON FUNZIONA! ATTENZIONE NON FUNZIONA!
</source>
 
Ecco un'algoritmo funzionante solo con numeri interi :
<source lang="java">
// 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;
}
</source>
}}
 
===Implementazione in [[LispJoy_(programmazione)|Joy]] ===
 
<source lang="lisp">
{{Matematica voce|Quicksort|Joy|
(defun partition (fun array)
<code><pre><nowiki>
(list (remove-if-not fun array) (remove-if fun array)))
DEFINE sort == [small][]
[uncons [>] split]
[[swap] dip cons concat] binrec .
</nowiki></pre></code>peido
}}
 
===[[Lisp]]===
 
{{Matematica voce|Quicksort|Lisp|
<source lang="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))
)
)
)
</source>
}}
 
===[[Pascal]]===
 
{{Matematica voce|Quicksort|Pascal|
<source lang="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
(defun sort (array)
pQuickSort(A, Low(A), High(A)); {First Call of the whole}
(if (null array) nil
{Implemented by Markus Gronotte in Pascal}
(let ((part (partition (lambda (x) (< x (car array))) (cdr array))))
end;
(append (sort (car part)) (cons (car array) (sort (cadr part)))))))
 
</source>
}}
 
=== [[Perl|Perl]] ===
{{Matematica voce|Quicksort|Perl|
<source lang="perl">
sub qsort {
@_ or return ();
my $p = shift;
(qsort(grep $_ < $p, @_), $p, qsort(grep $_ >= $p, @_));
}
</source>
}}
 
=== [[Perl|Perl 6]] ===
 
{{Matematica voce|Quicksort|Perl 6|
<source lang="perl">
multi quicksort () { () }
multi quicksort (*$x, *@xs) {
my @pre = @xs.grep:{ $_ < $x };
my @post = @xs.grep:{ $_ >= $x };
(@pre.quicksort, $x, @post.quicksort);
}
</source>
}}
 
=== [[Python]] ===
 
{{Matematica voce|Quicksort|Python|
Ordinamento in place:
<source lang="python">
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)
 
</source>
 
Algoritmo funzionale:
<source lang="python">
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]))
</source>
 
}}
 
=== [[Prolog]] ===
{{Matematica voce|Quicksort|Prolog|
<code><pre><nowiki>
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).
</nowiki></pre></code>
}}
 
===[[Ruby]]===
{{Matematica voce|Quicksort|Ruby|
<source lang="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
</source>
}}
 
=== [[Standard ML|SML]] ===
 
{{Matematica voce|Quicksort|SML|
<code><pre><nowiki>
'''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'''
</nowiki></pre></code>
}}
 
 
[[Categoria:Implementazioni di algoritmi|Quicksort]]
Estratto da "https://it.wikibooks.org/wiki/Implementazioni_di_algoritmi/Quicksort"