CODEWITHSUNDEEP
rubyarrays
Jgoo83
Jgoo83

Reputation: 377

Combine and sort 2 arrays

This question was asked somewhere else, but I just wanted to check if what I did was applicable given the rspec circumstances:

Write a method that takes two sorted arrays and produces the sorted array that combines both.

Restrictions:

Hint: you will probably need indices into the two arrays.

combine_arrays([1, 3, 5], [2, 4, 6]) == [1, 2, 3, 4, 5, 6]

Can you just combine the two arrays into a single array and then run a typical bubble sort?

def combine_arrays(arr1,arr2)
  final = arr1 + arr2
  sorted = true
  while sorted do
    sorted = false
    (0..final.length - 2).each do |x|
      if final[x] > final[x+1]
        final[x], final[x+1] = final[x+1], final[x]
        sorted = true
      end
    end
  end
  final
end

p combine_arrays([1,3,5],[2,4,6]) => [1, 2, 3, 4, 5, 6]

Upvotes: 2

Views: 966

Answers (4)

pjs
pjs

Reputation: 19853

Here is a variant which relies solely on Ruby's enumerators. The result is short and sweet.

# merge two sorted arrays into a sorted combined array
def merge(a1, a2)
  [].tap do |combined|
    e1, e2 = a1.each, a2.each
    # The following three loops terminate appropriately because
    #    StopIteration acts as a break for Kernel#loop.
    # First, keep appending smaller element until one of
    #    the enumerators run out of data
    loop { combined << (e1.peek <= e2.peek ? e1 : e2).next }
    # At this point, one of these enumerators is "empty" and will
    #    break immediately. The other appends all remaining data.
    loop { combined << e1.next }
    loop { combined << e2.next }
  end
end

The first loop keeps grabbing the minimum of the two enumerator values until one of the enumerators runs out of values. The second loop then appends all remaining (which may be none) values from the first array's enumerator, the third loop does the same for the second array's enumerator, and tap hands back the resulting array.

Upvotes: 2

Alex
Alex

Reputation: 533

Take a look at this one:

def merge(arr1, arr2)
  arr2.each { |n| arr1 = insert_into_place(arr1, n) }
  arr1.empty? ? arr2 : arr1
end

def insert_into_place(array, number)
  return [] if array.empty?
  group = array.group_by { |n| n >= number }
  bigger = group[true]
  smaller = group[false]
  if bigger.nil?
    number > smaller.last ? smaller << number : smaller.unshift(number)
  else
    (smaller << number) + bigger
  end
end

Upvotes: 0

Max Hollmann
Max Hollmann

Reputation: 345

This is based on the same logic as Dale M's post, but in proper ruby:

def combine_arrays(arr1,arr2)
  [].tap do |out|
    i1 = i2 = 0
    while i1 < arr1.size || i2 < arr2.size
      v1 = arr1[i1]
      v2 = arr2[i2]
      if v1 && (!v2 || v1 < v2)
        out << v1
        i1 += 1
      else
        out << v2
        i2 += 1
      end
    end
  end
end

combine_arrays([1,3,5], [2,4,6])

Upvotes: 0

Dale M
Dale M

Reputation: 2473

Sure, you can do that but you are overlooking a real gimmee - the two arrays you are given will already be sorted.

def combine_arrays(A1, A2)
    retVal = Array.CreateInstance(System::Int32, A1.Length + A2.Length - 1)
    i = 0
    j = 0
    while i < A1.Length | j < A2.Length
        if i < A1.Length and self.A1(i) < self.A2(j) then
            self.retVal(i + j) = self.A1(i)
            i += 1
        else
            self.retVal(i + j) = self.A2(j)
            j += 1
        end
    end
    return retVal
end

Upvotes: 0

Related Questions