Does this algorithm take up too much extra space to be "in place"?

fdan Source

The assignment is to sort negative and positive numbers from a vector. The catch is that the algorithm must be O(n) and in place.
My "solution" is:

def Rearrange(arr):
    neg = []
    pos = []
    for x in arr:
        if x < 0:
            neg.append(x)
        else:
            pos.append(x)
    return neg + pos

So, what I'm wondering is if this algorithm is in place or not? I know that the loop and append operations satisfy an in place algorithm. But what about the list that stores the values? Does it use too much extra space to satisfy an in place algorithm? If it does, is there an easy fix to this problem that's apparent? Right now I'm kind of stuck.

pythonpython-3.xalgorithmsorting

Answers

answered 5 months ago jpp #1

No. This solution is not in place. Two new objects (lists) are created, which you continually appended to according to the logic you have specified.

As far as I am aware, you cannot get an in-place view of your data using only the standard library.

If an in place solution is important to you, you can use a 3rd party library such as numpy.

If an O(n) solution is important, you should use a generator or list.append in a for loop to 2 lists.

answered 5 months ago zipa #2

You cannot change the variable inplace but you can achieve O(n) with this:

def rearrange(arr):
    result = []
    for i in arr:
        if i < 0:
            result.insert(0, i)
        else:
            result.append(i)
    return result

EDIT

Following the @Chris_Rands proposal this solution using deque seems to be the fastest:

from collections import deque

def rearrange2(arr):
    result = deque()
    for i in arr:
        if i < 0:
            result.appendleft(i)
        else:
            result.append(i)
    return result

Roughly 28% faster than the accepted solution according to %timeit results.

%timeit rearrange_accepted(nums)
100 loops, best of 3: 12.2 ms per loop

%timeit rearrange2(nums)
100 loops, best of 3: 8.84 ms per loop

answered 5 months ago carrdelling #3

Do you need to sort the whole array, or just have negative values on the left and positive values (and 0) on the right?

If what you want to achieve is this second thing, then the following function should work (it works in place and it is O(n)):

def rearrange(array):

    left = 0
    right = len(array) - 1

    while left < right:
        if array[left] >= 0 > array[right]:
            array[right], array[left] = array[left], array[right]
            left += 1
            right -= 1
        elif array[left] < 0:
            left += 1
        else:
            right -= 1

>>> array = [-5, 6, 7, -4, 2, 0, -1]
>>> rearrange(array)
>>> array 
[-5, -1, -4, 7, 2, 0, 6]

comments powered by Disqus