February 1
Con dozzine di algoritmi di ordinamento disponibili, determinare quale funziona meglio con il sistema dipenderà confronti di diversi fattori, come la dimensione della lista, la velocità o la complessità dell'algoritmo, e se si utilizzerà una chiave per ordinare.
La complessità di un algoritmo di ordinamento viene misurata da O (n), o "ordine di n", dove n è la dimensione della lista. Esso misura quanti passaggi ci vuole per ordinare l'elenco e calcola la sua migliore, peggiore e medio tempo per farlo. complessità comuni includono n come un caso migliore per i tipi, come insertion sort e shell sort, n log n, (con un logaritmo in base 2, non è una base-10), che è la complessità per merge sort e heapsort, e n², che è più lenta della prima volta e è la velocità per selezione.
A volte si sa come sono organizzati gli elementi non ordinati in un elenco: Per esempio, se sono quasi ordinati, in ordine inverso, o un elenco con alcuni oggetti unici. Tale conoscenza aiuta a selezionare un algoritmo efficiente per risolvere la. Ad esempio, utilizzando insertion sort per ordinare un elenco in ordine inverso ha un tempo di esecuzione di n², mentre heap sort può farlo più velocemente, n log n tempo. In un elenco che è quasi allineati, insertion sort è più veloce di heap sort. Quando l'elenco contiene una serie completamente randomizzato di dati, selezionare un algoritmo con un caso di complessità media di n log n tempo di esecuzione, come il mucchio sorta, quicksort o merge sort.
Alcuni algoritmi sono più difficili da usare rispetto ad altri, in modo che il numero di elementi di una lista ed ogni quanto tempo è necessario per ordinare può aiutare a determinare l'algoritmo si sceglierà. Sorta come insertion sort sono veloci e lavorare bene durante l'ordinamento liste più piccole, e sono facili da implementare, ma sono lento con liste più grandi. Tipi che utilizzano un algoritmo divide et impera, come quicksort e merge sort sono più difficili da attuare, ma loro liste specie più grandi più rapidamente nei casi medi.
stabilità Algoritmo descrive se il genere mantiene l'ordine degli elementi in base a una chiave di ordinamento. Ad esempio, utilizzando il primo carattere come chiave per una lista che ha "John", "Steve" e "Jim" in questo ordine, un algoritmo stabile ordina l'elenco di "John", "Jim" e "Steve", mentre un algoritmo instabile può o non può ordinare "Jim" prima "John". Merge sort, insertion sort e bubble sort sono tutti gli algoritmi stabili mentre Shell sort, selection sort e heap sort non lo sono.