Stack Overflow is a community of 4.7 million programmers, just like you, helping each other.

Join them; it only takes a minute:

Sign up
Join the Stack Overflow community to:
  1. Ask programming questions
  2. Answer and help your peers
  3. Get recognized for your expertise

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!

share|improve this question
up vote 4 down vote accepted

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.

share|improve this answer

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
share|improve this answer

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]    
share|improve this answer

Check this table of complexity

  • Insert - O(n)
  • Append - O(1) (lists are over allocated)
share|improve this answer

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).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.
{"cc_re__cc_re__cc_by_sa_3_0": ["                       <li><a href=\"//area51.stackexchange.com\" title=\"proposing new sites in the Stack Exchange network\">Area 51</a></li>\r\n                        <li><a href=\"//careers.stackoverflow.com\">Stack Overflow Careers</a></li>\r\n                    \r\n                </ol>\r\n            </td>\r\n    </tr>\r\n</table>\n                </div>\n            </div>\n\n            <div id=\"copyright\">\n                site design / logo &#169; 2016 Stack Exchange Inc; user contributions licensed under <a href=\"https://creativecommons.org/licenses/by-sa/3.0/\" rel=\"license\">cc by-sa 3.0</a> \n                with <a href=\"http://blog.stackoverflow.com/2009/06/attribution-required/\" rel=\"license\">attribution required</a>\n            </div>\n            <div id=\"svnrev\">\n                rev 2016.2.9.3241\n            </div>\n            \n        </div>\n    </div>\n    <noscript>\n        <div id=\"noscript-warning\">Stack Overflow works best with JavaScript enabled<img src=\"http://pixel.quantserve.com/pixel/p-c1rF4kxgLUzNc.gif\" alt=\"\" class=\"dno\"></div>\n    </noscript>\n<scri"], "copyright__copyright__copyright": ["ition into which you're inserting the element and the tail of the list.\n\nIf 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).\n\nshare|improve this answer\n\nYour Answer\n\n\u00a0\ndiscard\n\nBy posting your answer, you agree to the privacy policy and terms of service.\n\nNot the answer you're looking for? Browse other questions tagged or ask your own question."]}