Ako implementovať Merge Sort v Pythone?



Tu je jednoduchý a ľahký návod, ktorý sa dozviete, ako používať zlúčenie zoradenia, a dozviete sa viac o jeho algoritme a implementácii v jazyku Python.

Tento blog je založený na prístupe rozdeľuj a panuj. Merge Sort je algoritmus „rozdeľuj a panuj“, kde je problém rozdelený na podproblémy a potom je zlúčený, aby sa podmanilo riešenie. Tento blog o zlúčení Zoradiť vás podrobne prevedie nižšie uvedenými témami -

Čo je zlúčenie zoradenia v Pythone?

Zlúčenie zoradenia je založené na algoritme rozdelenia a dobývania, kde je vstupné pole rozdelené na dve polovice, potom je zoradené osobitne a zlúčené späť, aby sa dosiahlo riešenie. Na zlúčenie zoradených sa používa funkcia merge () .





Prístup Rozdeľuj a panuj

  • Pole je rozdelené na polovicu a proces sa opakuje s každou polovicou, kým každá polovica nemá veľkosť 1 alebo 0.
  • Pole veľkosti 1 je triviálne zoradené.
  • Teraz sú dve zoradené polia spojené do jedného veľkého poľa. A toto pokračuje, kým sa všetky prvky nespoja a pole sa nezoradí.

Tu je vizualizácia zlúčenia, ktorá vám pomôže vytvoriť lepší obraz

Vstupné pole = [3,1,4,1,5,9,2,6,5,4]



hybridný framework v selenovom webdriveri

Zlúčiť triedenie | Blogy Edureka | Edureka
Prejdime teraz k implementácii.

Implementácia zlúčeného zoradenia v Pythone

def mergeSort (nlist): print ('Splitting', nlist) if len (nlist)> 1: mid = len (nlist) // 2 lefthalf = nlist [: mid] righthalf = nlist [mid:] mergeSort (lefthalf) mergeSort (pravý) i = j = k = 0, zatiaľ čo i

Výkon:

$ python main.py
(„Rozdelenie“, [3, 1, 4, 1, 5, 9, 2, 6, 5, 4])
(„Rozdelenie“, [3, 1, 4, 1, 5])
(„Rozdelenie“, [3, 1])
(„Rozdelenie“, [3])
(„Zlúčenie“, [3])
(„Rozdelenie“, [1])
(„Zlúčenie“, [1])
(„Zlúčenie“, [1, 3])
(„Rozdelenie“, [4, 1, 5])
(„Rozdelenie“, [4])
(„Zlúčenie“, [4])
(„Rozdelenie“, [1, 5])
(„Rozdelenie“, [1])
(„Zlúčenie“, [1])
(„Rozdelenie“, [5])
(„Zlúčenie“, [5])
(„Zlúčenie“, [1, 5])
(„Zlúčenie“, [1, 4, 5])
(„Zlúčenie“, [1, 1, 3, 4, 5])
(„Rozdelenie“, [9, 2, 6, 5, 4])
(„Rozdelenie“, [9, 2])
(„Rozdelenie“, [9])
(„Zlúčenie“, [9])
(„Rozdelenie“, [2])
(„Zlúčenie“, [2])
(„Zlúčenie“, [2, 9])
(„Rozdelenie“, [6, 5, 4])
(„Rozdelenie“, [6])
(„Zlúčenie“, [6])
(„Rozdelenie“, [5, 4])
(„Rozdelenie“, [5])
(„Zlúčenie“, [5])
(„Rozdelenie“, [4])
(„Zlúčenie“, [4])
(„Zlúčenie“, [4, 5])
(„Zlúčenie“, [4, 5, 6])
(„Zlúčenie“, [2, 4, 5, 6, 9])
(„Zlúčenie“, [1, 1, 2, 3, 4, 4, 5, 5, 6, 9])
[1, 1, 2, 3, 4, 4, 5, 5, 6, 9]



ako používať triedenie v c ++

Vývojový diagram implementácie Merge Sort

Výhody a použitie zlúčenia zoradiť

Väčšina ostatných algoritmov nefunguje dobre so sekvenčnými dátovými štruktúrami, ako sú súbory a prepojené zoznamy. V týchto štruktúrach prístup k náhodnému prvku trvá lineárny čas, nie pravidelný konštantný čas. A povaha typu zlúčenia umožňuje také a rýchle dátové štruktúry.Jednou z najlepších vlastností zlúčenia je nízky počet porovnaní. Robí O (n * log (n)) počet porovnaní, ale konštantný faktor je v porovnaní s quicksortom dobrý, čo je užitočné, keď je funkcia porovnania pomalá operácia.Prístup rozdelenia a dobývania tiež zlučovacieho triedenia umožňuje pohodlné paralelné spracovanie.

Týmto sa dostávame na koniec tohto blogu o tom, „Ako implementovať Merge Sort v Pythone“. Dúfam, že obsah dodal vašim znalostiam v Pythone určitú hodnotu. Ak chcete získať podrobné informácie o Pythone a jeho rôznych aplikáciách, môžete sa zaregistrovať naživo s nepretržitou podporou a doživotným prístupom.