Language:

Remote Training on Programming

For authors:

About project

Hello, Guest! Login or register.

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

Time Limit:	1 seconds
Memory Limit:	16384KB
Points:	5

View Problem Statistics

Submit

Problem added Undefined

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


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

Пример выходных данных:

Примечание:
Сортировка слиянием - алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке. Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи.
Для решения задачи сортировки эти три этапа выглядят так:
1) Сортируемый массив разбивается на две половины примерно одинакового размера;
2) Каждая из получившихся половин сортируется отдельно, например - тем же самым алгоритмом;
3) Два упорядоченных массива половинного размера соединяются в один.
Рекурсивное разбиение задачи на меньшие происходит до тех пор, пока размер массива не достигнет единицы (любой массив длины 1 можно считать упорядоченным).

View Problem Statistics

Submit

Author/source:

Educational Courses /

Data Structures and Algorithms /

Place for problems from students' projects /

587. Сжигая мосты

817.

584. 1 - Триангуляция-2

583. 7 - Определения приращения

We can all benefit by doing occasional "toy" programs, when artificial restrictions are set up, so that we are forced to push our abilities to the limit. The art of tackling miniproblems with all our energy will sharpen our talents for the real problems. Donald E. Knuth.

time generating 0.031 sec.