Gnome sort
Da Wikipedia, l'enciclopedia libera.
Gnome sort è un algoritmo di ordinamento simile all'insertion sort con la differenza che il muovere un elemento alla sua corretta posizione è accompagnato da una serie di scambi, come nel bubble sort. Il nome ricalca il classico comportamento degli gnomi nell'ordinare.
E' concettualmente semplice, non richiede cicli annidati. Il costo computazionale è O(n2), e in pratica l'algoritmo svolge il suo compito generalmente in modo più veloce dell'Insertion sort, sebbene dipenda dai dettagli implementativi.
[modifica] Pseudocodice
function gnomeSort(a[0..size-1]) { i := 1 j := 2 while i ≤ size - 1 if a[i-1] ≤ a[i] i := j j := j + 1 else swap a[i-1] and a[i] i := i - 1 if i = 0 i := 1 }
[modifica] Altri progetti
- Wikibooks contiene implementazioni di Gnome sort
[modifica] Collegamenti esterni
Algoritmi di ordinamento | ||
---|---|---|
Teoria | Teoria della complessità computazionale | Notazione O Grande | Lista | Stack | Coda | |
Algoritmi a scambio | Bubble sort | Cocktail sort | Comb sort | Gnome sort | Quicksort | |
Algoritmi di selezione | Selection sort | Heapsort | Smoothsort | |
Algoritmi ad inserimento | Insertion sort | Shell sort | Tree sort | Library sort | Patience sorting | |
Algoritmi a fusione | Merge sort | |
Algoritmi non comparativi | Radix sort | Bucket sort | Counting sort | Pigeonhole sort | |
Altri algoritmi | Stupid sort |