## Interleaved Increasing-Decreasing Sort

### May 13, 2016

We have a two-stage solution: First, sort the input, without regard to even/odd indexes. Second, reverse the subarray at the odd indexes:

(define (f xs) (let ((xs (vector-sort < xs)) (len (vector-length xs))) (do ((lo 1 (+ lo 2)) (hi (- len (if (even? len) 1 2)) (- hi 2))) ((<= hi lo) xs) (let ((t (vector-ref xs lo))) (vector-set! xs lo (vector-ref xs hi)) (vector-set! xs hi t)))))

> (f '#(6 2 4 5 7 1 3 0 9 8)) #(0 9 2 7 4 5 6 3 8 1)

You can run the program at http://ideone.com/SMRv0a.

I want (intend) to implement a sorting algorithm that does this, rather than call sort from a standard library or external library, but I don’t have much energy at the moment (jetlagged).

Anyhow, here’s a solution in matlab (haven’t tested Octave).

In Python:

values = range(10)

print “”.join(map(str, [x for t in zip(sorted([x for i,x in enumerate(values) if not i % 2]), sorted([x for i,x in enumerate(values) if i % 2], reverse=True)) for x in t]))

And another Python solution: it’s not clear if we are meant to be separately sorting the odd and even positions, or just coming up with any permutation with the odd and even positions sorted as required. The former seems more interesting & involves sorting slices of the original array: it’s nice to do that in place & we can do that, for example, with slices of Python numpy arrays which construct a view onto the original array (slices of Python lists create new lists so aren’t in place). numpy sort only supports ascending order so we construct a reversed slice starting at an appropriate offset from the end of the array:

> “I want (intend) to implement a sorting algorithm that does this, rather than call sort from a standard library or external library…”

Here’s a Java solution that first sorts the array using quick sort, and then reverses the elements at even indexes (even with respect to 1-based indexing, odd with respect to 0-based indexing).

> “I want (intend) to implement a sorting algorithm that does this, rather than call sort from a standard library or external library…”

I was jetlagged when I wrote that. I think my actual intent was not to write a normal sorting algorithm, and then re-arrange, but rather to write a sorting algorithm that does the interleaved increasing-decreasing sort at sort-time. Here’s a solution in Java. It’s similar to my solution above, but at sort-time the indexing considers the interleaved increasing-decreasing ordering (using the reidx function).

The signature for iidsort should be:

I mistakenly left it private since it was based on the original quick sort I wrote, which was private. (the original iidsort method was correctly public).

A Haskell version.

Unless – in addition to the ascending/descending requirements of the even and odd slots – even numbers are supposed to end up in the even slots (and odd numbers in the odd slots), why would 0123456789 sort to 0927456381? I would think the more natural output would be 0918273645 – i.e. the even slots contain 01234 and the odd slots contain 98765.

And if the problem does include this unstated additional requirement, then it raises other questions when one is sorting an input of, say, 0468248820. Or is this just a poorly written problem that is only supposed to work with the one given input?

import java.util.*;

class Increasing_Decreasing_Sort {

static int getLength(int ar[]){

int len =ar.length-1;

if(ar.length%2 !=0)

return ar.length-2;

return len;

}

public static int[] sortByInc_Dec(int ar[]){

//First Sort the Array, If array is not Sorted

Arrays.sort(ar);

int len = Increasing_Decreasing_Sort.getLength(ar);

for(int i = 0; i < ar.length/2; i++){

if((i%2) != 0){

int temp = ar[i];

ar[i] = ar[len];

ar[len] = temp;

len =len-2;

}

}

return ar;

}

static void print(int ar[]){

for(int i : ar)

System.out.print(i+" ");

System.out.println(" ");

}

public static void main(String[] args){

int ar[] = {3,1,2,4,0,5,6,7,8,9};

int ans[] = sortByInc_Dec(ar);

print(ans);

}

}