2

I am trying to move even numbers in an array to the front and odd numbers to the back of the array. The problem asks to do this in a Linear Algorithm and do this In Place.

I came up with this:

 def sort(a): for i in range(0,len(a)-1): if a[i]%2==0: a.insert(0,a.pop(i)) return a

The issue is that, someone told me that technically, a.insert is an o(n) function so technically this would be considered a non-linear algorithm (when including the for i in range part of the function). Since the forum that asked this question is a couple months old, I couldn't ask for an explanation.

Basically I believe he said "Technically" because since this inserts it at the front, it does not check another N number of elements in the array, therefore making it run for practical purposes at O(n) and not O(n^2). Is this a correct assessment?

Also, someone on the forum used a.append to modify the above and changed it to look for odd numbers. No one replied so I was wondering, is a.append not an o(n) function since it moves it to the end? Is it o(1)?

Thanks for explanations and clarifications!

Improve this question
3
  • 1
    O(n) is linear Commented Jul 5, 2012 at 1:51
  • Oops. Sorry I meant it wasn't linear when you also factor in the for i in range I've edited my question. Commented Jul 5, 2012 at 2:01
  • 1
    lst = [i for i in lst if not i % 2] + [i for i in lst if i % 2] Commented Jul 5, 2012 at 7:55

5 Answers 5

Reset to default
10

insert at the 0th index of a list requires shifting every other element along which makes it an O(N) operation. However, if you use a deque this operation is O(1).

append is an amortized O(1) operation since it simply requires adding the item on to the end of the list and no shifting is done. Sometimes the list needs to grow so it is not always an O(1) operation.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

Actually it's only an amortized O(1) for append as well, for obvious reasons (we have to grow the list sometimes).
@Voo Ok then I will change it to average case and include that information.
Note that average case complexity is not the same as amortized complexity. The former is some kind of complexity with "average" (but not all) data/parameters, the latter applies to all inputs and denotes the complexity you get per operation if you repeat the operation frequently. That is, an average-case O(1) append might as well take O(n!) with some lists (e.g. sorted ones), an amortized O(1) append is O(1) when you repeatedly append, look at the total time, and average that - regardless of what's in the list.
6

That is correct - insertion at the front of a Python standard list is O(n). Python lists are implemented as arrays, and thus inserting something at the front of the list requires shifting the entire contents over one spot. Appending, on the other hand, does not require any shifting, and thus is amortized O(1).

Note, however, that a.pop(i) is also an O(n) operation, because it requires shifting everything after the popped item over one spot. Thus, simply modifying your code to use append() instead of insert() would still not result in a linear algorithm.

A linear-time algorithm wouldn't use pop() but instead would do something like swap elements around so that the rest of the list doesn't have to be modified. For example, consider this:

def even_to_front(a_list): next_even = 0 for idx in xrange(len(a_list)): if not a_list[idx] % 2: # a_list[idx] is even, so swap it towards the front a_list[idx], a_list[next_even] = a_list[next_even], a_list[idx] next_even += 1
Improve this answer

1 Comment

Hey great answer. Thanks for teaching me it shifts everything to the right 1. I didn't realize that was what made it technically work on another n elements!
2

Check this table of complexity

  • Insert - O(n)
  • Append - O(1) (lists are over allocated)
Improve this answer

1 Comment

Thanks for that table. It will definitely be invaluable as I go forward!
2

Here's how it can be done without append/insert or dequeue

def sort(L): i, j = 0, len(L)-1 while i<j: # point i to the next odd number from the start while i<j and not L[i]%2: i+=1 # point j to the next even number from the end while i<j and L[j]%2: j-=1 L[i],L[j] = L[j],L[i]
Improve this answer

Comments

0

Every time you pop element from a list, you have to copy the trailing portion of the list to move it over one index to fill the hole left by the removed element. This is linear in the distance between the popped element and the tail of the list.

Every time you insert an element into a list, you have to copy the trailing portion of the list to move it over one index to create a spot to insert the new element. This is linear in the distance between the position into which you're inserting the element and the tail of the list.

If you use collections.deque, you can append and pop to both the front and the back in O(1) time. However, removing an element from the middle still be linear (and I think you'd have to write it yourself).

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.