Как да приложим Merge Sort в Python?



Ето един лесен и лесен урок, за да научите как да използвате Merge Sort и да научите за неговия алгоритъм и изпълнение в Python

Този блог се основава на подхода „разделяй и владей“. Merge Sort е алгоритъм „разделяй и владей“, при който проблемът е разделен на подпроблеми и след това се обединява, за да завладее решението. Този блог в Merge Sort in ще ви преведе подробно през долните теми -

Какво е Merge Sort в Python?

Merge Sort се основава на алгоритъма за разделяне и завладяване, където входният масив е разделен на две половини, след това сортиран поотделно и обединен обратно, за да достигне до решението. Функцията merge () се използва за обединяване на сортираното .





Подходът „Разделяй и владей“

  • Масивът се разделя наполовина и процесът се повтаря с всяка половина, докато всяка половина е с размер 1 или 0.
  • Масивът с размер 1 е тривиално сортиран.
  • Сега двата сортирани масива се комбинират в един голям масив. И това продължава, докато всички елементи се комбинират и масивът се сортира.

Ето визуализация на сортиране на сливане, за да изчистите картината вместо вас

Входен масив = [3,1,4,1,5,9,2,6,5,4]



предпоставки за научаване на машинно обучение

Сливане на сортиране | Блогове на Edureka | Едурека
Сега да преминем към изпълнението.

Внедряване на Merge Sort в Python

def mergeSort (nlist): print ('Splitting', nlist) if len (nlist)> 1: mid = len (nlist) // 2 lefthalf = nlist [: mid] righthalf = nlist [mid:] mergeSort (lefthalf) mergeSort (вдясно) i = j = k = 0, докато i

Изход:

$ python main.py
(„Разделяне“, [3, 1, 4, 1, 5, 9, 2, 6, 5, 4])
(„Разделяне“, [3, 1, 4, 1, 5])
(„Разделяне“, [3, 1])
(„Разделяне“, [3])
(„Обединяване“, [3])
(„Разделяне“, [1])
(„Обединяване“, [1])
(„Обединяване“, [1, 3])
(„Разделяне“, [4, 1, 5])
(„Разделяне“, [4])
(„Обединяване“, [4])
(„Разделяне“, [1, 5])
(„Разделяне“, [1])
(„Обединяване“, [1])
(„Разделяне“, [5])
(„Обединяване“, [5])
(„Обединяване“, [1, 5])
(„Обединяване“, [1, 4, 5])
(„Обединяване“, [1, 1, 3, 4, 5])
(„Разделяне“, [9, 2, 6, 5, 4])
(„Разделяне“, [9, 2])
(„Разделяне“, [9])
(„Обединяване“, [9])
(„Разделяне“, [2])
(„Обединяване“, [2])
(„Обединяване“, [2, 9])
(„Разделяне“, [6, 5, 4])
(„Разделяне“, [6])
(„Обединяване“, [6])
(„Разделяне“, [5, 4])
(„Разделяне“, [5])
(„Обединяване“, [5])
(„Разделяне“, [4])
(„Обединяване“, [4])
(„Обединяване“, [4, 5])
(„Обединяване“, [4, 5, 6])
(„Обединяване“, [2, 4, 5, 6, 9])
(„Обединяване“, [1, 1, 2, 3, 4, 4, 5, 5, 6, 9])
[1, 1, 2, 3, 4, 4, 5, 5, 6, 9]



пример за извикване на отдалечен метод

Блок-схема за прилагане на Сливане на сортиране

Предимства и използване на сортиране на обединяване

Повечето от другите алгоритми се представят лошо с последователни структури от данни като файлове и свързани списъци. В тези структури достъпът до случаен елемент отнема линейно време, а не редовно постоянно време. А естеството на сортирането на сливанията го прави лесно и бързо за такива структури от данни.Една от най-добрите характеристики на сортирането на сливанията е неговият малък брой сравнения. Това прави O (n * log (n)) брой сравнения, но постоянният коефициент е добър в сравнение с бързата сортировка, което го прави полезен, когато функцията за сравнение е бавна операция.Също така подходът „разделяй и владей“ при сортиране на сливания го прави удобен за паралелна обработка.

С това стигнахме до края на този блог на тема „Как да приложим Merge Sort в Python“. Надявам се, че съдържанието добави някаква стойност към вашите познания в Python. За да получите задълбочени познания за Python заедно с различните му приложения, можете да се регистрирате за живо с 24/7 поддръжка и доживотен достъп.