-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathmerge_sort.py
More file actions
38 lines (32 loc) · 2.72 KB
/
merge_sort.py
File metadata and controls
38 lines (32 loc) · 2.72 KB
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
from random import randint
# Создаём тестовый неотсортированный массив.
arr = []
for i in range(10):
arr.append(randint(1,9))
print(f'Изначальный:\n{arr}\n')
# Сортировка слиянием (Merge sort)
def merge_sort(arr):
# Проверка: Если массив из 1 или 0 элемента - он уже отсортирован
if len(arr) <= 1:
return arr
# 1. Разделение (Divide)
mid = len(arr) // 2 # Делим попалам длинну массива, для нахождения середины
left_half = merge_sort(arr[:mid]) # Левая отсортированная половина, потому что рекурсивно вызывается merge_sort(), который сортирует половину
right_half = merge_sort(arr[mid:]) # Правая отсортированная половина, потому что рекурсивно вызывается merge_sort(), который сортирует половину
# 2. Слияние (Merge)
return merge(left_half, right_half) # Здесь мы обращаемся к функции merge, которая будет соединять эти 2 части
def merge(left, right):
result = [] # Создаём пустой массив для дальнейшего хранения в нём отсортированного списка
i = j = 0 # Задаём указатели для прохождения по элементам, со стартовыми индексами "0"
# Сравниваем элементы из обеих половин по указателям
while i < len(left) and j < len(right): # Проходимся до того момента, пока не закончатся элементы в одной из половин
if left[i] <= right[j]:
result.append(left[i]) # Если Left <= Right - вставляем Left (наименьший элемент).
i += 1 # Идём дальше
else:
result.append(right[j]) # Если Right <= Left - вставляем Right (наименьший элемент).
j += 1 # Идём дальше
result.extend(left[i:]) # Добавляем остаток элементов из Left половины в конец массива (если остались)
result.extend(right[j:]) # Добавляем остаток элементов из Right половины в конец массива (если остались)
return result # Возвращаем результат ( ͡° ͜ʖ ͡°)
print(f'Отсортированный, при помощи Merge Sort:\n{merge_sort(arr)}\n')