будет ли эта часть кода выполняться при сортировке слиянием?

Алгоритм сортировки слиянием

Шаг 1 — если это только один элемент в списке, он уже отсортирован, возврат. Шаг 2 — рекурсивно разделите список на две половины, пока его больше нельзя будет разделить. Шаг 3 — объедините меньшие списки в новый список в отсортированном порядке.

с этим псевдокодом:

procedure mergesort( var a as array )
   if ( n == 1 ) return a

   var l1 as array = a[0] ... a[n/2]
   var l2 as array = a[n/2+1] ... a[n]

   l1 = mergesort( l1 )
   l2 = mergesort( l2 )

   return merge( l1, l2 )
end procedure

procedure merge( var a as array, var b as array )

   var c as array

   while ( a and b have elements )
      if ( a[0] > b[0] )
         add b[0] to the end of c
         remove b[0] from b
      else
         add a[0] to the end of c
         remove a[0] from a
      end if
   end while

   while ( a has elements )
      add a[0] to the end of c
      remove a[0] from a
   end while

   while ( b has elements )
      add b[0] to the end of c
      remove b[0] from b
   end while

   return c

end procedure

мой вопрос:

в функции merge есть два цикла while для проверки наличия элементов в a и b и добавления их в массив c.

мой вопрос: будут ли (могут ли) эти два пока выполняться в одной и той же функции?

или например, если a все еще есть элементы, это означает, что b определенно пусто, и наоборот?


person Ania David    schedule 16.04.2016    source источник
comment
ребята почему вы меня минусуете?   -  person Ania David    schedule 16.04.2016


Ответы (1)


Нет. Если бы оба они все еще не были пустыми, то первое условие while было бы истинным.

После завершения первого while хотя бы одно из a, b пусто.

person aviad    schedule 16.04.2016