Implementazioni di algoritmi/Gnome sort

Indice del libro


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