Implementazioni di algoritmi/Gnome sort: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Nessun oggetto della modifica |
|||
Riga 18:
i := 1
}
== Algoritmo in C ==
<source lang="C">
void GnomeSort (int *Array,int Dimensione)
{
int i,j;
i = 1;
j = 2;
while ( i <= Dimensione - 1 )
{
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--;}
}
}
}
</source>
Effettivamente, l'algoritmo trova sempre il primo posto dove ci sono due elementi in ordine non corretto, e li scambia. Se questo posto non venisse cercato efficientemente, il risultato sarebbe addirittura O(n<sup>3</sup>). Invece, Ci si avvantaggia del fatto che l'effettuare uno scambio può solo introdurre una nuova coppia adiacente non ordinata prima dei due elementi ordinati, e si potrà cercare questa coppia immediatamente dopo lo scambio.
| |||