Python: Alternating elements of a sorted array

Question

In my little project here I have sorted a list in decending order, however, my goal is to sort it in this custom pattern. (largest -> smallest -> next largest -> next smallest ->)etc.

In java I was able to do this like this:

public static void wackySort(int[] nums) {
    //first, this simply sorts the array by ascending order.
    int sign = 0;
    int temp = 0;
    int temp2 = 0;
    for (int i = 0; i < nums.length; i++) {
        for (int j = 0; j < nums.length -1; j++){
            if (nums[j] > nums[j+1]) {
               temp = nums[j];
               nums[j] = nums[j+1];
               nums[j+1] = temp;
            }
        }
    }

    //prepare for new array to actually do the wacky sort.
    System.out.println();
    int firstPointer = 0;
    int secondPointer = nums.length -1;
    int[] newarray = new int[nums.length];
    int size = nums.length;

    //increment by two taking second slot replacing the last (n-1) term
    for (int i = 0; i < nums.length -1; i+=2) {
        newarray[i] = nums[firstPointer++];
        newarray[i+1] = nums[secondPointer--];
    }

    //store those values back in the nums array    
    for (int i = 0; i < nums.length; i++) {
        nums[i] = newarray[i];
    }
}

My goal is to do the same thing but in python, except backwards. Any ideas on how to convert that last for loop that does the wackysort into python and make it go backwards?

Answer 1

nums = [1, 2, 3, 4]
newarray = sum(zip(reversed(nums), nums), ())[:len(nums)]

>>> print(newarray)
(4, 1, 3, 2)

---

What it does, step by step. first, reversed():

>>> list(reversed(nums))
[4, 3, 2, 1]

Then zip():

>>> list(zip([4, 3, 2, 1], [1, 2, 3, 4]))
[(4, 1), (3, 2), (2, 3), (1, 4)]

You can see we have almost the list we want, we have a problem: these are tuples. we want to flatten them.

>>> (4, 1) + (3, 2) + (2, 3) + (1, 4)
(4, 1, 3, 2, 2, 3, 1, 4)

Oh. That's nice. But how to do it inside the list? Simple: use sum(), which does exactly this - adding many things together. Only we need to give it something to start with - an empty tuple ():

>>> sum([(4, 1), (3, 2), (2, 3), (1, 4)], ())
(4, 1, 3, 2, 2, 3, 1, 4)

But the we don't want the second half, so let's remove it. We know he list is exactly twice too long, yes?

>>> (4, 1, 3, 2, 2, 3, 1, 4)[:len(nums)]
(4, 1, 3, 2)

That's it.

---

Another option:

from itertools import chain, islice
a = list(islice(chain.from_iterable(zip(nums, reversed(nums))), len(nums)))

Answer 2

I would suggest sorting it normally first, then doing your shuffle:

inlist=[3,5,7,6,9,8,2,1]
inlist.sort()
outlist=[]
while len(inlist)>0:
  if (len(outlist)%2==0):
      outlist.append(inlist.pop())
  else:
      outlist.append(inlist.pop(0))

Answer 3

That last for loop:

for (int i = 0; i < nums.length; i++){
    nums[i] = newarray[i];

… is a one-liner in Python. The exact equivalent is:

nums[:] = newarray[:len(nums)]

However, most likely, all you really need is:

nums = newarray

---

If you really want to write it in "Java style" for some reason, it would be this:

i = 0
while i < len(nums):
    nums[i] = newarray[i]
    i += 1

But that does exactly the same thing as the first version, except a slower more slowly and less readably.

---

Meanwhile, for the previous loop:

for (int i = 0; i < nums.length -1; i+=2){
    newarray[i] = nums[firstPointer++];
                newarray[i+1] = nums[secondPointer--];

Again, you can translate this more-or-less directly to Python:

i = 0
while i < len(nums)-1:
    newarray[i] = nums[firstPointer]
    firstPointer += 1
    newarray[i+1] = nums[secondPointer]
    secondPointer -= 1
    i += 2

But as with the last version of the last loop, this is horribly unreadable, and you'll be a lot happier if you try to describe the algorithm, then write that in Python.

Answer 4

As I said in a comment on your previous question, the simplest way to do what (I think) you want is to first write a function that can swap an already-sorted list into your desired order, then you can just chain your sorting function and the new function together.

def wacky_sort(seq):
    # code you already have

def alternate_ends(seq):
    new_seq = []
    while seq:
        new_seq.append(seq.pop(0))
        if seq:
            new_seq.append(seq.pop())
    return new_seq

def wacky_sort_with_alternating_ends(seq):
    wacky_sort(seq)
    return alternate_ends(seq)

Answer 5

If you want to slove this question in O(1)extra space and O(n)time then you can solve like below code.

def rearrange(arr, n):

k,j=1,1
a=[0]*n
for i in range(0,n):

    if i%2==0:
        a[i]=arr[n-k]
        k=k+1

    else:
        a[i]=arr[i-j]
        j=j+1
for i in range(n):
    arr[i]=a[i]