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?
- L'approccio Divide and Conquer
- Implementazione dell'ordinamento di unione in Python
- Diagramma di flusso per l'implementazione di Merge Sort
- Vantaggi e utilizzo
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]
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 iProduzione:
$ 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 javaDiagramma 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.