Oliver Xymoron wrote:
> Though we should probably just stick a simple qsort in the library
> somewhere.
Since we're comparing sort algorithms, I am quite fond of Heapsort.
Simple, no recursion or stack, and worst case O(n log n). It's not
especially fast, but the worst case behaviour is nice:
/* This function is a classic in-place heapsort. It sorts the array
`nums' of integers, which has `count' elements. */
void my_heapsort (int count, int * nums)
{
int i;
for (i = 1; i < count; i++) {
int j = i, tmp = nums [j];
while (j > 0 && tmp > nums [(j-1)/2]) {
nums [j] = nums [(j-1)/2];
j = (j-1)/2;
}
nums [j] = tmp;
}
for (i = count - 1; i > 0; i--) {
int j = 0, k = 1, tmp = nums [i];
nums [i] = nums [0];
while (k < i && (tmp < nums [k]
|| (k+1 < i && tmp < nums [k+1]))) {
k += (k+1 < i && nums [k+1] > nums [k]);
nums [j] = nums [k];
j = k;
k = 2*j+1;
}
nums [j] = tmp;
}
}
cheers,
-- Jamie
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
This archive was generated by hypermail 2b29 : Tue Apr 23 2002 - 22:00:24 EST