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]
Rephinescarol45, +27655765355 SSD MONEY CLEANING CHEMICAL +27655765355 BLACK MONEY IN JOHANNESBURG, OMAN, SAUDI ARABIA, SUDAN, Somalia ,Zimbabwe Botswana at 247quickbookshelp
I am Carol From San Diego USA, I am Working as a Personal assistant in a Castle Realty organization, I ...
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