Reorder list in python so even numbers appear first

Question

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!

Hmm, all you need to do is `sorted([ ... ], key=lambda n: n % 2)` — DeepSpace, May 13 '20 at 16:14
The solution you posted (once fixed) is preferable to using sort, since sort will run in O(n\*log(n)) time, while the posted solution is O(n). Given the requirement that no additional memory be used, it is reasonable to assume that this should work well for large lists, for which an O(n\*log(n)) solution is undesirable. — Tom Karzes, May 13 '20 at 16:44

X Æ A-Xiii · Answer 1 · 2020-05-13T16:33:18.080

1

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]

edited May 13 '20 at 16:33

answered May 13 '20 at 16:17

X Æ A-Xiii

576
4
14

Don't directly access `__` methods. Also, my comment shows a much more readable and idiomatic approach – DeepSpace May 13 '20 at 16:18
@DeepSpace lambdas are not idiomatic in Python. Guido even wanted them removed from the language entirely. What do you think is the problem to use a magic method as a callable *in the case that you are sorting a list of integers*? – X Æ A-Xiii May 13 '20 at 16:19
@TomKarzes Why do you say it's clearly meant to be solved in O(n) time? I don't see that clearly in the question at all. I do see it clearly that it should be in O(1) space. – X Æ A-Xiii May 13 '20 at 16:23
Given the requirement that no additional memory be used, it is reasonable to assume that this should work well for large lists, for which an O(n\*log(n)) solution is undesirable. Also note that OP's solution was adapted from an O(n) solution. It just has a simple bug which, when fixed, will result in a much faster solution (albeit less concise than using sort). – Tom Karzes May 13 '20 at 16:40
@TomKarzes Changing your position from from "clearly" to "it is reasonable to assume" is a big jump.. :) Anyway I don't believe the asymptotically optimal solution will actually be faster in practice, since pure-Python loops are so slow – X Æ A-Xiii May 13 '20 at 16:44
@XÆA-13 It will definitely be faster for large lists. Python loops incur a fixed overhead over compiled code, but in the long term algorithmic complexity will always dominate runtime. An O(n) algorithm in Python will be always be faster than an O(n\*log(n)) loop in C once n is large enough. – Tom Karzes May 13 '20 at 16:46
Once "n is large enough" is correct. But maybe the "n" required is bigger than the amount of memory even available in the computer. So, I don't make optimization decisions based on theoretical biases - measure with data instead. (To paraphrase Jerry Maguire, "show me the benchmarks!") – X Æ A-Xiii May 13 '20 at 16:48
@XÆA-13 I agree that it's much less clear-cut in a language like Python. In C the difference would be much more obvious. My interpretation of this question was that they wanted a good algorithm for solving the problem, independent of the language being used to implement it. On a level playing field, sort will lose. – Tom Karzes May 13 '20 at 17:11

score 1 · Answer 2 · answered May 13 '20 at 16:27

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]

vanPelt2 · Answer 3 · 2020-05-19T18:06:44.287

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.

`sort` is a bad way to do this. It's an O(n*log(n)) solution to an O(n) problem. — Tom Karzes, May 13 '20 at 16:36

Tom Karzes · Answer 4 · 2020-05-13T17:14:09.120

1

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.

edited May 13 '20 at 17:14

answered May 13 '20 at 16:32

Tom Karzes

22,815
2
22
41

At what `n` will the *O(n)* approach shown in question consistently outperform the *O(n log n)* approach of using sort? – X Æ A-Xiii May 13 '20 at 17:01
@XÆA-13 It might need to be very large, but keep in mind that using sort also requires a lambda to be passed in (unless you try to access the internal `__rmod__` method, but that's not a very general approach). My interpretation of this question was that they wanted a good algorithm for solving the problem, independent of the language being used to implement it. On a level playing field, sort will lose. – Tom Karzes May 13 '20 at 17:08
You are right that sort is not arithmetically optimal, but I object to all these claims in comments like "sort is a bad way to do this". Using an overly complicated method, which turns out is actually slower in practice, is a bad way to do this. I was not able to discover the crossover point yet- have measured up to a gigabyte of data and sorting is still significantly faster.. – X Æ A-Xiii May 13 '20 at 17:18
@XÆA-13 If you're going to compare them, I would suggest using a `lambda` as the sort key function, rather than `__rmod__` which isn't really a fair comparison. – Tom Karzes May 13 '20 at 17:20
Up to 2^27 integers, sort was winning, at 2^28 the OP code overtook. My bench is here: https://repl.it/repls/UrbanPartialActivecontent (but it seems that repl.it OOM kills it before you can witness the takeover point). – X Æ A-Xiii May 13 '20 at 17:45

score 1 · Answer 5 · answered May 13 '20 at 16:33

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]

Kriti Pawar · Answer 6 · 2020-05-19T18:34:12.980

0

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

edited May 19 '20 at 18:34

answered May 19 '20 at 18:28

Kriti Pawar

832
7
15

Reorder list in python so even numbers appear first

6 Answers6

What is this doing?

Why do we need it?

Your code updated