Partition sort: differenze tra le versioni

Versione delle 20:35, 5 apr 2006

Versione attuale delle 01:14, 6 apr 2006

Riga 1:

#REDIRECT [[Quicksort]]

{{da cancellare}}

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