|
#REDIRECT [[Quicksort]]
{{da cancellare semplificata}}
{{da aiutare mese|motivo=forma carente, poco chiaro|marzo 2006}}
{{wik|marzo 2006}}
{{stub informatica}}
Il partizionamento consiste nel ordinadare un array di numeri secondo un dato elemento.Per esempio,consideriamo il seguente array:
53 6 2 21 1 93 47
Ipotizziamo di volerlo partizionare in base al numero 20(il numero può essere presente o no nell'array considerato,nn cambia nulla). A sinistra verranno messi i numeri minori od uguali a 20 e nella parte di destra quelli maggiori.
L'algoritmo fa queste operazioni: Due indici i e j,il primo che parte dall'inizio dell'array,l'altro dalla fine che si fermano solo quando individuano elementi che nn vanno bene in quella posizione.Ciò,vale a dire,che nell'esempio considerato,i si fermera sul 53 mentre j sul 1.Individuati i numeri,scambia i due numeri. Il programma,ovviamente,termina quando l'array è stato partizionato oppure quando esso lo era già in partenza.
La complessità di questo algoritmo è:<br>
-Caso migliore: n confronti<br>
-Caso peggiore: n confronti + n/2 scambi
Di seguito riporto l'algoritmo scritto in C:
=== [[C]] ===
<pre>
void PartitioSort(int *a,int n) {
int i,j; //indici
int k,x; //variabili di supporto
i=0;
j=n-1;
while (a[i]<=x && i<j)
i=i+1;
while (a[j]>x && i<j)
j=j-1;
while (i<j) {
k=a[j];
a[j]=a[i];
a[i]=k;
i=i+1;
j=j-1;
while (a[i]<=x && i<j)
i=i+1;
while (a[j]>x && i<j)
{j=j-1;}
}
return;
}
</pre>
[[Categoria:Algoritmi di ordinamento]]
[[en:Partition sort]]
| 