Sorting for search by monotomy

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 Jth integer output is larger than the Kth 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;
}
• Usually the tie-breaker is the earliest posted submission. It's not recommended to use running time or speed or anything else as a tie-breaker, since then solvers of this challenge will have to account for those factors too. – Erik the Outgolfer Feb 9 '18 at 15:00
• I've VTCed this as unclear; after reading through it 3 times and trying to decipher the lone test case, I still don't know what's being asked of us and, what little I thought I understood is contradicted by the test case. – Shaggy Feb 9 '18 at 15:04
• Sorry, I don't mean to be obstinate, but I still don't understand why the 5 and the 7 have to be where they are rather than flip-flopped. I understand the rest of the number, just not those two. – AdmBorkBork Feb 9 '18 at 19:06
• @AdmBorkBork: the J=9th integer (5) must be smaller than the K=2th (7) because when dividing J by two (hiving M=4), then by two again (giving K=2), the M=4 (from which K=2 was obtained) is even. See the explanation in version 5 for J=9 and K=2 (removed for it took so much room). Alternatively, run monotomic() with the integers in p (zero-based), or/and the whole sample code with a modified order. – fgrieu Feb 9 '18 at 19:21
• FWIW YMMV, but I think another way to say this would be to put the numbers into a left-biased binary tree, and then produce a breadth-first traversal. – recursive Feb 10 '18 at 4:24

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.

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

Stax, 54532915 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

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

[, [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.

• Wow! I'm honestly surprised to see someone else using this new language. Please let me know if you find it confusing or have suggestions. – recursive Feb 10 '18 at 8:22
• @recursive I just want to say it is so good. The documentation is also clear and extensive. Some of the instructions do things beyond my wildest imagination of a golfing language, plus that it can be debugged easily online. I really love it and thank you for your marvelous work. – Weijun Zhou Feb 10 '18 at 8:26
• Thanks for your appreciation. I will analyze your program in more depth soon, but for starters, I can tell you that you can eliminate the first ~ at the beginning of the program. It means "push to input" stack, as you know. However, the only available value is already on the input stack, so it doesn't do anything in that usage. Also, technically, I've made a couple of other submissions since that one, but I'm pretty sure you're in the first 5 though. – recursive Feb 10 '18 at 8:30
• Your inner loop is much more complicated than it needs to be, the whole thing can be done in 15 bytes (18 unpacked: o~;%c~{:B|(F,l|o@m). – Neil Feb 10 '18 at 21:33
• Nice explanation! (I was wondering how the binary related to the resulting tree; the reason for using a rotation is so that the walk to a given node sorts after the walk to a node to its left but before the walk to a node to its right.) – Neil Feb 11 '18 at 9:57

JavaScript (ES6), 176144 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.

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"