Implementazioni di algoritmi/Gnome sort

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(n²), e in pratica l'algoritmo svolge il suo compito generalmente in modo più veloce dell'Insertion sort, sebbene dipenda dai dettagli implementativi.

Pseudocodice

 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

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

/*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(n³). 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

Altri progetti

• Wikipedia

• Wikipedia contiene una voce su questo algoritmo