Алгоритм сортировки слиянием на Python

https://t.me/data_analysis_ml


Программа будет сортировать список методом слияния (Merge Sort).

Алгоритм сортировки слиянием на Python

Суть сортировки

  1. Сортируемый массив разбивается на две части примерно одинакового размера.
  2. Каждая из получившихся частей сортируется отдельно, например, тем же самым алгоритмом.
  3. Два упорядоченных массива половинного размера соединяются в один.

Сложность сортировки по времени

  1. Худшая O(n log n)
  2. Средняя O(n log n)
  3. Лучшая O(n log n)

Шаги к правильному решению

  1. Создадим функцию merge_sort, которая принимает на вход список и 2 переменные: start и end.
  2. Функция merge_sort будет сортировать список от start до end-1 индексов.
  3. Если end-start не больше 1, выходим.
  4. Иначе, устанавливаем mid = (start+end)//2 (округляет до меньшего 15//2=7)
  5. Вызываем merge_sort(alist, start, mid).
  6. Вызываем merge_sort(alist, mid, end).
  7. Вызываем merge_list(alist, start, mid, end).
  8. Функция принимает список и 3 параметра, полагает, что список отсортирован от start до mid-1 и от mid до end-1, смерживает их и образует новый сортированный список от start до end-1.
def merge_sort(alist, start, end):
    '''Sorts the list from indexes start to end - 1 inclusive.'''
    if end - start > 1:
        mid = (start + end)//2
        merge_sort(alist, start, mid)
        merge_sort(alist, mid, end)
        merge_list(alist, start, mid, end)
 
def merge_list(alist, start, mid, end):
    left = alist[start:mid]
    right = alist[mid:end]
    k = start
    i = 0
    j = 0
    while (start + i < mid and mid + j < end):
        if (left[i] <= right[j]):
            alist[k] = left[i]
            i = i + 1
        else:
            alist[k] = right[j]
            j = j + 1
        k = k + 1
    if start + i < mid:
        while k < end:
            alist[k] = left[i]
            i = i + 1
            k = k + 1
    else:
        while k < end:
            alist[k] = right[j]
            j = j + 1
            k = k + 1
 
 
alist = input('Enter the list of numbers: ').split()
alist = [int(x) for x in alist]
merge_sort(alist, 0, len(alist))
print('Sorted list: ', end='')
print(alist)

источник

+1
0
+1
0
+1
0
+1
0
+1
0

Ответить

Ваш адрес email не будет опубликован. Обязательные поля помечены *