Messages in this thread | | | Date | Fri, 19 Apr 2002 14:46:13 +0100 | From | Jamie Lokier <> | Subject | Re: [RFC] 2.5.8 sort kernel tables |
| |
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/
| |