Gnome sort
In informatica lo Gnome sort (soprannominato stupid sort) è un algoritmo di ordinamento molto simile all'insertion sort da cui, però, differisce per il fatto che lo spostamento di un elemento nella sua posizione corretta è eseguito mediante una serie di scambi, come nel Bubble sort. Lo Gnome sort è molto semplice e non richiede cicli nidificati. Il tempo di esecuzione è O(n2), ma tende verso O(n) se la lista iniziale è parzialmente ordinata[1]. In pratica l'algoritmo può risultare veloce quanto l'Insertion sort.
Gnome sort | |
---|---|
Classe | Algoritmo di ordinamento |
Struttura dati | Array |
Caso peggiore temporalmente | |
Caso ottimo temporalmente | |
Caso medio temporalmente | |
Caso peggiore spazialmente | ausiliario |
Ottimale | No |
Lo Gnome sort trova sempre la prima posizione in cui 2 elementi adiacenti sono in ordine errato e li scambia. L'algoritmo si avvantaggia del fatto che l'esecuzione di uno scambio può disordinare una coppia ordinata di elementi adiacenti solo appena dopo o appena prima i due elementi scambiati. Lo Gnome sort non controlla che gli elementi posti dopo la posizione corrente siano ordinati per cui necessita soltanto di controllare la posizione immediatamente precedente gli elementi scambiati.
Pseudocodice
modificaEcco una implementazione in pseudocodice dello Gnome sort:
procedure gnomeSort( a : lista di elementi da ordinare) pos ← 0 while pos < length(a) if ( pos = 0 ) or ( a[pos] >= a[pos - 1] ) then pos ← pos + 1 else swap ( a[pos], a[pos - 1] ) pos ← pos - 1
Esempio
modificaData una lista non ordinata a composta dagli elementi [5, 3, 2, 4], lo Gnome sort dovrebbe eseguire, durante il ciclo, i seguenti passaggi (la "posizione corrente" è segnata in grassetto):
Lista corrente | Azione da eseguire |
---|---|
[5, 3, 2, 4] | pos = 0, incrementa pos: |
[5, 3, 2, 4] | a[pos] < a[pos-1], scambia e decrementa pos: |
[3, 5, 2, 4] | pos = 0, incrementa pos: |
[3, 5, 2, 4] | a[pos] > a[pos-1], incrementa pos: |
[3, 5, 2, 4] | a[pos] < a[pos-1], scambia e decrementa pos: |
[3, 2, 5, 4] | a[pos] < a[pos-1], scambia e decrementa pos: |
[2, 3, 5, 4] | pos = 0, incrementa pos: |
[2, 3, 5, 4] | a[pos] > a[pos-1], incrementa pos: |
[2, 3, 5, 4] | a[pos] > a[pos-1], incrementa pos: |
[2, 3, 5, 4] | a[pos] < a[pos-1], scambia e decrementa pos: |
[2, 3, 4, 5] | a[pos] > a[pos-1], incrementa pos: |
[2, 3, 4, 5] | a[pos] > a[pos-1], incrementa pos: |
[2, 3, 4, 5] | pos = lunghezza(a), finito. |
Ottimizzazioni
modificaLo Gnome sort può essere ottimizzato introducendo una variabile in cui memorizzare la posizione corrente prima di iniziare a scorrere all'indietro la lista fino al suo inizio. Essa permetterà allo "gnomo" di ritrovare la sua posizione precedente dopo lo spostamento di un vaso da fiori. Con questa modifica lo Gnome sort diventa una variante dell'Insertion sort.
procedure gnomeSort( A : lista di elementi da ordinare) i ← 1 j ← 2 while i <= length(a) - 1 if a[i - 1] <= a[i] then i ←j j ← j + 1 else swap ( a[i - 1] , a[i] ) i ← i - 1 if i = 0 i ← 1
Il nome
modificaOriginariamente proposto con il nome di Stupid Sort da Hamid Sarbazi-Azad[1] fu successivamente ripreso da Dick Grune e presentato con il nome di Gnome sort. Il suo nome deriva dal supposto modo con cui gli gnomi da giardino ordinano una fila di vasi da fiori[2]:
«Lo Gnome sort è basato sulla tecnica utilizzata dagli gnomi da giardino olandesi (o tuinkabouter). Ecco come uno gnomo da giardino ordina una fila di vasi da fiori. In pratica egli guarda il vaso da fiori che lo segue e quello che lo precede: se sono nella giusta posizione, egli avanza di un vaso altrimenti li scambia e torna indietro di un vaso. Condizione limite: se non c'è un vaso prima di lui, egli allora si sposta in avanti; se non c'è un vaso dopo di lui, allora ha finito»
Note
modifica- ^ a b Paul E. Black, gnome sort, in Dictionary of Algorithms and Data Structures, U.S. National Institute of Standards and Technology. URL consultato il 9 marzo 2012.
- ^ Dick Grune, Gnome sort, su dickgrune.com. URL consultato il 9 marzo 2012.
Altri progetti
modificaWikibooks contiene implementazioni dello Gnome sort
Collegamenti esterni
modifica- Gnome sort, su cs.vu.nl.