May 31
Ordinamento di un elenco è un'operazione software importante. Trovare qualcosa in un elenco non ordinato significa, in media, di andare a metà strada attraverso la lista. Trovare qualcosa in un elenco ordinato prende, al massimo, il logaritmo in base due del lunghezza della lista. Per esempio, ci si potrebbe aspettare di guardare 500.000 le cose per trovare ciò che si desidera in una lista non ordinata di un milione di cose. Se fossero ordinati ci si potrebbe aspettare di guardare circa 20 le cose.
L'efficienza degli algoritmi - compresi algoritmi di ordinamento - sono spesso espresse in "notazione O-grande." Questo O è scritto (N ^ 2) e si pronuncia "ordine N al quadrato." La notazione descrive cosa accade quando la "dimensione" del problema cresce. Se si tratta di O (N ^ 2), quindi il tempo cresce come il quadrato della dimensione - il numero di cose da ordinare. Se ci vogliono tre secondi per ordinare un milione di articoli, ci vorranno 12 secondi per ordinare due milioni di pezzi. La dimensione raddoppiata e il tempo prende 2 ^ 2 = 4 volte più a lungo.
Una molto semplice, facile da programmare sorta richiederebbe un altro elenco vuoto la stessa dimensione della lista di interi che si desidera ordinare. Passare attraverso l'array di interi volta, cercando il più piccolo intero. Quando lo trovate, contrassegnare come "preso" e metterlo in all'inizio della lista vuota. Farlo di nuovo, trovando il più piccolo intero non godute e metterlo nel prossimo slot disponibile nella lista ordinata. Ripetere questo ultimo passo fino a quando tutto è contrassegnato come presa. Questo algoritmo di ordinamento è O (N ^ 2) e adatto solo per piccole liste. Esso "Non scala bene", così è proibitivo lento per elenchi di grandi dimensioni.
L'ondulazione tipo o bubble sort è chiamato per il modo in cui gli oggetti rimanere nella stessa lista, mentre da ordinare. Si tratta di un grande favorito con i programmatori perché consente di risparmiare spazio ed è estremamente facile da scrivere ed eseguire il debug. Nel caso peggiore è O (N ^ 2), ma nel caso migliore è O (N). Nel caso medio è O (N log N), che è quanto di meglio si possa. Passare attraverso la lista guardando coppie di numeri interi, e passare loro se sono fuori uso. Continuare a fare questo fino a quando la lista è ordinata.
Ci sono una varietà di specie - come merge sort e quick sort - che il lavoro a O (N log N) tempo, ma sono difficili da scrivere e spesso eseguire peggio di bubble sort su liste brevi. Questi algoritmi devono essere considerati solo quando enormi liste sono spesso ordinate. Se è possibile utilizzare specifiche sui dati per aiutare con il tipo, a volte è possibile ottenere l'ordine fino a O (N), ma che è il limite teorico assoluto. In generale, il tempo umano è più prezioso di tempo al computer ed è una buona idea per mantenere il codice più semplice possibile.