Комбинирование и сортировки 2 массивов

Question

Этот вопрос был задан в другом месте, но я просто хотел проверить, что я сделал это применимо, учитывая RSpec обстоятельства:

Написать метод, который принимает два отсортированных массива и производит отсортированные массив, который объединяет оба.

Ограничения:

• Не называйте сортировать в любом месте.
• Ни в коем случае не изменяйте два массива, данные вам.
• Не обходите (2) путем клонирования или дублирования двух массивов, только для изменения копий.

Подсказка: вам, вероятно, понадобятся индексы в двух массивах.

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

Можете ли вы объединить два массива в один массив, а затем запустить типичный вид пузыря?

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] 

Answer 1

Конечно, вы можете сделать это, но вы с видом на реальный gimmee - два массива вы данные уже будут отсортированы.

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 

Answer 2

Это основано на той же логике, пост Dale M, но в правильном рубина:

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]) 

Answer 3

Взгляните на этот:

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 

Answer 4

Вот вариант, который опирается исключительно на счетчики Ruby. Результат короткий и сладкий.

# 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 

Первый loop держит не хватать минимум двух значений счетчиков, пока один из переписчиков исчерпывает значения. Второй loop затем добавляет все оставшиеся (которые могут быть не равны) значениям из перечислителя первого массива, третий loop делает то же самое для перечислителя второго массива, а tap отсылает результирующий массив.