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

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

Python предоставляет модульную библиотеку предварительно созданных алгоритмов, которая позволяет пользователям выполнять различные операции, которые могут помочь им выполнить свою задачу сами по себе или служить шагом на пути к достижению более крупной и сложной цели. Одним из наиболее популярных таких алгоритмов является тот, который включает функциональность сортировки слиянием.

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

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

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

Ознакомьтесь с другими нашими курсами по науке о данных на upGrad.

Техника «разделяй и властвуй»

Возьмем, к примеру, случайный набор букв алфавита: N, H, V, B, Q, D, Z, R.

Шаг 1. Исходный набор данных сначала разбивается на две группы следующим образом:

Н, Ч, В, Б В , Д, З, Р

Шаг 2 : Оба результирующих массива подразделяются следующим образом:

Н, Х В, Б К, Д З, Р

Шаг 3 : Наконец, все четыре массива подвергаются дальнейшей обработке до тех пор, пока весь ряд данных не будет разбит на отдельные компоненты:

N H V B Q D Z R

Затем процесс меняется на противоположный, и теперь отдельные точки данных начинают поэтапно объединяться. Но в ходе этого процесса слияния каждый элемент в каждом подмассиве оценивается и заменяется местами, чтобы они сортировались в логической последовательности (в алфавитном порядке) следующим образом:

Шаг 4 : Отдельные элементы объединяются в пары, меняя местами, как требуется, чтобы сформировать правильную последовательность:

H, N B, V D, Q R, Z

Шаг 5 : Рекурсивный процесс слияния и сортировки продолжается до следующей итерации:

Б, Ч, Н, В Г, В, Р, Я

Шаг 6 : Весь ряд данных окончательно восстанавливается в логическом алфавитном порядке:

Б, Г, Ч, Н, В, Р, В, Я

Изучите наши популярные курсы по науке о данных

Реализации сортировки слиянием

Существует два подхода к реализации сортировки слиянием в Python. Подход «сверху вниз» и подход «снизу вверх».

Нисходящий подход:

Наиболее часто используемый подход «сверху вниз» описан выше. Это занимает больше времени и использует больше памяти, поэтому неэффективно при работе с небольшими наборами данных. Однако он намного надежнее, особенно применительно к большим наборам данных.

Читайте наши популярные статьи о науке о данных

Введите код:

def merge_sort (inp_arr):

размер = длина (inp_arr)

если размер > 1:

средний = размер // 2

left_arr = inp_arr (: среднее)

rIght_arr = inp_arr (посередине:)

merge_sort(left_arr)

слияние _sort (right_arr)

я = 0

j = 0

к = 0

(Где i и j — итераторы для обхода левой и правой половин ряда данных соответственно, а k — итератор всего ряда данных).

левый_размер = длина (левый_арр)

правый _size = длина (правый_арр)

в то время как я <left_size и j <правый размер:

если левая_обработка(i) < правая_обработка(j):

inp_arr (к) – left_arr (я)

я >= 1

еще:

inp_arr (k) = right_arr (j)

j += 1

к += 1

пока я <left_size:

inp_arr (k) = left_arr (i)

я += 1

к += 1

в то время как j < right_size:

inp_arr (k) = right_arr (j)

j += 1

к += 1

inp_arr = (N, H, V, B, Q, D, Z, R)

print(:Входной массив:\n”)

печать (inp_arr)

merge_sort (inp_arr)

print("Отсортированный массив:\n")

печать (inp_arr)

Вывод:

Входной массив: N, H, V, B, Q, D, Z, R

Выходной массив: B, D, H, N, Q, R, V, Z

Подход «снизу вверх:

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

Введите код:

деф слияние (слева, справа):

результат = [] х, у = 0, 0

для k в диапазоне (0, len (слева) + len (справа)):

if i == len(left): # если в конце 1-го тайма,

result.append(right[j]) # добавляем все значения второй половины

j += 1

elif j == len(right): # если в конце второй половины,

result.append(left[x]) # добавить все значения 1-й половины

я += 1

Элиф вправо[j] < влево[i]:

результат.добавлять(справа[j])

j += 1

еще:

результат.append(слева[i])

я += 1

вернуть результат

сортировка слиянием (ar_list):

длина = длина (ar_list)

размер = 1

в то время как размер <длина:

size+=size # инициализируется равным 2, как описано

