We’re rewarding the question askers & reputations are being recalculated! Read more.
5 of 13 Hopefully correct

Sorting for search by monotomy

Statement

Given N distinct integers, output them in order such that, for any integer from 2 to N, for any K>0 obtained by dividing J by 2 (rounding down) at least one time, the Jth integer output is larger than the Kth if and only if the division by 2 that gave K started from an odd integer.

Note: this is for one-based index, as in common language, because that makes the statement less hairy. The motivating code below uses zero-based indexes.

This is a code golf. Output shall be in decimal, with some separator. 2 to 99 non-negative distinct integers must be handled, regardless of initial order.

Example

Given the first 10 primes (in any order), the output must be in this order

17 7 23 3 13 19 29 2 5 11

which, when rewritten as a binary tree, gives:

17 /-------------\ 7 23 /------\ /------\ 3 13 19 29 /-\ / 2 5 11

This is correct since

  • for J=2,
    • for K=1 obtained by dividing the (even) J=2 by 2, the second output 7 is smaller than the first output 17
  • and for J=3,
    • for K=1 obtained by dividing the (odd) J=3 by 2, the third output 23 is larger than the first output 17
  • and for J=4,
    • for K=2 obtained by dividing the (even) J=4 by 2, the 4th output 3 is smaller than the second output 7
  • and for J=5,
    • for K=2 obtained by dividing the (odd) J=5 by 2, the 5th output 13 is larger than the second output 7
    • and for K=1 obtained by further dividing the (even) previous K=2 by 2, said 5th output 13 is smaller than the first output 17
  • and for J=6,
    • for K=3 obtained by dividing the (even) J=6 by 2, the 6th output 19 is smaller than the third output 23
    • and for K=1 obtained by further dividing the (odd) previous K=3 by 2, said 6th output 19 is larger than the first output 17
  • and for J=7,
    • for K=3 obtained by dividing the (odd) J=7 by 2, the 7th output 29 is larger than the 4th output 3
    • and for K=1 obtained by further dividing the (odd) previous K=3 by 2, said 7th output 29 is larger than the first output 17
  • and for J=8,
    • for K=4 obtained by dividing the (even) J=8 by 2, the 8th output 2 is smaller than the 4th output 3
    • and for K=2 obtained by further dividing the (even) previous K=4 by 2, said 8th output 2 is smaller than the second output 7
    • and for K=1 obtained by further dividing the (odd) previous K=3 by 2, said 8th output 2 is smaller than the first output 17
  • and for J=9,
    • for K=4 obtained by dividing the (odd) J=9 by 2, the 9th output 5 is larger than the 4th output 3
    • and for K=2 obtained by further dividing the (even) previous K=4 by 2, said 9th output 5 is smaller than the second output 7
    • and for K=1 obtained by further dividing the (odd) previous K=3 by 2, said 9th output 5 is smaller than the first output 17
  • and for J=10,
    • for K=5 obtained by dividing the (even) J=10 by 2, the 10th output 11 is smaller than the 5th output 13
    • and for K=2 obtained by further dividing the (odd) previous K=5 by 2, said 10th output 11 is larger than the second output 7
    • and for K=1 obtained by further dividing the (odd) previous K=3 by 2, said 10th output 11 is smaller than the first output 17

Motivation

This allows search in a static list by monotomy, simpler and typically faster than dichotomy. // Search t in table *p of length n (with n<=MAX_INT/2 and n>=0) // Returns the index (zero-based), or -1 for not found // Assumes table *p is in monotomic order (see below) int monotomy(const int *p, int n, int t) { int j; for( j = 0; j

// Return 1 iff table *p is in correct order for monotomy
// Table *p of length n is zero-based.
int monotomic(const int *p, int n) {
  int j,k,m;
  for( j = 2; j<n; ++j)
    for ( m = k = j; (k /= 2)>0; m = k)
      if ( (p[j-1]>p[k-1]) != (m%2) )
        return 0; // incorrect order
  return 1;       //   correct order
  }

// monotomy demo
#include <stdio.h>
int main(void) {
  const int p[] = { 17, 7, 23, 3, 13, 19, 29, 2, 5, 11 };
  #define n (sizeof(p)/sizeof(*p))
  int t, i, j;
  printf("monotomic = %d\n", monotomic(p, n) );
  for( t = i = 0; t<9999; ++t )
    if( ( j = monotomy(p, n, t) )>=0 )
       printf( "%d\n", p[++i, j] );
  if ( i!=n )
      printf("Incorrect\n");
  return 0;
}