Come implementare Merge Sort in Python?



Ecco un tutorial semplice e facile per imparare a utilizzare Merge Sort e conoscere il suo algoritmo e l'implementazione in Python

Questo blog si basa sull'approccio divide et impera. Merge Sort è un algoritmo di 'divide et impera' in cui il problema è suddiviso in sottoproblemi e viene quindi unito per conquistare la soluzione. Questo blog su Merge Sort in ti guiderà attraverso i seguenti argomenti in dettaglio -

Cos'è l'ordinamento di unione in Python?

Merge Sort si basa sull'algoritmo divide et impera in cui l'array di input è diviso in due metà, quindi ordinato separatamente e ricongiunto per raggiungere la soluzione. La funzione merge () viene utilizzata per unire i file ordinati .





L'approccio Divide and Conquer

  • La matrice viene divisa a metà e il processo viene ripetuto con ciascuna metà fino a quando ciascuna metà è di dimensione 1 o 0.
  • L'array di dimensione 1 è ordinato in modo banale.
  • Ora i due array ordinati vengono combinati in un unico grande array. E questo viene continuato fino a quando tutti gli elementi vengono combinati e l'array viene ordinato.

Ecco una visualizzazione di merge sort per cancellare l'immagine per te

come utilizzare i parametri in tableau

Array di input = [3,1,4,1,5,9,2,6,5,4]



Unisci ordinamento | Blog di Edureka | Edureka
Passiamo ora all'implementazione.

Implementazione dell'ordinamento di unione in Python

def mergeSort (nlist): print ('Splitting', nlist) if len (nlist)> 1: mid = len (nlist) // 2 lefthalf = nlist [: mid] righthalf = nlist [mid:] mergeSort (lefthalf) mergeSort (metà destra) i = j = k = 0 mentre i

Produzione:

$ python main.py
('Divisione', [3, 1, 4, 1, 5, 9, 2, 6, 5, 4])
('Divisione', [3, 1, 4, 1, 5])
('Divisione', [3, 1])
('Divisione', [3])
('Fusione', [3])
('Divisione', [1])
('Unione', [1])
('Fusione', [1, 3])
('Divisione', [4, 1, 5])
('Divisione', [4])
('Fusione', [4])
('Divisione', [1, 5])
('Divisione', [1])
('Unione', [1])
('Divisione', [5])
('Fusione', [5])
('Fusione', [1, 5])
('Merging', [1, 4, 5])
('Merging', [1, 1, 3, 4, 5])
('Divisione', [9, 2, 6, 5, 4])
('Divisione', [9, 2])
('Divisione', [9])
('Fusione', [9])
('Divisione', [2])
('Fusione', [2])
('Fusione', [2, 9])
('Divisione', [6, 5, 4])
('Divisione', [6])
('Fusione', [6])
('Divisione', [5, 4])
('Divisione', [5])
('Fusione', [5])
('Divisione', [4])
('Fusione', [4])
('Fusione', [4, 5])
('Merging', [4, 5, 6])
('Merging', [2, 4, 5, 6, 9])
('Unione', [1, 1, 2, 3, 4, 4, 5, 5, 6, 9])
[1, 1, 2, 3, 4, 4, 5, 5, 6, 9]



tipi di commenti in java

Diagramma di flusso per l'implementazione di Merge Sort

Vantaggi e utilizzo di Merge Sort

La maggior parte degli altri algoritmi funziona male con strutture di dati sequenziali come file ed elenchi collegati. In queste strutture l'accesso a un elemento casuale richiede tempo lineare, non tempo costante regolare. E la natura del merge sort lo rende facile e veloce per tali strutture di dati.Una delle migliori caratteristiche del merge sort è il suo basso numero di confronti. Rende O (n * log (n)) il numero di confronti, ma il fattore costante è buono rispetto al quicksort, il che lo rende utile quando la funzione di confronto è un'operazione lenta.Inoltre, l'approccio divide et impera del merge sort lo rende conveniente per l'elaborazione parallela.

Con questo, arriviamo alla fine di questo blog su 'Come implementare Merge Sort in Python'. Spero che il contenuto abbia aggiunto valore alla tua conoscenza in Python. Per ottenere una conoscenza approfondita di Python e delle sue varie applicazioni, puoi iscriverti a live con supporto 24 ore su 24, 7 giorni su 7 e accesso a vita.