Originally Posted by
Sang-drax
But your assumption is that it must be possible for all elements to be distinct. Sometimes that is not the case. You are right, but my problem is still a sorting problem.
You can't really discard that assumption and talk about sorting algorithms' theoretical performance. Quicksort, if coded accordingly, is a O(N) sort in all cases if you limit the integers to a finite domain.
Code:
// All integers fall between 0 and 10
qsort (unsigned int * sort_begin, unsigned int * sort_end) {
unsigned int pivot = *sort_begin;
unsigned int * piv_begin = sort_begin;
unsigned int * piv_end = piv_begin + 1;
unsigned int * compare = piv_end;
// partition
for ( ; compare != sort_end; ++compare ) {
if (*compare <= pivot) {
swap (piv_end, compare);
if (*piv_end == pivot)
++piv_end
else
swap (piv_begin++, piv_end++);
}
}
// Since the pivot value got clumped, we are guaranteed to use each pivot only once.
// Therefore, we are guaranteed to recurse <= 10 times total.
if (sort_begin != piv_begin) // Values less than pivot
qsort (sort_begin, piv_begin);
if (piv_end != sort_end) // Values greater than pivot
qsort (piv_end, sort_end);
}