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.
Programming Praxis 
sub srt { my @a = sort @_; my @c; push @c,shift @a,pop @a while @a; return @c; } print join ' ',srt( qw(0 1 2 3 4 5 6 7 8 9) ),"\n";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).
function sorted = iidsort( l ) %IIDSORT IID = "Interleaved Increasing-Decreasing" sorted = sort(l); endeven = length(l); if mod(endeven,2) ~= 0 endeven = endeven - 1; end sorted(2:2:endeven) = sorted(endeven:-2:2); endIn 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:
import sys import random import numpy def slicesort(a): a = numpy.array(a) a[0::2].sort() a[-1-(len(a)%2)::-2].sort() return a a = range(int(sys.argv[1])) random.shuffle(a) print(a) a = slicesort(a) print(a) print(a[0::2]) print(a[1::2])> “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).
// throughout the code, lo is inclusive and hi is exclusive. // in-place Lomuto partition. Returns index of pivot after partitioning. private static int partition(int[] lst, int lo, int hi) { int pivot = lst[hi-1]; // i is the start index of the greater-than-pivot sub-array // j is the index of the current element int i = lo; for (int j = lo; j < hi-1; j++) { int val = lst[j]; if (val < pivot) { int tmp = lst[i]; lst[i] = val; lst[j] = tmp; i++; } } lst[hi-1] = lst[i]; lst[i] = pivot; return i; } // sorts a list in-place using qsort. private static void sort(int[] lst, int lo, int hi) { if (lo < hi) { int idx = partition(lst, lo, hi); sort(lst, lo, idx); sort(lst, idx + 1, hi); } } private static void sort(int[] lst) { sort(lst, 0, lst.length); } // iid: interleaved increasing-decreasing sort // sorts in-place // O(n log n) public static void iidsort(int[] lst) { sort(lst); // O(n log n) int lastodd = lst.length - (lst.length % 2 == 0 ? 1 : 2); // O(n) for (int i = 1; i < lst.length / 2; i += 2) { int tmp = lst[i]; lst[i] = lst[lastodd - i + 1]; lst[lastodd - i + 1] = tmp; } }> “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).
// throughout the code, lo is inclusive and hi is exclusive. private static int reidx(int[] lst, int idx) { if (idx % 2 == 0) { return idx; } else { int lastodd = lst.length - (lst.length % 2 == 0 ? 1 : 2); return lastodd - idx + 1; } } // in-place Lomuto partition. Returns index of pivot after partitioning. private static int partition(int[] lst, int lo, int hi) { int pivot = lst[reidx(lst, hi-1)]; // i is the start index of the greater-than-pivot sub-array // j is the index of the current element int i = lo; for (int j = lo; j < hi-1; j++) { int val = lst[reidx(lst, j)]; if (val < pivot) { int tmp = lst[reidx(lst, i)]; lst[reidx(lst, i)] = val; lst[reidx(lst, j)] = tmp; i++; } } lst[reidx(lst, hi-1)] = lst[reidx(lst, i)]; lst[reidx(lst, i)] = pivot; return i; } private static void iidsort(int[] lst, int lo, int hi) { if (lo < hi) { int idx = partition(lst, lo, hi); iidsort(lst, lo, idx); iidsort(lst, idx + 1, hi); } } // iid: interleaved increasing-decreasing sort private static void iidsort(int[] lst) { iidsort(lst, 0, lst.length); }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.
import Data.List (sort, sortOn, transpose) import Data.Ord (Down(..)) incDecSort :: Ord a => [a] -> [a] incDecSort = merge . zipWith ($) [sort, sortOn Down] . split where merge = concat . transpose split = foldr (\x [l,r] -> [x:r,l]) [[],[]] main :: IO () main = print $ incDecSort [0..9]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);
}
}