Different sorting orders - divide and win?

Question

I am trying to rebuild the list of objects in different ways. Here I will use integers, but there could be anything on this list.

The sample code below sorts 1,2,3,4,5,6,7,8 in the following order: 1,8,2,7,3,6,4,5

So, first .. last .. second .. second to last, etc. it may be a little awkward, but it works.

Now what I'm trying to do now is to list the list in a different order so that it continues to divide by two. I think it can be called Divide and Conquer, but after trying / searching for some recursive sort code, etc. I don’t understand very clearly how to implement this here.

I hope to get an ordered number this way.

1,8,4,2,6,3,5,7

first, last, half, first half half, second half half, etc.

So, in other words, I'm trying to split a set of numbers in half ... then for each half, in turn, split them in half .. etc.

  1 2 3 4 5 6 7 8
 1 (first item)
               8 (last item)
       4 (mid item)
   2 (mid of first half) 
           6 (mid of second half)
     3 (mid of 1st chunk)
         5 (mid of 2nd chunk)
            7 (mid of 3rd chunk)

If anyone could show me how to do this, with this simple example it would be really great.

static void Main(string[] args) { List<int> numberlist = new List<int>(); numberlist.Add(1); numberlist.Add(2); numberlist.Add(3); numberlist.Add(4); numberlist.Add(5); numberlist.Add(6); numberlist.Add(7); numberlist.Add(8); int rev = numberlist.Count-1; int fwd = 0; // order 1,8,2,7,3,6,4,5 for (int re = 0; re < numberlist.Count; re++) { if (re % 2 == 0) { Console.WriteLine(numberlist[fwd]); fwd++; } else { Console.WriteLine(numberlist[rev]); rev--; } } Console.ReadLine(); } 

A few additional sampling and output ranges to read from left to right, top to bottom:

  1 2 3 4 5 6 7
 1 7
       4
   2 5
     3 6

 1 2 3 4 5 6 7 8 9 10 11 12
 1 12
           6 
     3 9 
   2 4 7 10
         5 8 11


 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
 1 16
               8 
       4 12
   2 6 10 14
     3 5 7 9 11 13 15 

Answer 1

Let me see if I understand this problem. Let the example work with a large number of elements:

Do you need this order?

 ABCDEFGHIJKLMNOPQ AQI EM CGKO BDFHJLNP 

It seems simple. Create a data structure called the Interval, which has two fields: the largest lower bound and the least upper bound. That is, which elements are the biggest thing that is below the interval and the smallest thing that is above the interval. The algorithm is as follows:

 Input: the size of the array. Yield the first item -- if there is one Yield the last item -- if it is different from the first item. Make a queue of intervals. Enqueue the interval (0, array.Length - 1) While the queue is not empty: Dequeue the queue to obtain the current item. Is the interval empty? If so, skip this interval Otherwise, the interval has a GLB, a LUB, and a value in the middle. Yield the middle of the interval Enqueue the interval (bottom, middle) Enqueue the interval (middle, top) 

Let's look at the example above. We have an array of ABCDEFGHIJKLMNOPQ .

 Yield A Yield Q Enqueue AQ. The queue is now AQ Is the queue empty? No. Dequeue the queue. It is now empty. current is AQ Is the current interval empty? no. The middle is I. Yield I. Enqueue AI. The queue is now AI. Enqueue IQ. The queue is now AI, IQ. Is the queue empty? No. Dequeue the queue. It is now IQ. current is AI. Is the current interval empty? No. The middle is E. Yield E. Enqueue AE. The queue is now IQ, AE. Enqueue EI. The queue is now IQ, AE, EI Is the queue empty? No. Dequeue. The queue is now AE, EI current is IQ The middle is M Yield M. Enqueue IM Enqueue MQ. The queue is now AE, EI, IM, MQ OK, let start skipping some steps here. The state of the queue and the yields are: Yield C EI, IM, MQ, AC, CE Yield G IM, MQ, AC, CE, EG, GI Yield K MQ, AC, CE, EG, GI, IK, KM yield O AC, CE, EG, GI, IK, KM, MO, OQ yield B CE, EG, GI, IK, KM, MO, OQ, AB, BC OK, skip more steps... Yield D, F, H, J, L, N, P Queue is now AB, BC, CD, DE, ... PQ Every interval is now empty, so we skip all of htem and we are done. 

Make sense?

The trick here is to notice that the order you want is a wide selection of wood. You just need to be able to "see" the array in the tree structure that you want to cross.

By the way, the ordering seems a little strange. For the most part, ordering "divides the range into two parts and gives the middle of each range in the first place." Why, then, are the two extremes inferior first, and not the last? I would find an order:

 ABCDEFGHIJKLMNOPQ I EM CGKO BDFHJLNP AQ 

more intuitively obvious; if things “in the middle” always take precedence over things “to the extremes,” then the extremes should go last, not first.

Answer 2

I can demonstrate a similar choice; this leads to a slightly different order of yours.

Take numbers from 0 to 7 and produce them in binary format: 000 001 010 011 100 101 110 111 .

Now cancel them: 000 100 010 110 001 101 011 111 .

In decimal form, this gives 0 4 2 6 1 3 5 7. So, you start with the first element, then halfway through the rest of the elements, then a quarter and three quarters, and then finally all the elements with an odd number.

Obviously, this procedure only works for exact powers of two.