Partition sort: differenze tra le versioni

Versione delle 01:09, 22 mar 2006

Versione attuale delle 01:14, 6 apr 2006

(7 versioni intermedie di 5 utenti non mostrate)

Riga 1:

#REDIRECT [[Quicksort]]

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>

#include <stdio.h>

main()

{

int i,j,n,k,x;

int a[10];

printf("Di quanti numeri e' formato l'array? (max 10)\n");

scanf("%d",&n);

printf("Scrivi i numeri che compongono l'array:\n");

for(i=0;i<n;i++)

{scanf("%d",&a[i]);}

printf("Qual'e' il numero secondo il quale vuoi partizionare?\n");

scanf("%d",&x);

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;}

}

printf ("L'array partizionato e':\n");

for(i=0;i<n;i++)

{printf ("%d\n",a[i]);}

return 0;

}

</pre>