## Interleaved Increasing-Decreasing Sort

### May 13, 2016

This must be somebody’s homework:

Given an array of integers, rearrange the elements of the array so that elements in even-indexed positions are in ascending order and elements in odd-indexed positions are in descending order. For instance, given the input 0123456789, the desired output is 0927456381, with the even-indexed positions in ascending order 02468 and the odd-indexed positions in descending order 97531.

Your task is to write a program that performs the indicated rearrangement of its input. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Advertisements

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);

}

}