Gnome sort

Gnome sort
Ordinamento di una sequenza numerica con lo Gnome sort
Classe	Algoritmo di ordinamento
Struttura dati	Array
Caso peggiore temporalmente	$O(n^{2})$
Caso ottimo temporalmente	$O(n)$
Caso medio temporalmente	$O(n^{2})$
Caso peggiore spazialmente	$O(1)$ ausiliario
Ottimale	No

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(n²), ma tende verso O(n) se la lista iniziale è parzialmente ordinata. In pratica l'algoritmo può risultare veloce quanto l'Insertion sort.

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

Ecco 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

Data 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

Lo 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

Originariamente proposto con il nome di Stupid Sort da Hamid Sarbazi-Azad 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:

«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»

(Dick Grune)

Altri progetti

Altri progetti

• Wikibooks

• Wikibooks contiene implementazioni dello Gnome sort

Collegamenti esterni

• Gnome sort, su cs.vu.nl.