khurum3 / algorithms Goto Github PK

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

В качестве рекурсивного алгоритма "разделяй и властвуй" алгоритм MergeSort оперирует более мелкими массивами. Самый простой способ разложить задачу сортировки на более мелкие - разбить входной массив пополам. Первая и вторая половины сортируются рекурсивно.

Вход: массив(список) A из n разных целых чисел.

Выход: массив(список) с теми же самыми целыми числами, отсортированными от наименьшего к наибольшему.

С - left_partition - рекурсивно отсортировать первую половину A.

D - right_partition - рекурсивно отсортировать вторую половину А. Вернуть Merge(C, D).

1. Сохраняем длину исходного списка в переменной list-length.

def merge_sort(list):
    list_length = len(list)

2. Функция merge_sort возвращает отсортированный список. Список длиной в единицу технически отсортирован; следовательно, список возвращается.

   if list_length == 1:
       return list

3. Для любого списка длиной больше 1 следующим шагом является разделение списка на left_partition и right_partition. Это достигается путем передачи средней точки исходного списка в функцию merge_sort.

   mid_point = list_length // 2

4. Алгоритмы "разделяй и властвуй" рекурсивны. В реализации алгоритма сортировки слиянием рекурсия происходит при разбивке списков. Чтобы убедиться, что все разделы разбиты на их отдельные компоненты, вызывается функция merge_sort, и в качестве параметра передается разделенная часть списка.

   left_partition = merge_sort(list[:mid_point])
   right_partition = merge_sort(list[mid_point:])

5. Функция merge_sort возвращает список, состоящий из отсортированных левого и правого разделов.

   return merge(left_partition, right_partition)

Вторая часть алгоритма сортировки слиянием связана с фактической сортировкой элементов в списке в указанном порядке. В этом случае порядок сортировки элементов в исходном списке возрастающий.

Вход: отсортированные массивы С и D.

Выход: отсортированный массив B.

i = 0

j = 0

for k = 1 to n do

if C[i] < D[j] then
    
    B[k] = C[i]           #заполнить выходной массив
    
    i = i + 1             #прирастить i

else
    
    B[k] = D[j]
    
    j = j + 1

6. Функция слияния принимает в себя два списка и возвращает отсортированный список, состоящий из элементов в двух списках, переданных в качестве параметров функции слияния.

def merge(left, right):

7. Инициализируется пустой список с именем output. Этот список заполняется отсортированными элементами. Кроме того, инициализируются две переменные i и j, которые используются в качестве указателей при переборе списков.

    output = []
    i = j = 0

8. Мы выполняем итерацию обоих списков с помощью цикла while, который выполняется при условии, что оба индекса i и j меньше длины левого и правого списков соответственно.

    while i < len(left) and j < len(right):

9. В теле цикла while сравниваем элементы в каждой позиции обоих списков во время каждой итерации. Искомый список заполняется меньшим значением по текущему индексу списка, в котором находится соответствующий указатель.

         if left[i] < right[j]:
            output.append(left[i])

10. После заполнения output списка необходимо увеличить соответствующий указатель. По сути, мы перемещаем указатель вправо или на следующее значение в списке.

            i += 1
        else:
            output.append(right[j])
            j += 1

11. После завершения цикла while или если условие всего цикла не выполняется, output список заполняется содержимым остатков каждого списка. Оставшиеся элементы выбираются из текущего значения указателя в конец соответствующего списка.

    output.extend(left[i:])
    output.extend(right[j:])

    return output
    
def run_merge_sort():
    unsorted_list = [4, 1, 5, 7, 2, 6, 1, 1, 6, 4, 10, 33, 5, 7, 23]
    print(unsorted_list)
    sorted_list = merge_sort(unsorted_list)
    print(sorted_list)


run_merge_sort()

Сортировка слиянием, по сравнению с другими алгоритмами сортировки, обычно выполняется быстрее на больших наборах данных. Это связано с тем, что сортировка слиянием занимает меньшее количество шагов для сортировки списка. Большинство других алгоритмов сортировки, таких как InsertionSort и BubbleSort , должны выполнять много шагов для сортировки списка. Например, сортировка списка, содержащего 40 элементов, займет 1600 шагов (40*40) с использованием алгоритма сортировки вставкой, но при сортировке слиянием для сортировки списка потребуется примерно 64 шага.