#11. Слияние двух упорядоченных списков | Алгоритмы на Python

Спасибо, Сергей!

Всегда интересно.

Учусь программированию пока по этому каналу для того, чтобы потом брать какие-либо заказы на фрилансе. У меня вопрос, достаточно ли того, что предлагает здесь автор на своём канале, чтобы выполнять какие-либо маленькие заказы? Потому что я не знаю, какие именно нужны практические знания для этого. может быть посоветуете хороший курс? желательно по с++.

Какая сложность алгоритма?

а если нужно получить массив по возрастанию из двух массивов по убыванию

Спасибо, все подробно разжевываете!

Возможно будет ещё быстрее если переносить не по 1 числу, а кусками. Т.е например 2,7,8 и 1,3,4,5,6,9 тут числа 3,4,5,6 можно перенести одной командой. Но нужно искать такие куски.

Спасибо за понятное объяснение.

блин
я через попу нулевых элементов реализовывал
хотя через указатели мне кажется более программистским подходом
спасибо, Сергей, за науку!

Благодарю за подробное объяснение! 👍

спасибо огромное за объяснение. Все доступным языком без усложнений

Я не понимаю, а как программа знает о том, что счетчик i принадлежит первому списку, а счетчик j ко второму списку?

Спасибо большое за то, что показали как можно ещё реализовать данный алгоритм!

Спасибо огромное. Отличная подача материала!

Если программу запустить 2 раза, то к предыдущему выводу добавится еще один такой же список. И так можно делать до бесконечности. То есть сначала ответом был список: с. Запустили еще раза прогу: на выводе уже две "с". Сколько раз запускаешь прогу столько списков "с" и будет.

Удивительно, но факт. Формирование такого списка намного (на порядок или чуть больше) дольше, чем конкатенация (или расширение) двух списков, а затем их сортировка с помощью метода списков sort() или встроенной функции sorted().
Причина в механике метода append().
Для С++ такая сортировка, наверное, годится, но для Python - неоптимальное решение.

result = []
while a and b:
result.append(a.pop(0) if a[0] < b[0] else b.pop(0))
result.extend(a if len(a) >0 else b)

Если сразу добавлять оба равных элемента в список, то это будет меньше итераций.
И если в списках много одинаковых элементов, то выигрыш будет существенный.

while i < N and j < M:
if a[i] == b[j]:
c.append(a[i])
c.append(b[j])
i += 1
j += 1
elif a[i] < b[j]:
c.append(a[i])
i += 1
elif a[i] > b[j]:
c.append(b[j])
j += 1