Timsort
Questa voce sull'argomento algoritmi è solo un abbozzo.
Contribuisci a migliorarla secondo le convenzioni di Wikipedia.
Timsort | |
---|---|
Rappresentazione grafica del Timsort: per liste brevi come quella del grafico le prestazioni del Timsort sono equivalenti a quelle del insertion sort | |
Classe | Algoritmo di ordinamento |
Struttura dati | Array |
Caso peggiore temporalmente | |
Caso ottimo temporalmente | |
Caso medio temporalmente | |
Caso peggiore spazialmente | |
Ottimale | Sì |
Manuale |
In informatica il Timsort è un algoritmo di ordinamento derivato dal merge sort e dall'insertion sort. La sua struttura è ottimizzata per trattare diversi tipi di dato.
Il suo nome deriva da quello del suo inventore, Tim Peters, che lo ha creato nel 2002 quale algoritmo di ordinamento standard del linguaggio di programmazione Python e di Rust, in cui è stato integrato a partire dalla versione 2.3. È anche utilizzato per ordinare i vettori in Java 7[1].
Note
- ^ jdk7/tl/jdk: changeset 1423:bfd7abda8f79, su hg.openjdk.java.net. URL consultato il 17 maggio 2010 (archiviato dall'url originale il 28 febbraio 2012).
Collegamenti esterni
- (EN) Denis Howe, Timsort, in Free On-line Dictionary of Computing. Disponibile con licenza GFDL
V · D · M | ||
---|---|---|
Teoria | Teoria della complessità computazionale · Notazione O Grande · Array · Lista · Stack · Coda · Ordinamento comparativo · Ordinamento adattivo | |
Algoritmi a scambio | Bubble sort · Shaker sort · Odd-even sort · Comb sort · Gnome sort · Quicksort | |
Algoritmi di selezione | Selection sort · Heap sort · Smoothsort | |
Algoritmi ad inserimento | Insertion sort · Shell sort · Tree sort · Library sort · Patience sorting | |
Algoritmi a fusione | Merge sort · Timsort | |
Algoritmi non comparativi | Radix sort · Bucket sort · Counting sort · Pigeonhole sort | |
Altri algoritmi | Rete di ordinamento · Ordinamento topologico · Ordinamento bitonico · Ordinamento delle frittelle | |
Algoritmi inefficienti | Stupid sort · Trippel sort |
Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica