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