🔍 Как сделать сортировку слиянием на питоне? Простое руководство!

Сортировка слиянием - это алгоритм сортировки, который разбивает список на меньшие части, сортирует их отдельно, а затем объединяет в один отсортированный список. Вот пример реализации на Python:

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left_half = merge_sort(arr[:mid])
    right_half = merge_sort(arr[mid:])
    
    return merge(left_half, right_half)

def merge(left, right):
    result = []
    i = j = 0
    
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    result.extend(left[i:])
    result.extend(right[j:])
    
    return result

# Пример использования
data = [5, 2, 9, 1, 7]
sorted_data = merge_sort(data)
print(sorted_data)
    

Как сделать сортировку слиянием на питоне

Добро пожаловать в мир сортировки слиянием на языке программирования Python! В этой статье мы рассмотрим, как реализовать алгоритм сортировки слиянием и как он работает.

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

Сортировка слиянием - это эффективный алгоритм сортировки, основанный на принципе "разделяй и властвуй". Он работает следующим образом:

1. Разделяем исходный массив на две равные по размеру части.
2. Рекурсивно сортируем каждую половину массива.
3. Объединяем отсортированные половины в один новый массив.

Алгоритм продолжает разделять и соединять массивы до тех пор, пока не будет достигнута конечная сортировка. Это происходит благодаря тому, что разделение массива происходит до тех пор, пока не останется только один элемент, а затем происходит объединение соседних элементов в отсортированные массивы.

Пример реализации на Python

Давайте теперь рассмотрим пример кода на языке Python, который иллюстрирует, как реализовать сортировку слиянием.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left_half = arr[:mid]
    right_half = arr[mid:]
    
    left_half = merge_sort(left_half)
    right_half = merge_sort(right_half)
    
    return merge(left_half, right_half)

def merge(left, right):
    merged = []
    i = 0
    j = 0
    
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    
    while i < len(left):
        merged.append(left[i])
        i += 1
    
    while j < len(right):
        merged.append(right[j])
        j += 1
    
    return merged

arr = [8, 3, 1, 5, 6, 2, 7, 4]
sorted_arr = merge_sort(arr)
print("Отсортированный массив:", sorted_arr)
	

В этом примере функция `merge_sort` принимает массив `arr` в качестве входных данных и рекурсивно разделяет его на две половины. Затем она вызывает себя для сортировки каждой половины и объединяет результаты, используя функцию `merge`.

Функция `merge` сравнивает элементы из двух половин и добавляет их в результирующий массив. Затем она проверяет, остались ли еще элементы в одной из половин, и добавляет их в конец результирующего массива.

Наконец, мы создаем массив `arr` с неотсортированными значениями и передаем его в функцию `merge_sort`. Результат сортировки выводится на экран.

Заключение

Сортировка слиянием - это один из наиболее эффективных алгоритмов сортировки на языке Python. Его простая реализация и высокая скорость работы делают его отличным выбором для сортировки больших объемов данных.

Мы рассмотрели, что такое сортировка слиянием и как ее реализовать на языке Python. Код примера поможет вам лучше понять работу этого алгоритма и применить его в ваших собственных проектах.

Надеюсь, теперь вы лучше понимаете, как сделать сортировку слиянием на питоне! Успехов в программировании!