Implementazioni di algoritmi/Gnome sort

Wikibooks, manuali e libri di testo liberi.
CopertinaImplementazioni di algoritmi/Copertina


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.

È 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.

Pseudocodice[modifica]

 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
 }


Algoritmo in C[modifica]

void GnomeSort (int *Array,int Dimensione)
{
   int i,j;
 
   i = 1;
   j = 2;
 
   while ( i < Dimensione  )
   {
      if ( Array[i-1] <= Array[i] )
      {
         i = j;
         j++;
      }
      else
      {
         Swap(& Array[i-1], & Array[i] ); // funzione Swap non definita in questo listato
         if ( i > 1 )
             i--;
      }
   }
}

Algoritmo in JAVA[modifica]

/*Ordinamento fatto partendo da una schiera di valori alfanumerici (Es. Argomenti della classe)*/
static void GnomeSort (String[] schiera)
		{
		   int i = 0, j = 1;
 
		   int s_length = schiera.length -1;
 
		   while ( i < s_length )
		   {
		      if (schiera[i].compareTo(schiera[i+1]) < 0)
		      {
		         i = j;
		         j++;
		      }
		      else
		      {
		    	  String temp_s = schiera[i+1];
			      schiera[i+1] = schiera[i];
			      schiera[i] = temp_s;
 
		         if ( i > 0 )
		             i--;
		      }
		   }
		}

L'algoritmo cerca i primi due elementi in ordine non corretto e li scambia. Se questo posto non venisse cercato efficientemente, il risultato sarebbe addirittura O(n3). Tuttavia, effettuare uno scambio può solo introdurre una nuova coppia adiacente non ordinata, posizionata esattamente prima dei due elementi ordinati. Per questo il codice decrementa i subito dopo lo scambio.

Altri progetti[modifica]