Andreas Gruenbacher <[EMAIL PROTECTED]> said:
[...]
> Yes, because a custom swap routine isn't very useful generally. It's
> over-engineered IMHO.
It shouldn't swap, but juggle elements around like so:
t --------------->+
^ |
| v
x <-- x <-- x <-- x
Sure, this needs a temporary element, but reduces the data copying to
around 1/3 (1 swap == 3 copies, this makes a bit more than 1 copy for each
element moved). This is probably much more important than
microoptimizations in swap.
My tuned heapsort for doubles is:
/*
* heapsort.c: Heap sort
*/
#include "sort.h"
void
sort(double a[], int n)
{
double tmp;
int i, j, k;
/* Make heap */
for(i = n / 2 - 1; i >= 0; i--) {
/* downheap(a, i, n); */
j = i;
tmp = a[j];
for(;;) {
k = 2 * j + 1;
if(k >= n)
break;
if(k + 1 < n && a[k + 1] > a[k])
k++;
if(tmp > a[k])
break;
a[j] = a[k];
j = k;
}
a[j] = tmp;
}
/* Sort */
for(i = n - 1; i >= 1; i--) {
/* downheap(a, 1, i); swap(a[1], a[n]); */
j = 0;
tmp = a[j];
for(;;) {
k = 2 * j + 1;
if(k > i)
break;
if(k + 1 <= i && a[k + 1] > a[k])
k++;
if(tmp > a[k])
break;
a[j] = a[k];
j = k;
}
a[j] = tmp;
tmp = a[0]; a[0] = a[i]; a[i] = tmp;
}
}
Hack on it as you wish.
--
Dr. Horst H. von Brand User #22616 counter.li.org
Departamento de Informatica Fono: +56 32 654431
Universidad Tecnica Federico Santa Maria +56 32 654239
Casilla 110-V, Valparaiso, Chile Fax: +56 32 797513
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [EMAIL PROTECTED]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
