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

@Defaultinge · Регистрация: 27.02.2019

Студворк — интернет-сервис помощи студентам

Написать функцию, которая принимает на вход любой массив/список и выдает все промежуточные списки, которые получаются в процедуре MergeSort от самого нижнего уровня до отсортированного массива в конце.
Тоесть сначала нужно выдать список, в котором отсортирована каждая пара, затем список, в котором отсортирована каждая четверка, и так далее, пока не дойдем до полностью отсортированного массива.

@Catstail · 27.02.2019, 14:08

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
def mergeArr(a,b):
    la=len(a)
    lb=len(b)
    r=[]
    ia=ib=0
    while(True):
        if (ib>=lb):
            for ja in range(ia,la):
                r+=[a[ja]]
            break
        if (ia>=la):
            for jb in range(ib,lb):
                r+=[b[jb]]
            break
        if (a[ia]>b[ib]):
            r+=[b[ib]]
            ib+=1
        else:
            r+=[a[ia]]
            ia+=1
    return r
    
def mkA(arr):
    r=[]
    for a in arr:
        r+=[[a]]
    return r
    
def mergeSort(arr):
    tmp=mkA(arr)
    while(True):
        res=[]
        print(str(tmp))
        l=len(tmp)
        if l==1:
            return tmp[0]
        i=0
        while (i+1<=l-1):
            res+=[mergeArr(tmp[i],tmp[i+1])]
            i+=2
        if i==l-1:
            res+=[tmp[l-1]]
        tmp=res
 
x=mergeSort([1,2,3,1,2,3,1,2,3,1,2,4,1,2,5])
print(str(x))

Code
1
2
3
4
5
6
[[1], [2], [3], [1], [2], [3], [1], [2], [3], [1], [2], [4], [1], [2], [5]]
[[1, 2], [1, 3], [2, 3], [1, 2], [1, 3], [2, 4], [1, 2], [5]]
[[1, 1, 2, 3], [1, 2, 2, 3], [1, 2, 3, 4], [1, 2, 5]]
[[1, 1, 1, 2, 2, 2, 3, 3], [1, 1, 2, 2, 3, 4, 5]]
[[1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 4, 5]]
[1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 4, 5]

https://ideone.com/xJXNlw

@Dax · 27.02.2019, 14:44

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

Новые блоги и статьи Все статьи Все блоги /
Доступность команды формы по условию Maks 07.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: сделать доступной кнопку (команда формы "ЗавершитьСписание") при. . .	Уведомление о неверно выбранном значении справочника Maks 06.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "НарядПутевка", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если в документе выбран неверный склад. . .	Установка Qt Creator для C и C++: ставим среду, CMake и MinGW без фреймворка Qt 8Observer8 05.04.2026 Среду разработки Qt Creator можно установить без фреймворка Qt. Есть отдельный репозиторий для этой среды: https:/ / github. com/ qt-creator/ qt-creator, где можно скачать установщик, на вкладке Releases:. . .	AkelPad-скрипты, структуры, и немного лирики.. testuser2 05.04.2026 Такая программа, как AkelPad существует уже давно, и также давно существуют скрипты под нее. Тем не менее, прога живет, периодически что-то не спеша дополняется, улучшается. Что меня в первую очередь. . .
Отображение реквизитов в документе по условию и контроль их заполнения Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеСпецтехники", разработанного в конфигурации КА2. Данный документ берёт данные из другого нетипового документа. . .	Фото всей Земли с борта корабля Orion миссии Artemis II kumehtar 04.04.2026 Это первое подобное фото сделанное человеком за 50 лет. Снимок называют новым вариантом легендарной фотографии «The Blue Marble» 1972 года, сделанной с борта корабля «Аполлон-17». Новое фото. . .	Вывод диалогового окна перед закрытием, если документ не проведён Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать программный контроль на предмет проведения документа. . .	Программный контроль заполнения реквизитов табличной части документа Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: 1. Реализовать контроль заполнения реквизита. . .

@Defaultinge 0 / 0 / 0 Регистрация: 27.02.2019 Сообщений: 42

	Сортировка слиянием 27.02.2019, 13:14. Показов 2092. Ответов 2 Метки нет (Все метки) Написать функцию, которая принимает на вход любой массив/список и выдает все промежуточные списки, которые получаются в процедуре MergeSort от самого нижнего уровня до отсортированного массива в конце. Тоесть сначала нужно выдать список, в котором отсортирована каждая пара, затем список, в котором отсортирована каждая четверка, и так далее, пока не дойдем до полностью отсортированного массива. 0

@Dax 1356 / 653 / 207 Регистрация: 23.03.2014 Сообщений: 3,057
	27.02.2019, 14:44
	Сортировка слияниями 0

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

Решение