Standard Forth versus Python: a case study
Paul Rubin
http
Fri Oct 13 02:54:25 CEST 2006
Gabriel Genellina <gagsl-py at yahoo.com.ar> writes:
> That explains all. Finding the median in an efficient way (that is,
> without sorting the data first) isn't trivial, so your claim of "I can
> do that using only one temp variable" was a bit surprising...
> BTW, the median is the value which sits just in the middle of the list
> when ordered: median(3,5,12,1,2)=median(1,2,3,5,12) = 3
How is this? Note that m and n are treated as constants, so
expressions like n-1, n/2 etc. are also constants. Also assume
m[i+1] is evaluated as (m+1)[i] and of course m+1 is constant.
================================================================
#include <stdio.h>
int
median (int m[], int n)
{
int i;
while (1) {
for (i = 0; i < n-1; i++) {
if (m[i] > m[i+1]) {
/* swap m[i] and m[i+1] with no temp var */
m[i] ^= m[i+1];
m[i+1] ^= m[i];
m[i] ^= m[i+1];
goto yes;
}
}
break;
yes:
for (i = 0; i < n-1; i++) {
if (m[i] > m[i+1]) {
m[i] ^= m[i+1];
m[i+1] ^= m[i];
m[i] ^= m[i+1];
}
}
}
return m[n / 2];
}
int a[] = {9,6,1,5,4,2,8,3,7};
main()
{
int m;
m = median(a, 9);
printf ("%d\n", m);
}
More information about the Python-list
mailing list