Gnome sort

algortimo di ordinamento

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
Ordinamento di una sequenza numerica con lo Gnome sort
ClasseAlgoritmo di ordinamento
Struttura datiArray
Caso peggiore temporalmente
Caso ottimo temporalmente
Caso medio temporalmente
Caso peggiore spazialmente ausiliario
OttimaleNo

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

modifica

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

modifica

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

modifica

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

modifica

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

  1. ^ 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.
  2. ^ Dick Grune, Gnome sort, su dickgrune.com. URL consultato il 9 marzo 2012.

Altri progetti

modifica

Collegamenti esterni

modifica
  Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica