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

Saved searches

Use saved searches to filter your results more quickly

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

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

ViktorSalimonov/sorting-algorithms

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

README.md

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

Сортировка пузырьком (Bubble Sort)

Сортировка пузырьком проходит по массиву несколько раз. На каждом этапе алгоритм сравнивает два соседних элемента и, если левый элемент больше правого — меняет их местами. Такой проход гарантирует что самое больше число будет в конце массива. Этот процесс попарного сравнения повторяется до тех пор, пока каждый элемент не будет на своем месте.

def bubble_sort(arr): n = len(arr) for i in range(n): for j in range(n-i-1): if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] return arr

Сортировка выбором (Selection Sort)

Основная идея — рассматривать последовательность как две части: первая включает отсортированные элементы, вторая — неотсортированные. Алгоритм находит наименьшее число из неотсортированной части и помещает его в конец отсортированной.

def selection_sort(arr): n = len(arr) for i in range(n-1): min_index = i for j in range(i+1, n): if arr[j]  arr[min_index]: min_index = j if min_index != i: arr[i], arr[min_index] = arr[min_index], arr[i] return arr

Сортировка вставками (Insertion Sort)

Этот алгоритм совмещает идеи первых двух алгоритмов. Как и в сортировке выбором представляем последовательность как две части: первая включает отсортированные элменты, вторая — неотсортированные. Алгоритм сортировки вставками последовательно помещает каждый элемент из неотсортированной части на правильную позицию отсортированной части.

def insertion_sort(arr): n = len(arr) for i in range(1, n): current_value = arr[i] j = i - 1 while j >= 0: if current_value  arr[j]: arr[j+1] = arr[j] arr[j] = current_value j = j - 1 else: break return arr

Быстрая сортировка (Quick Sort)

Рекурсивный алгоритм, который работает по следующему принципу:

1. Выбрать опорный элемент из массива. Это можно сделать разными способами, в данной реализации этой будет случайный элемент.
2. Сравнить все элементы с опорным и распределить их в подмассивы. Первый подмассив будет состоять из элементов, которые меньше опорного; второй — больше опорного или равные.
3. Рекурсивно выполнить шаги 1 и 2, пока в подмассиве есть хотя бы 2 элемента.

import random def quick_sort(arr): n = len(arr) if n  1: return arr else: pivot = random.choice(arr) less = [x for x in arr if x  pivot] greater_or_equal = [x for x in arr if x >= pivot] return quick_sort(less) + quick_sort(greater_or_equal)

• В худшем случае O(n²)
• В среднем случае O(n * log n)
• В лучшем случае O(n * log n)

Сортировка слиянием (Merge Sort)

Рекурсивный алгоритм, который работает по следующему принципу:

1. Разделить массив на две равные части
2. Отсортировать каждую половину
3. Из двух отсортированных массивов получить один (операция слияния)

def merge_sort(arr): n = len(arr) if n  1: return arr else: middle = int(len(arr) / 2) left = merge_sort(arr[:middle]) right = merge_sort(arr[middle:]) return merge(left, right) def merge(left, right): result = [] while len(left) > 0 and len(right) > 0: if left[0]  right[0]: result.append(left[0]) left = left[1:] else: result.append(right[0]) right = right[1:] if len(left) > 0: result += left if len(right) > 0: result += right return result

• В худшем случае O(n * log n)
• В среднем случае O(n * log n)
• В лучшем случае O(n * log n)

Источник

Сортировка слиянием: для тех, кто не хочет просто использовать .sort()

Задача, старая как мир. Есть список вещей, который нужно отсортировать. Как это сделать?

Ну, самый интуитивный вариант — взять список, разделить его пополам, затем еще пополам и еще, пока у вас не окажется куча списков с длиной, равной единице. После этого нужно выстроить элементы в пары, располагая их в правильном порядке, а затем соединять эти пары вместе, образуя все большие упорядоченные группы, до тех пор, пока не получите целый отсортированный список. Вам тоже именно это сразу в голову пришло?

Ну ладно, может, это действительно не самое интуитивное решение, но мы избавим вас от утомительного прохождения сортировки пузырьком или случайной сортировки (тут впору вздрогнуть) и сразу перейдем к объяснению сортировки слиянием. Единственное, что вам нужно знать, это что сортировка слиянием по сравнению с другими алгоритмами довольно эффективна. Временная сложность этого алгоритма, как вы можете догадаться по подходу «разделим пополам», — O(N log N).

Итак, давайте начнем. Создадим функцию merge_sort() , которая будет принимать список. Для наших целей мы назовем этот список nums (т. е. «числа»), но тот же метод будет работать со списком любых сортируемых типов, например, со списком строк.

Наш первый шаг — разделить список надвое. Мы будем использовать целочисленное деление, чтобы в итоге получить целый индекс (а то вдруг у нас в списке нечетное количество элементов). Затем мы создадим два меньших списка, left и right . Для этого мы используем очень удобную нотацию Python для подсписков.

Погодите, а если длина списка будет 0 или 1? Мы же тогда не сможем разделить его пополам! Чтобы учесть такую возможность, мы обернем весь наш метод в if-предложение. Таким образом весь этот код будет работать только если длина списка больше 1.

def merge_sort(nums): if len(nums) >1: mid = len(nums)//2 left = nums[:mid] right = nums[mid:]

Что мы делаем дальше? Все просто! Мы отсортируем обе половины, вызывая для них merge_sort() .

def merge_sort(nums): if len(nums) >1: mid = len(nums)//2 left = nums[:mid] right = nums[mid:] merge_sort(left) merge_sort(right)

Но погодите, это еще не все. Пока что мы просто последовательно делили наши списки пополам, пока не получили кучу маленьких списков с длиной, равной 1. Например, если бы у нас был список [4, 2, 1, 3] , он был бы разделен на [4, 2] и [1, 3] , а затем на [4] , [2] , [1] и [3] (каждый из этих списков имеет длину, равную 1).

Что дальше? Подсказка кроется в названии алгоритма сортировки. Дальше будет слияние списков.

Здесь нужно быть внимательным. Нам нужно отслеживать три индекса. Назовем их i , j и k . Вот что они будут представлять:

• i — индекс в списке left ,
• j — индекс в списке right ,
• k — индекс в исходном списке nums , в который в конечном итоге нужно вставить все числа по порядку.

Для начала давайте зададим им всем значение 0.

После этого мы будем перебирать и левый, и правый список, сравнивая каждый элемент. Пройти списки необходимо только один раз, потому что left и right уже отсортированы. Нам нужно только соединить их.

Если число из списка left меньше, чем число из списка right , мы вставляем его в nums на позицию k , после чего увеличиваем индекс i на единицу. Если число из списка right меньше или равно числу из списка left , тогда оно отправляется в nums , а мы увеличиваем на единицу индекс j . Наконец, после добавления любого из чисел в список nums , мы увеличиваем на единицу индекс k .

Вот и все! Что касается слияния, мы начали со списков [4] , [2] , [1] и [3] . Эти списки соединились в [2, 4] и [1, 3] , а затем образовали [1, 2, 3, 4] .

Вот наш полный код. Заметьте, что весь метод по сути лежит в самом первом блоке if .

def merge_sort(nums): if len(nums) > 1: mid = len(nums)//2 left = nums[:mid] right = nums[mid:] merge_sort(left) merge_sort(right) i = j = k = 0 while i < len(left) and j < len(right): if left[i] < right[j]: nums[k] = left[i] i+=1 else: nums[k] = right[j] j+=1 k+=1 while i < len(left): nums[k] = left[i] i+=1 k+=1 while j < len(right): nums[k] = right[j] j+=1 k+=1

Проверка

Давайте отсортируем какие-нибудь числа. Создадим список чисел и вызовем для него merge_sort(). Обратите внимание, что мы выводим в результате тот же список nums, потому что наш метод ничего не возвращает, а лишь изменяет исходный список.

nums = [5, 2, 3, 6, 84, 9, 8] merge_sort(nums) print(nums)

В результате вы должны получить отсортированный список — [2, 3, 5, 6, 8, 9, 84] . Как уже говорилось, это сработает и со строками. Если передать этому методу список ['banana', 'apple', 'grape', 'orange'] , он будет отсортирован в алфавитном порядке: ['apple', 'banana', 'grape', 'orange'] .

Метод .sort() в Python работает сходным образом, это тоже алгоритм из серии «разделяй и властвуй», да и временная сложность у него приблизительно такая же. В общем, нет никаких причин, по которым вам стоило бы реализовывать сортировку слиянием… если не вспоминать о технических собеседованиях, конечно. Но теперь-то вы будете готовы к таким заданиям!

Источник

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

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

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

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

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

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

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] 

Источник
Читайте также:  Api error message html