Sorting for search by monotomy

Question

Statement

Given N distinct integers, output them in order such that

• for any integer J from 2 to N,
  • for any K>0 obtainable by dividing J by 2 (rounding down) at least one time,
    • the J^th integer output is larger than the K^th if and only if the division by 2 that gave K (i.e., the last division) divided an odd integer.

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

This is a code golf. Output is a list of integers.

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

Note: when walking up in this tree towards its root, the parent is obtained by dividing the (one-based) index by two. The statement's "odd" and "larger" correspond to node at index J being compared to one of it's ancestor node at index K situated on the left and above.

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<n; j += (p[j]<t)+j+1 )
    if( p[j]==t )
      return j;
  return -1;
  }

// 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) )  // zero-based indexes
        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;
  }

Answer 1

Jelly, 11 9 bytes

JBÇṙ€1ỤỤịṢ

Try it online! Explanation:

J           Create a range 1-(length of input array).
 B          Convert all the elements to binary.
  ṙ€1       Rotate each element left by 1.
     ỤỤ     Find each element's position within the sorted list.
       ịṢ   Apply that permutation to the sort of the input.

Answer 2

Stax, 27 bytes

âX→δ╦Q),/BΦ♪ó╟&íY╧ù@T¶`&é²╞

Run it

This is the ascii representation of the same program.

o]wrEc%c:Gvsc:Gh-|m[@Q]/{fr{~FLc

The general idea is to sort the list, then calculate the first output as a function of the array length. Then queue the prefix and suffix for the same algorithm. The 0-based index of the next output is always min(N-high(N)/2, high(N)-1). high() clears all but the highest set bit.

o]                                  Sort input, and embed array in array.
  w                                 While; loop over the rest of the program
   rE                               Reverse, then explode array to stack.
                                        This makes each element a separate
                                        stack entry. 
     c%                             Length of this array chunk
       c:Gvsc:Gh-|m                 Calculate array index of output using
                                        given formula.
                   [                Copy current working array chunk.
                    @Q              Read at the calculated index, and output
                                        but leave on the stack.
                      ]/            Split the working chunk into two.
                        {f          Remove any resulting empty chunks.
                          r{~F      Push the remaining new smaller chunks to
                                        the input stack.  This will
                                        effectively put them at the end of
                                        the queue.
                              L     Combine all stack values into one list
                               c    Copy queue for use as while condition

Answer 3

Stax, 54 53 29 15 11 bytes

Credit to @Neil for simplifying the structure of the program so much that another 14 bytes have been saved (half of my original trimmed down post), and @recursive (creator of the Stax language) for streamlining the array manipulation to save 4 bytes.

óÆV¶┘Év▲♫☼»

Run and debug it online

About Stax:

From the first public golfing of Stax:

Stax is normally written in the printable ASCII character set.

This 11 byte submission is packed into a variant of the CP437 character set. The corresponding ascii representation takes 13 bytes:

oc%{:B|(m|o@m

Stax is a stack based language, but it has two data stacks, "main" and "input". Most operations use the main stack, but input starts on the input stack. Stax instructions are mostly one or two character ascii sequences. Most of them are overloaded, meaning their behavior is determined by the top few values on the stack(s).

Detailed explanation

This program does not use recursion. Instead, it uses a transform of the array [1..n](where n is the size of the input vector) to generate the necessary indexes such that when the input array is first sorted and then indexed with this array, it will give the correct result. Check the code for details.

For example, if n is 10, the transformed array is

[[1], [0, 1], [1, 1], [0, 0, 1], [0, 1, 1], [1, 0, 1], [1, 1, 1], [0, 0, 0, 1], [0, 0, 1, 1], [0, 1, 0, 1]]

which, if the final 1 in each of the embedded array is dropped, is simply a description of the path to walk from the root to the nth node, with 0 meaning going down the left branch and 1 going down the right. (This is the idea behind my original approach but I have made it much more complicated than needed)

Stax has the handy |o to transform it to the 0-based index array I need (credit to @Neil for directly sorting the embedded array without converting back to integer, as well as a much more efficient way to manipulate the array of the binary representation to achieve what I have in mind. The algorithm is now identical to that in his own answer in Jelly. ):

[6, 3, 8, 1, 5, 7, 9, 0, 2, 4]

This submission takes 48 steps in total for n=10.

The code has been much trimmed down by @Neil and further trimmed down by @recursive as I am not familiar with code golfing in general and this is my first submission in PPCG.

o               Sort input array
 c              Duplicate sorted array
  %             Size of the input array, denoted by `n` hereinafter

   {    m       Map range [1..n] (inclusive) with block (lambda){
    :B          Map the variable to its binary representation (as integer)
                It also works if `:B` is replaced with `|B` which returns a string of the binary representation.
      |(        And then rotate the array by 1 bit
                }

         |o     Get the destination index of each element if array were to be sorted
                This gives the index array needed
           @    Index the sorted input array with the index array 

            m   Print all elements of the array
                    One element on each line

---

_{If I am not mistaken, this is the second appearance of Stax (edit: within the first 5, confirmed by the @recursive) as a golfing language for a public challenge in PPCG. I really appreciate Stax and I want to express my respect and gratitude to its creator, @recursive.}

Answer 4

JavaScript (ES6), 176 144 104 bytes

a=>a.sort((a,b)=>a-b).map((_,i)=>(i+1).toString(2).slice(1)+1).map((e,_,b)=>a[[...b].sort().indexOf(e)])

After reading @WeijunZhou's answer I realised that he was over-complicating his bit-twiddling and came up with a simple JavaScript port. Previous 144-byte recursive version:

f=(a,l=a.length,n=1,...r)=>n>l?l?[a[p=Math.min(l-n/4,n/2-1)],...f(...r,a.slice(0,p),p,n/=2,a.slice(p+1),l-p-1,n)]:[]:f(a.sort((a,b)=>a-b),l,n*2)

Explanation: Having sorted the array, the position of the root of the binary tree is calculated. The array is then split into its left and right halves and these subarrays are queued to processes the remaining positions. Example: For the sorted array 2,3,5,7,11,13,17,19,23,29 the root is in position 6. The first element of the result is therefore 17. The array is then split into 2,3,5,7,11,13 for the second element and 19,23,29 for the third element. For the array 2,3,5,7,11,13 the root is in position 3. The second element of the result is therefore 7. The array is then split into 2,3,5 for the fourth element and 11,13 for the fifth element. The array 19,23,29 then provides the element 23, 2,3,5 provides 3 and 11,13 provides 13. Meanwhile the rest of the elements have been split into 1-element arrays which are in the correct order for the rest of the result.

Answer 5

Perl, 69 68 bytes

Includes +1 for a

perl -aE '$_=(sort{$a-$b}@F)[$n++]for sort@G=map{sprintf"%b1",++$m}@F;say"@G"' <<< "2 3 5 7 11 13 17 19 23 29"