Rilasciato · in miglioramento
Algorithm
Gli algoritmi di ordinamento mettono in ordine i dati: merge sort, quicksort, heapsort, stabilità, limite inferiore n log n e ordinamenti integrati.
Ordinare significa disporre gli elementi secondo un criterio definito, ad esempio numerico, alfabetico o cronologico. Esistono due grandi famiglie: gli ordinamenti per confronto (bubble sort, insertion sort, selection sort, merge sort, quicksort, heapsort), che chiedono soltanto se un elemento viene prima di un altro, e quelli senza confronti, come counting sort e radix sort, che usano direttamente i valori interi o le loro cifre.
L'ordinamento è il passo preliminare di ricerca binaria, rimozione dei duplicati, unione di intervalli, classifiche e molto altro, per questo è tra i primi algoritmi che si studiano. Conoscere il limite inferiore Ω(n log n) degli ordinamenti per confronto, la differenza tra ordinamento stabile e in loco e il comportamento degli ordinamenti integrati, come Timsort in Python o l'introsort della maggior parte delle implementazioni di std::sort in C++, aiuta a scegliere bene nel lavoro e nei colloqui tecnici.
Per studiarlo conviene seguire a mano insertion sort, merge sort e quicksort su piccoli array, poi implementare merge sort e quicksort e confrontare caso migliore, medio e peggiore. In seguito, esercitati a ordinare con funzioni chiave e comparatori e risolvi problemi basati sull'ordinamento, come l'unione di intervalli o il conteggio delle inversioni.
Merge sort divide l'input a metà e poi fonde le due parti; quicksort partiziona attorno a un pivot. Entrambi richiedono in media O(n log n).
Un ordinamento stabile mantiene l'ordine originale degli elementi con chiavi uguali; uno in loco non usa quasi memoria aggiuntiva. Quale conti di più dipende dal compito.
Un argomento basato sugli alberi di decisione dimostra che ogni ordinamento per confronto richiede, nel caso peggiore, un numero di confronti dell'ordine di n log n. Merge sort e heapsort raggiungono questo limite.
Counting sort e radix sort ordinano interi con intervallo di valori o numero di cifre limitato in tempo quasi lineare, senza confrontare gli elementi tra loro.
merge_sort divide la lista a metà, ordina ricorsivamente ciascuna metà e poi le fonde prendendo sempre il più piccolo dei due elementi in testa. In caso di parità prende prima l'elemento di sinistra (<=), quindi è stabile, e richiede O(n log n) per qualsiasi input. L'ultima riga confronta il risultato con la funzione integrata sorted().
merge_sort.py
def merge_sort(items):
"""Return a new sorted list (stable, O(n log n))."""
if len(items) <= 1:
return list(items)
mid = len(items) // 2
left, right = merge_sort(items[:mid]), merge_sort(items[mid:])
merged, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: # take the left one on ties: stable
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
return merged + left[i:] + right[j:]
if __name__ == "__main__":
data = [38, 27, 43, 3, 9, 82, 10]
print(merge_sort(data)) # [3, 9, 10, 27, 38, 43, 82]
print(merge_sort(data) == sorted(data)) # True
python merge_sort.pySei capitoli che ti accompagnano dall'installazione ai concetti chiave di Ordinamento.
Fai domande, condividi la tua esperienza e scambia opinioni su Ordinamento.
Ancora nessuna discussione. Avvia la prima.
0 commenti
Accedi · Accedi per lasciare un commento.
Scrivi tu il primo commento.