Hi,

I have the feeling the messages on this forum are not read much, but anyway, someone might be interested.

I tested the 4 sort test algorithms aroung page 126 (selection sort, insertion sort, merge sort, quick sort) and I believe a big limition lies in quick sort implementation on page 128 - 129 : it doesn't work if original array contains duplicate values.

The fix I found is to count how many times the "pivot value" is found in array and then not only copy this pivot value between left and right values, but copy it

*as many times as needed*.

Here's my version of the quick sort implementation, tested with arrays with duplicate values:

Code:

protected void quickSortRec(int[] toSort) {
if (toSort.length > 1) {
int pivotIndex = toSort.length / 2;
int pivotValue = toSort[pivotIndex];
int lessSize = 0;
int nbPivot = 0;
// Calculate size of "less" array
// Decide arbitrarily to keep pivot value in "less"
for (int value : toSort) {
if (value < pivotValue) {
lessSize++;
} else if (value == pivotValue) {
nbPivot ++;
}
}
int[] less = new int[lessSize];
int[] more = new int[toSort.length - lessSize - nbPivot];
lessSize = 0;
int moreSize = 0;
for (int value : toSort) {
if (value < pivotValue) {
less[lessSize++] = value;
} else if (value > pivotValue) {
more[moreSize++] = value;
}
}
quickSortRec(less);
quickSortRec(more);
System.arraycopy(less, 0, toSort, 0, lessSize);
for (int i = 0; i < nbPivot; i ++) {
toSort[lessSize + i] = pivotValue;
}
System.arraycopy(more, 0, toSort, lessSize + nbPivot, moreSize);
}
}

I believe it is mandatory for a sort algorithm, even simple, to handle such case...

Hope this helps, comments welcome!

Cheers

Olivier