Reorder list in python so even numbers appear first

user_11803732 0
Viewed 1092

I am going through Elements of Programming Interviews in Python and am confused by this problem. The problem takes an array of numbers and is supposed to output a list where the even numbers are ordered first. You're supposed to do it without allocating extra storage.

They gave a solution, and I tested it out, but it didn't give the right answer. 

def even_odd(arr):
    next_even = 0
    next_odd = len(arr) - 1

    while next_even < next_odd:
        if arr[next_even] % 2 == 0:
            next_even += 1
            print("next" + str(next_even))
        else:
            arr[next_even] = arr[next_odd]
            arr[next_odd] = arr[next_even]
            next_odd -= 1
            print(arr)
            print("first" + str(arr[next_even]))
    return arr


print(even_odd([1, 2, 3, 4, 5, 6]))

The result was [6, 2, 4, 4, 5, 6] I also don't understand the mechanism of swapping elements with each other (A[next_even], A[next_odd] = A[next_odd], A[next_even]). I think this is an important concept when you can't create another array, you have to swap elements, but I just can't seem to wrap my head around it.

Can someone help where my code went wrong and explain the swapping? Thanks!

python
6 Answers

Think about these lines:

arr[next_even] = arr[next_odd]
arr[next_odd] = arr[next_even]

Whatever the values of next_even and next_odd, the result will be that the values at those indices are equal. That's clearly bugged. If you change it instead to be a swap, the algorithm works:

arr[next_even], arr[next_odd] = arr[next_odd], arr[next_even]

As a final note, just using a sort without allocating extra storage, should be much easier approach in Python. Simply:

>>> L = [1, 2, 3, 4, 5, 6]
>>> L.sort(key=(2).__rmod__)
>>> L
[2, 4, 6, 1, 3, 5]
user_135280170

You are swapping without checking if the element at index next_odd is even or odd. If the element at next_odd is odd, just move the index to left.

def even_odd(arr):
    next_even = 0
    next_odd = len(arr) - 1

    while next_even < next_odd:
        if arr[next_even] % 2 == 0:
            next_even += 1
        else:
            if arr[next_odd] % 2 == 0:
                arr[next_odd], arr[next_even] = arr[next_even], arr[next_odd]
                next_even += 1
                next_odd -= 1
            else:
                next_odd -= 1
    return arr


print(even_odd([1, 5, 2, 0, 3, 4, 5, 7, 8, 1, 10]))

[10, 8, 2, 0, 4, 3, 5, 7, 5, 1, 1]
user_62873080

As was already pointed out in a comment, the simplest (though not least expensive) way to do this is with the lists's sort() method, with a key that determines whether or not an entry is even.

>>> numbers = [1, 2, 3, 4, 5, 6]
>>> numbers.sort(key=lambda n: n % 2 != 0)
>>> print(numbers)
[2, 4, 6, 1, 3, 5]

To answer your original question, in Python you can switch the value of two variables simultaneously with a, b = b, a. This is equivalent to

c = a    # Remember the value of a.
a = b    # Overwrite the value of a with the value of b.
b = c    # Overwrite the value of b with the original value of a.

except the swap syntax cleans up any allocated space for the variable c.

The issue in your code is the line

arr[next_even] = arr[next_odd]    # Overwrite the value of arr[next_even].

This is like the step a = b, but you haven't stored the old value with something like c = a. To do this explicitly, you need to do

temp = arr[next_even]
arr[next_even] = arr[next_odd]
arr[next_odd] = temp

or simply use the nice swap syntax,

arr[next_even], arr[next_odd] = arr[next_odd], arr[next_even]

See also Python Simple Swap Function.

user_74079670

The problem with your code is the element swap:

arr[next_even] = arr[next_odd]
arr[next_odd] = arr[next_even]

The doesn't work, because the second assignment is picking up the new value of arr[next_even], which is arr[next_odd], so the assignment isn't doing anything. Together, they're just copying arr[next_odd] to arr[next_even] without changing arr[next_odd].

A simple way to fix it is to do:

tmp = arr[next_odd]
arr[next_odd] = arr[next_even]
arr[next_even] = tmp

A more concise way to do it in Python, which you asked about, is:

arr[next_even], arr[next_odd] = arr[next_odd], arr[next_even]

Basically it's doing:

a, b = b, a

This works because the right side is evaluated before any of the assignments on the left side take place. So it correctly swaps a and b.

Note that your posted solution (with this fix) runs in linear time, O(n), without the need for additional storage. The solutions that involve calling sort will run in O(n*log(n)) time.

user_54607190

Swapping can be done by doing this (or something similar)

arr[i], arr[i+1] = arr[i+1], arr[i]

What is this doing?

Lets say we have an array = [1,2,3,4].

If we do something like array[0], array[1] = array[1], array[0] we are "swapping" these array values.

So the resulting array will be [2,1,3,4]. This is because array[0] is being assigned the value at array[1] and array[1] is being assigned the value at array[0].

Why do we need it?

This effectively saves us the need of a temporary variable to perform the swap. If instead we try to do the swap and not use the syntax above we get something like follows:

array = [1,2,3,4]
array[0] = array[1] # [2,2,3,4] We have lost the value 1

So instead we need a temporary value to hold the value we are "swapping"

array = [1,2,3,4]

temp = array[0] #1
array[0] = array[1] # [2,2,3,4] We have lost the value 1
array[1] = temp #[2,1,3,4]

Your code updated

def even_odd(arr):
    next_even = 0
    next_odd = len(arr) - 1

    while next_even < next_odd:
        if arr[next_even] % 2 == 0:
            next_even += 1
        else:
            arr[next_even], arr[next_odd] = arr[next_odd], arr[next_even]
            next_odd -= 1
    return arr


print(even_odd([1, 2, 3, 4, 5, 6])) # Output: [6, 2, 4, 5, 3, 1]
user_119595670

You can also try this if sequence doesn't matter just even number should be listed first:

def even_odd(arr):
    u = 0
    for i in range(len(arr)):
        if arr[u]%2!=0:
            temp = arr[u]
            arr.remove(arr[u])
            arr.append(temp)
        else:
            u+=1
    return arr
user_135654940
Related