для позиции в диапазоне (0, длина, размер):

начало = поз.

середина = позиция + интервал (размер / 2)

конец = позиция + размер

слева = ar_list[начало: середина] справа = ar_list[середина: конец]

ar_list[начало:конец] = объединить (слева, справа)

вернуть ar_list

ar_list = [N, H, V, B, Q, D, Z, R] печать (сортировка слиянием (ar_list))

Вывод:

Входной массив: N, H, V, B, Q, D, Z, R

Выходной массив: B, D, H, N, Q, R, V, Z

Реализация сортировки слиянием применяется к более сложным наборам данных из реальной жизни.

Давайте применим нисходящий подход к четырем случайным внедорожникам в Индии:

Введите код:

Класс Автомобиль:

def __init__(я, марка, модель, цена):

селф.бренд = бренд

self.model = модель

собственная цена = цена

защита __str __(я):

return str.format("Бренд: {}, Модель: {}, Цена: {}", self.brand,

сел.модель, сел.цена)

def слияние (list1, i, j, k, comp_fun):

левая_копия = список1[i:k + 1]

r_sublist = список1[k+1:r+1]

левая_копия_индекс = 0

j_sublist_index = 0

отсортированный_индекс = я

в то время как left_copy_index < len(left_copy) иj_sublist_index <

Лен(j_sublist):

если comp_fun(left_copy[left_copy_index], j_sublist[j_sublist_index]):

list1[sorted_index] = левая_копия[left_copy_index]

левый_индекс_копии = левый_индекс_копии + 1

еще :

список1[отсортированный_индекс] = j_подсписок[j_подсписок_индекс]

j_sublist_index = j_sublist_index + 1

отсортированный_индекс = отсортированный_индекс + 1

в то время как left_copy_index < len(left_copy):

list1[sorted_index] = левая_копия[left_copy_index]

левый_индекс_копии = левый_индекс_копии + 1

отсортированный_индекс = отсортированный_индекс + 1

в то время как j_sublist_index < len(j_sublist):

список1[отсортированный_индекс] = j_подсписок[j_подсписок_индекс]

j_sublist_index = j_sublist_index + 1

отсортированный_индекс = отсортированный_индекс + 1

def merge_sort (list1, i, j, comp_fun):

если я >= j:

возвращаться

k = (i + j)//2

merge_sort (list1, i, k, comp_fun)

merge_sort (список1, k + 1, j, comp_fun)

слияние (список1, я, j, k, comp_fun)

car1 = Автомобиль («Джип», «Рэнглер», 0,58)

car2 = Автомобиль («Форд», «Индевор», 0,35)

car3 = Автомобиль («Ягуар Ленд Ровер», «Рейндж Ровер Спорт», 1.76)

car4 = Автомобиль("Мерседес-Бенц", "G-класс", 2.42)

список1 = [машина1, машина2, машина3, машина4]

merge_sort(list1, 0, len(list1) -1, lambda carA, carB: carA.brand < carB.brand)

print («Автомобили отсортированы по маркам:»)

для автомобиля всписке1:

печать (автомобиль)

распечатать ()

merge_sort(list1, 0, len(list1) -1, lambda carA, carB: carA.price< carB.price)

print ("Автомобили отсортированы по цене:")

для автомобиля всписке1:

печать (автомобиль)

Вывод:

Автомобили отсортированы по маркам:

Форд Индевор

Ягуар Ленд Ровер Рендж Ровер Спорт

Джип Вранглер

Мерседес Бенц G-класса

Автомобили отсортированы по цене:

Форд Индевор

Джип Вранглер

Ягуар Ленд Ровер Рендж Ровер

Мерседес Бенц G-класса

Вы можете изучить как теоретические, так и практические аспекты Python с профессиональным сертификатом upGrad в области науки о данных и бизнес-аналитики Университета Мэриленда. Этот курс поможет вам изучить Python с нуля. Даже если вы новичок в программировании и кодировании, upGrad предложит вам двухнедельный подготовительный курс, чтобы вы могли освоить основы программирования. вы узнаете о различных инструментах, таких как Python, SQL, работая над несколькими отраслевыми проектами.

Планируйте свою карьеру в области разработки программного обеспечения прямо сейчас!

Подать заявку на профессиональную программу сертификации в области науки о данных и бизнес-аналитики