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
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
If an O(n) solution is important, you should use a generator or
list.append in a
for loop to 2 lists.
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
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
28% faster than the accepted solution according to
%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
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]