Partition sort: differenze tra le versioni

Versione delle 11:21, 30 mar 2006

Versione delle 11:24, 30 mar 2006

Riga 4:

{{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.Per esempio,consideriamo il seguente array:

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

L'algoritmo esegue le seguenti operazioni:

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.

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

*L'algoritmo ovviamente termina quando l'array è stato partizionato oppure quando esso lo era già in partenza.

La complessità di questo algoritmo è:<br>

Line 21 ⟶ 22:

=== [[C]] ===

<pre>

void PartitioSort(int *a,int n, int x) {

int i,j; //indici= 0;

int k,x;j //variabili= di supporton-1;

int k; //indici e variabile di supporto

i=0;

j=n-1;

while (a[i]<=x && i<j)

i=i+1;