Partition sort

Template:Da cancellare semplificata Template:Da aiutare mese Template:Wik Template: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 è:
-Caso migliore: n confronti
-Caso peggiore: n confronti + n/2 scambi

Di seguito riporto l'algoritmo scritto in C:

C

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