Heapsort
Organizza la lista in uno heap, un albero in cui ogni genitore è più grande dei suoi figli. Poi sposta il valore più grande alla fine, ancora e ancora.
- Ω(n log n)
- Θ(n log n)
- O(n log n)
- O(1)
- no
- sì
Caso migliore: come cresce il tempo con la dimensione n della lista quando l'input è il più facile per questo algoritmo.
Caso medio: crescita tipica del tempo con n. Con n², raddoppiare il numero di valori quadruplica circa il tempo; n log n cresce molto meno.
Caso peggiore: la crescita sull'input più difficile. Utile quando la velocità non deve mai calare.
Spazio: quanta memoria extra serve oltre alla lista. 1 vuol dire poche variabili, n una copia della lista.
Stabile: due valori uguali mantengono il loro ordine originale. Conta quando si ordinano record in base a un solo campo.
Sul posto: ordina dentro la lista stessa, senza una seconda lista.
- confronto
- spostamento
- al suo posto finale
Prova così: Scegli una lista invertita. Costruire lo heap non richiede quasi scambi, poi a ogni giro il valore più grande va in fondo.
Come funziona
Lo heap sta dentro la lista stessa: il valore nella posizione numero i ha i suoi figli nelle posizioni 2i+1 e 2i+2, e il valore più grande è sempre all'inizio. Lo si scambia con l'ultimo valore, si riduce lo heap di uno e lo si ripara. La parte ordinata cresce da destra.
Quando conviene usarlo
Quando serve una velocità che resti buona anche nel caso peggiore, senza memoria extra, per esempio su piccoli dispositivi. In media è più lento del quicksort, quindi spesso si usa come rete di sicurezza.