Merge lists 2 [ Python 3 ]

5.0/5 оценка (2 голосов)

Сортировка последовательностей чисел.

def quick_merge(list1, list2):
    result = []

    p1 = 0  # указатель на первый элемент списка list1
    p2 = 0  # указатель на первый элемент списка list2

    while p1 < len(list1) and p2 < len(list2):  # пока не закончился хотя бы один список
        if list1[p1] <= list2[p2]:
            result.append(list1[p1])
            p1 += 1
        else:
            result.append(list2[p2])
            p2 += 1

    if p1 < len(list1):   # прицепление остатка
        result += list1[p1:]
    if p2 < len(list2):
        result += list2[p2:]
    
    return result

# Заводим новый пустой список, в котором будет окончательный результат
result_list = []

# Указываем количество списков, которые нужно отсортировать в единый список.
# Например, если задать цифру 5, то программа будет запрашивать 5 последовательностей цифр, для создания 5-ти списков.
for i in range(int(input())):
    num = [int(ii) for ii in input().split()]  # Вводим отсортированные списки, которые нужно завести в единый список. 

    result_list = quick_merge(result_list, num)

# Передаем в функцию сначала пустой список и первый введеный. Сравниваем "два списка". 
# После первого сравнения результат сохраниться в пустой список result_list. 
# Далее будут сортироваться сохраненный список "result_list" и новый список, введенный пользователем.

# выводим результат
print(*result_list)

Описание функции (quick_merge)

Пусть мы имеем два уже отсортированных по возрастанию списка list1 и list2.

Алгоритм быстрого слияния следующий:

1. Создаем численные указатели p1 = 0 и p2 = 0 на начала обоих списков list1 и list2 соответственно;
2. На каждом шаге берем меньший из двух элементов list1[p1] и list2[p2];
3. Записываем его в результирующий список; 
4. Увеличиваем указатель на первый элемент списка (p1 или p2) из которого был взят элемент на $1$;
5. Когда один из начальных списков закончился, добавляем все оставшиеся элементы второго списка в результирующий список.