algorithm
Ordinamento
Ricerca…
Parametri
| Parametro | Descrizione |
|---|---|
| Stabilità | Un algoritmo di ordinamento è stabile se conserva l'ordine relativo di elementi uguali dopo l'ordinamento. |
| A posto | Un algoritmo di ordinamento è sul posto se ordina utilizzando solo O(1) memoria ausiliaria (senza contare l'array che deve essere ordinato). |
| La migliore complessità del caso | Un algoritmo di ordinamento ha una complessità del caso migliore di O(T(n)) se il suo tempo di esecuzione è almeno T(n) per tutti i possibili input. |
| Complessità del caso medio | Un algoritmo di ordinamento ha una complessità temporale di caso medio di O(T(n)) se il suo tempo di esecuzione, mediato su tutti i possibili input , è T(n) . |
| Peggiore complessità del caso | Un algoritmo di ordinamento ha una complessità temporale di caso peggiore di O(T(n)) se il suo tempo di esecuzione è al massimo T(n) . |
Stabilità nell'ordinamento
Stabilità nell'ordinamento indica se un algoritmo di ordinamento mantiene l'ordine relativo delle chiavi uguali dell'ingresso originale nell'output del risultato.
Quindi un algoritmo di ordinamento si dice che sia stabile se due oggetti con chiavi uguali appaiono nello stesso ordine nell'output ordinato come appaiono nell'array non ordinato di input.
Considera una lista di coppie:
(1, 2) (9, 7) (3, 4) (8, 6) (9, 3)
Ora ordineremo la lista usando il primo elemento di ogni coppia.
Un ordinamento stabile di questa lista produrrà la seguente lista:
(1, 2) (3, 4) (8, 6) (9, 7) (9, 3)
Perché (9, 3) appare dopo (9, 7) nell'elenco originale.
Un ordinamento instabile produrrà la seguente lista:
(1, 2) (3, 4) (8, 6) (9, 3) (9, 7)
L'ordinamento instabile può generare lo stesso risultato dell'ordinamento stabile ma non sempre.
Tipi stabili ben noti:
Tipi instabili noti: