Partition sort

Template:Da cancellare semplificata Template:Da aiutare mese Template:Wik Template: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 è:

• Caso migliore: n confronti
  
• Caso peggiore: n confronti + n/2 scambi

Di seguito riporto l'algoritmo scritto in C:

C

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