# 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

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]
``````