I precedenti algoritmi comunque funzionano solo se non ci sono ripetizioni all'interno dell'array, una versione che funziona anche in questo caso è:
Codice PHP:
void part(int array[], int x){
int last = array.length - 1;
int first = 0;
int swap = 1;
for(; ((first < last) && (swap <= last)); ){
//primo elemento maggiore del pivot
if(array[first] > x){
int temp = array[first];
array[first] = array[last];
array[last] = temp;
last--;
}
//primo elemento minore del pivot
else if(array[first] < x){
first++;
swap++;
}//primo elemento uguale al pivot
//cerco tra gli elementi rimasti uno minore del pivot
else{
if(array[swap] < array[first]){
int temp = array[first];
array[first] = array[swap];
array[swap] = temp;
first++;
swap = first + 1;
}
else
swap++;
}
}
}