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.

Pages: 1 2

10 Responses to “Interleaved Increasing-Decreasing Sort”

  1. 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";
    
  2. Daniel said

    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);
    end
    
  3. Rutger said

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

  4. matthew said

    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])
    
    $ python slice.py 10
    [4, 6, 2, 9, 7, 5, 1, 8, 3, 0]
    [1 9 2 8 3 6 4 5 7 0]
    [1 2 3 4 7]
    [9 8 6 5 0]
    $ python slice.py 11
    [3, 8, 6, 2, 5, 0, 9, 1, 4, 10, 7]
    [ 3 10  4  8  5  2  6  1  7  0  9]
    [3 4 5 6 7 9]
    [10  8  2  1  0]
    
  5. Daniel said

    > “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;
    	}
    }
    
  6. Daniel said

    > “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);
    }
    
  7. Daniel said

    The signature for iidsort should be:

    public static void iidsort(int[] lst)
    

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

  8. Globules said

    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]
    
    $ ./incdecsort 
    [0,9,2,7,4,5,6,3,8,1]
    
  9. Chris Judge said

    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?

  10. Ankur Sharma said

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

    }
    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: