Tutorial sull'algoritmo di ordinamento di unione Python
Scopri come implementare Merge Sort in Python. Un esempio interattivo passo dopo passo della strategia di ordinamento Divide and Conquer.
Panoramica
Merge Sort è un algoritmo di ordinamento altamente efficiente che utilizza una strategia divide et impera. Suddivide un elenco non ordinato in sottoelenchi più piccoli, ordina tali sottoelenchi e quindi li unisce di nuovo insieme.
L'algoritmo divide ricorsivamente l'array a metà finché non raggiunge i sottoarray a elemento singolo. Quindi unisce i sottoarray ordinati confrontando gli elementi di ciascun lato e posizionandoli in ordine. Ciò garantisce una complessità temporale ottimale.
Indipendentemente dal fatto che l'array iniziale sia ordinato, invertito o completamente casuale, Merge Sort viene eseguito in tempo O(n log n). Tuttavia, è necessario O(n) spazio aggiuntivo per contenere le sottoliste durante la fase di fusione.
Codice e output di esecuzione
Un'implementazione ricorsiva standard dell'algoritmo Merge Sort in Python.
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left_half = merge_sort(arr[:mid])
right_half = merge_sort(arr[mid:])
return merge(left_half, right_half)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
# Test dataset
data = [38, 27, 43, 3, 9, 82, 10]
print("Original List:", data)
sorted_data = merge_sort(data)
print("Sorted List: ", sorted_data)Original List: [38, 27, 43, 3, 9, 82, 10]
Sorted List: [3, 9, 10, 27, 38, 43, 82]Implementazione passo dopo passo
- Ordinamento di elenchi collegati in cui la struttura dei nodi facilita la facile fusione senza copiare
- Routine di ordinamento esterne per file che non rientrano completamente nella RAM di sistema
- Applicazioni di ordinamento stabili in cui le chiavi corrispondenti devono preservare l'ordine originale
Domande frequenti
Merge Sort è un algoritmo di ordinamento stabile?
Sì, Merge Sort è stabile. Quando si confrontano elementi identici, l'elemento del sottoarray sinistro (originale per primo) viene posizionato per primo, preservando le loro posizioni relative originali.
Perché Python usa Timsort invece del puro Merge Sort?
`sorted()` integrato di Python utilizza Timsort, che è un algoritmo ibrido che combina Merge Sort e Insertion Sort. Ottimizza i modelli di dati del mondo reale identificando sottosegmenti già ordinati, rendendoli più veloci del puro Merge Sort.
Argomenti correlati
Esplora l'algoritmo Quicksort in Python. Scopri la selezione del pivot, il partizionamento e la ricorsione in questo esempio di codice interattivo.
Algoritmi di ordinamento PythonEsplora gli algoritmi di ordinamento di Python. Visualizza l'ordinamento a bolle e unisci l'ordinamento in modo nativo all'interno del contesto IDE del browser.
Algoritmo di ricerca binaria PythonCerca elenchi ordinati in tempo logaritmico O(log n). Esegui e comprendi la ricerca binaria in Python, inclusa la logica passo passo, i casi limite e le ottimizzazioni.