Gnome sort

Da Wikipedia, l'enciclopedia libera.
Gnome sort
Sorting gnomesort anim.gif
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 ?
Caso peggiore spazialmente O(1) ausiliario
Ottimale No

In informatica lo Gnome 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 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.

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 | modifica sorgente]

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 | modifica sorgente]

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 | modifica sorgente]

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 <= lenght(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

Curiosità[modifica | modifica sorgente]

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 »
(Dick Grune)

Note[modifica | modifica sorgente]

  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. URL consultato il 09/03/2012.

Altri progetti[modifica | modifica sorgente]

Collegamenti esterni[modifica | modifica sorgente]