Shuffle an int array such that array elements in even indices are smaller than array elements in odd indices

Question

I need to have all the elements in the even indices arr[0],arr[2],arr[4] etc be smaller than the elements with odd indices arr[1],arr[3],arr[5], etc

My approach was to find the MEDIAN and then write out all elements smaller than the median in odd indices and all elements larger than the median in even places.

Question: is there a way to do the array shuffling IN PLACE after finding the median ?

import random
def quickselect(items, item_index):
    def select(lst, l, r, index):
        # base case
        if r == l:
            return lst[l]

        # choose random pivot
        pivot_index = random.randint(l, r)

        # move pivot to beginning of list
        lst[l], lst[pivot_index] = lst[pivot_index], lst[l]

        # partition
        i = l
        for j in range(l+1, r+1):
            if lst[j] < lst[l]:
                i += 1
                lst[i], lst[j] = lst[j], lst[i]

        # move pivot to correct location
        lst[i], lst[l] = lst[l], lst[i]

        # recursively partition one side only
        if index == i:
            return lst[i]
        elif index < i:
            return select(lst, l, i-1, index)
        else:
            return select(lst, i+1, r, index)

    if items is None or len(items) < 1:
        return None

    if item_index < 0 or item_index > len(items) - 1:
        raise IndexError()

    return select(items, 0, len(items) - 1, item_index)

def shuffleArray(array, median):
    newArray = [0] * len(array)
    i = 0
    for x in range(0,len(array),2):
        newArray[x] = array[i]
        i+=1

    for y in range(1,len(array),2):
        newArray[y] = array[i]
        i+=1

return newArray

What exactly is your question, and what have you tried so far? — PL200, Nov 05 '18 at 00:58
@JohnAnderson I don't think that would work. For example if your array is `[7, 8, 9, 10]`, then 9 (at array index 2) is greater than 8 (at array index 1). — John Gordon, Nov 05 '18 at 01:05
How is your [too broad] question related to python, especially to python-3.x? — DYZ, Nov 05 '18 at 01:05

score 1 · Answer 1 · answered Nov 05 '18 at 01:09

So here's my interpretation of the question.

Shuffle an array so that all data in even indices are smaller than all data in odd indices. Eg [1, 3, 2, 4] would be valid, but [1, 2, 3, 4] wouldn't be. This stops us just being able to sort the array.

Sort the array, smallest to largest.
Split the array at its mid point (rounding the mid point down).
Shuffle the two arrays together. Such that given array [1, 2, 3] and array [4, 5, 6] it becomes [1, 4, 2, 5, 3, 6].

To elaborate on 3, here's some example code... (using javascript)

let a = [ 1, 2, 3 ];
let b = [ 4, 5, 6 ];
let c = [ ] // this will be the sorted array
for (let i = 0; i < a.length + b.length; i++ ) {
    if(i % 2 == 0) c.push( a[Math.floor( i/2 )]);
    else c.push( b[Math.floor( i/2 )]);
}

This produces the array [1, 4, 2, 5, 3, 6], which i believe fufils the requirement.

Shuffle an int array such that array elements in even indices are smaller than array elements in odd indices

1 Answers1