Mediana del 3 partizionamento

Ho trovato il seguente codice per trovare un pivot per quicksort usando la mediana del primo, ultimo e medio elemento:

int middle = ( low + high ) / 2; if( a[ middle ].compareTo( a[ low ] ) < 0 ) swapReferences( a, low, middle ); if( a[ high ].compareTo( a[ low ] ) < 0 ) swapReferences( a, low, high ); if( a[ high ].compareTo( a[ middle ] ) < 0 ) swapReferences( a, middle, high ); // Place pivot at position high - 1 swapReferences( a, middle, high - 1 ); Comparable pivot = a[ high - 1 ]; 

Voglio sapere dopo aver trovato la mediana, perché lo scambio è fatto con indice alto 1 invece di alto?

La ragione è che l’algoritmo non trova solo la mediana, ma ordina anche gli elementi basso, medio e alto. Dopo le tre permutazioni sai che a [middle] <= a [high]. Quindi è necessario solo partizionare gli elementi prima dell'altezza, perché un [alto] è maggiore o uguale a pivot.

Diamo un’occhiata a un esempio: basso = 0, medio = 4 e alto = 8. Il tuo array è così:

 lowerOrEqualToPivot XXX pivot XXX greaterOrEqualToPivot 

Se scambiate la parte centrale con l’altezza, dovete dividere gli 8 elementi tra parentesi:

 [ lowerOrEqualToPivot XXX greaterOrEqualToPivot XXX ] pivot 

Se scambi metà con high-1, devi dividere solo 7 elementi:

 [ lowerOrEqualToPivot XXXXXX ] pivot greaterOrEqualToPivot 

Tra l’altro c’è un bug nella prima riga:

 int middle = ( low + high ) / 2; //Wrong int middle = ( low + high ) >>> 1; //Correct 

Il motivo è che se (basso + alto) è maggiore di Integer.MAX_VALUE avrai un overflow e il centro sarà un numero negativo. La seconda linea ti darà sempre un risultato positivo.