sarasaurus
BAN USERThe idea here is when we encounter a positive number in the slot we're examining, we find the next negative number, store it in a temp variable, then shuffle over all the positives. Finally, insert the saved negative number into the current slot.
i.e. if we had: [ 1, <1>, 2, 3, 4, 2, ..]
When we encounter the 1, we search forward til we find the index of the 2, and we store that value. We then copy between our current index and that index:
[ 1, <1>, 1, 2, 3, 4, ....]
Then finally insert the saved number into our current location.
[1, <2>, 1, 2, 3, 4, ...]
Then we move onto examining the next index.
<strike>This is O(n) in the worst case, because in [3,2,1,3,2,1], we perform n/2 shuffles, where each shuffle swaps at most n/2 elements. n/2 * n/2 = O(n).</strike>
It's actually O(n^2), thanks for the correction lxduan.
def find_next_negative(i, arr):
while i < len(arr):
if arr[i] < 0:
return i
i = i + 1
return None
def sort_relative(arr):
next_negative_index = None
for current_index in xrange(0, len(arr)):
if arr[current_index] < 0:
pass
else:
# find next negative
next_negative_index = find_next_negative(current_index+1, arr)
if next_negative_index:
# copy it to this location, and bump everything up
value_to_copy = arr[next_negative_index]
copy_index = next_negative_index  1
while copy_index >= current_index:
arr[copy_index+1] = arr[copy_index]
copy_index = 1
arr[current_index] = value_to_copy
else:
break
return arr
print sort_relative([3,2,1,1]) == [1, 3, 2, 1]
print sort_relative([11, 1, 3, 2, 5, 2]) == [2, 5, 11, 1, 3, 2]
print sort_relative([3,2,1,3,2,1]) == [3,2,1,3,2,1]

sarasaurus
August 24, 2013 Open Chat in New Window
Yep you're right. It's O(n) if you store an extra array with all the indices of negative numbers, but then that's O(n) space. My bad.
 sarasaurus August 25, 2013