Структуры данных и алгоритмы Python: сортировка слиянием

Поиск и сортировка Python: упражнение 8 с решением

Напишите программу Python для сортировки списка элементов с использованием алгоритма сортировки слиянием.
Примечание. Согласно Википедии «Сортировка слиянием (также обычно обозначается как сортировка слиянием) — это алгоритм сортировки на основе сравнения O (n log n). Большинство реализаций производят стабильную сортировку, что означает, что реализация сохраняет порядок ввода равных элементов в отсортированном выводе».

Алгоритм:

Концептуально сортировка слиянием работает следующим образом:

  • Разделите несортированный список на n подсписок, каждый содержащий 1 элемент (список из 1 элемента считается отсортированным).
  • Неоднократно объединяйте подсписки для создания новых отсортированных подсписок, пока не останется только 1 подсписок. Это будет отсортированный список.

Пример сортировки слиянием:

Сортировка слиянием: графическое представление

Пример решения :

Код Python:

  def mergeSort (nlist): print ("Разделение", nlist) if len (nlist)> 1: mid = len (nlist)//2 lefthalf = nlist [  : mid] righthalf = nlist [mid:] mergeSort (lefthalf) mergeSort (righthalf) i = j = k = 0 while i  

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

 Разделение [14, 46, 43, 27, 57, 41, 45, 21, 70] Разделение [14, 46, 43, 27] Разделение [14, 46] Разделение [14] Слияние [14] Разделение [46]  ------- Объединение [14, 21, 27, 41, 43, 45, 46, 57, 70] [14, 21, 27, 41, 43, 45, 46, 57, 70] 

Блок-схема:

Визуализируйте выполнение кода Python:

Следующий инструмент визуализирует, что делает компьютер. шаг за шагом по мере выполнения указанной программы:

Редактор кода Python:

Оцените статью
nanomode.ru
Добавить комментарий