Problema procedura partition

[Darèios89]

Nell'algoritmo Quicksort ci si serve della procedura partition, l'ho anche cercata su google, ma non mi è chiaro a cosa serva e soprattuto come funzioni, non è che potreste con un breve codice commentato farmi capire?

[bstefano79]

il partition è il cuore del quicksort, il concetto è quello di mettere i numeri più grandi del pivot a destra e quilli più piccoli a sinistra del pivot stesso in un sottoinsieme di un vettore

private int partition(T[] array, int lo, int hi, int pivotIndex)
{
   T pivotValue = array[ pivotIndex ];
 
   swap(array, pivotIndex, hi); //send pivot item to the back
 
   int index = lo; //keep track of where the front ends
 
   for (int i = lo; i < hi; i++) //check from the front to the back
   {
      //swap if the current value is less than the pivot
      if ( (array[i]).compareTo(pivotValue) <= 0 ) 
      {
         swap(array, i, index);
         index++;
      }
   }
 
   swap(array, hi, index); //put pivot item in the middle
 
   return index;
}

piccolo esempio supponiamo di avere hi=10 low=5 pivotIndex=6

la parte dell'array che andiamo a considerare è quindi quella che va dall'indice 5 all'indice 10. Il pivot deve ovviamente ricadere all'interno dell'intervallo e deve essere scelto casualmente se possibile

quindi supponiamo che il vettore sia così fatto

Vett    34 67 102 11 112 66

indici   5    6   7    8   9   10

il pivot è il numero con indice 6 quindi il numero 67 che andremo a scambiare con l'ultimo elemento del vettore

Vett    34 66 102 11 112 67

indici   5    6   7    8   9   10

ora partendo dall'indice minore hi=i=index=5 andiamo a confroontare i numeri con il pivot

34 è minore di 67 quindi scabiamo il numero con indice i con quello con indice index in questo caso è lo stesso (i=index=5) quindi rimane tutto come è incrementiamo i e index che vanno a 6

66 è minore di 67 ripetiamo la stessa cosa anche in questo caso i=index quindi lo scambio lascia le cose invariate incrementiamo sia index che i che vanno a 7

102 è maggiore di 67 quindi non effettuiamo nessuno scambio e incrementiamo solo i che va a 8

11 è minore si 67 quindi invertiamo i valori di indice 7 e 8

Vett    34 66 11  102 112 67

indici   5    6   7    8   9   10

ed incrementiamo sia i che index i=9 e index=8

112>67 quindi non effettuiamo nessuno scambio

siamo arrivati alla fine del sottoinsieme non ci resta che scambiare il pivot con l'elemento di indice index=8

Vett    34 66 11  67 112 102

indici   5    6   7    8   9   10

si può notare che gli elementi minori di 67 sono a sinistra e quelli maggiori a destra anche se il vettore non è ordinato

in pratica il pivot è al posto giusto nell'ordinamento, ora basta ripetere l'operazione per i 2 sottoinsiemi (34,66,11) e (112,102) ovvero eseguire
partition(Vet,5,7,indexPivot) con indexPivot preso a caso fra 5,6 e 7
partition(Vet,9,10,indexPivot) con indexPivot preso a caso fra 9 e 10