АВТ
Язык:

Дистанционный практикум по программированию

Задачи On-line статус ЧаВо Турниры
Для авторов:
Регистрация  ||  Вход
Рейтинг авторов
 
О системе
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

817. Сортировка слиянием

Ограничение времени: 1 секунды
Ограничение памяти:16384КБ
Баллы:5
Статистика Послать на проверку Задачу добавил Неизвестный
Дана сортировка слиянием.

MergeSort(list,first,last)
list сортируемый список элементов
first номер первого элемента в сортируемой части списка
last номер последнего элемента в сортируемой части списка

if (first < last) then
middle=(first+last)/2
MergeSort(list,first,middle)
MergeSort(list,middle+l,last)

MergeLists(list,first,middle,middle+l,last)
end if
Выписать состояние исходного списка после каждого слияния функцией MergeLists.

Входные данные:
в первой строке: n - количество элементов исходного списка, где 2<=n<=1000.
в следующей строке записан список, элементы которого перечислены через пробел.

Выходные данные:
в первой строке: количество сформированных списков.
в последующих строчках вывести состояние исходного списка после каждого вызова функции MergeLists.
Элементы разделять пробелами.

Пример входных данных:
5
5 4 2 3 1
Пример выходных данных:
4
4 5 2 3 1
2 4 5 3 1
2 4 5 1 3
1 2 3 4 5

Примечание:
Сортировка слиянием - алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке. Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи.
Для решения задачи сортировки эти три этапа выглядят так:
1) Сортируемый массив разбивается на две половины примерно одинакового размера;
2) Каждая из получившихся половин сортируется отдельно, например - тем же самым алгоритмом;
3) Два упорядоченных массива половинного размера соединяются в один.
Рекурсивное разбиение задачи на меньшие происходит до тех пор, пока размер массива не достигнет единицы (любой массив длины 1 можно считать упорядоченным).
Статистика Послать на проверку Автор/источник:
Учебные курсы / Структуры и алгоритмы / Сюда помещаем задачи из курсовиков! /
587. Сжигая мосты 817. 584. 1 - Триангуляция-2 583. 7 - Определения приращения
 
время генерации 0.078 сек.
© Copyright ВоГТУ, АВТ, Носов Д.А.