Sorting a subsequence of an array without an additional array

user_13567753 0
Viewed 95

I'm new to programming. I start to learn Ruby freshly and I can't understand how to implement an algorithm for permuting negative(or positive) elements of an array without using an additional array.
For example:
Like this: [-10, 3, -1, 0, -9 ] -> [-10, 3, -9, 0, -1 ] (sort only negatives)
Either that: [-5, 5, -8, 2, 1] -> [-5, 1, -8, 2, 5] (sort only positives)

sorting ruby algorithm
2 Answers
def sort_positives(arr)
  (arr.size-1).times do |i|
    next if arr[i] <= 0
    smallest = i
    (i+1..arr.size-1).each do |j|
      smallest = j if arr[j] > 0 && arr[j] < arr[smallest]
    end
    if smallest > i
      tmp = arr[i]
      arr[i] = arr[smallest]
      arr[smallest] = tmp
    end
  end
  arr
end

arr = [-2, 5, 3, -4, 6, 1, -3]
sort_positives arr
  #=> [-2, 1, 3, -4, 5, 6, -3]
arr
  #=> [-2, 1, 3, -4, 5, 6, -3]

sort_negatives is a straightforward modification to sort_positives.

user_2569700 
def swap(arr, i, j)
  arr[i] = arr[i] ^ arr[j]
  arr[j] = arr[j] ^ arr[i]
  arr[i] = arr[j] ^ arr[i]
end

def sort_negative(arr)
  size = arr.size
  i = 0
  while i < size - 1
    next if arr[i] > 0 # first index of negative number
    next_neg = 0
    min_neg = i
    (i + 1).upto(size - 1) do |j|
      if arr[i] < 0 && arr[j] < 0
        next_neg = j if next_neg == 0
        min_neg = j if arr[min_neg] > arr[j]
      end
    end
    swap(arr, i, min_neg) if min_neg > i
    if next_neg > 0
      i = next_neg # jump to next negative number
    else
      break
    end
  end
end

arr = [-10, 0, 2, 6, 10, -1, 7, 20, 1, 0, -9, 13, 6, 88, -11, -156]
sort_negative(arr)
puts arr.inspect # [-156, 0, 2, 6, 10, -11, 7, 20, 1, 0, -10, 13, 6, 88, -9, -1]
user_122196790
Related