|
#REDIRECT [[Quicksort]]
{{da cancellare semplificata}}
{{da aiutare mese|motivo=forma carente, poco chiaro|marzo 2006}}
{{wik|marzo 2006}}
{{stub informatica}}
Il ''Partition Sort'' è un metodo di ordinamento degli elementi di un vettore.
Il partizionamento consiste nel ordinadare un array di numeri secondo un dato elemento.
L'algoritmo esegue le seguenti 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 non in posizione corretta.
*Individuati i numeri, essi vengono scambiati.
*L'algoritmo 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 x) {
int i = 0;
int j = n-1;
int k; //indici e variabile di supporto
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]]
| 