Implementazioni di algoritmi/Gnome sort: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m 11 revisioni importate da w:Gnome sort |
link a pedia, template indice e interprogetto |
||
Riga 1:
{{algoritmi}}
'''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 [[gnomo|gnomi]] nell'ordinare.▼
▲'''Gnome sort''' è un [[w:algoritmo di ordinamento|algoritmo di ordinamento]] simile all'[[w:insertion sort|insertion sort]] con la differenza che il muovere un elemento alla sua corretta posizione è accompagnato da una serie di scambi, come nel [[w:bubble sort|bubble sort]]. Il nome ricalca il classico comportamento degli [[w:gnomo|gnomi]] nell'ordinare.
E' concettualmente semplice, non richiede cicli annidati. Il costo computazionale è [[O-grande|O]](''n''<sup>2</sup>), e in pratica l'algoritmo svolge il suo compito generalmente in modo più veloce dell'[[Insertion sort]], sebbene dipenda dai dettagli implementativi.▼
▲E' concettualmente semplice, non richiede cicli annidati. Il costo computazionale è [[w:O-grande|O]](''n''<sup>2</sup>), e in pratica l'algoritmo svolge il suo compito generalmente in modo più veloce dell'[[Insertion sort]], sebbene dipenda dai dettagli implementativi.
== Pseudocodice ==
Line 21 ⟶ 23:
== Algoritmo in C ==
<source lang="C">
Line 49 ⟶ 50:
== Algoritmo in JAVA ==
<source lang="JAVA">
Riga 81:
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<sup>3</sup>). 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.
==
{{interprogetto|w=Gnome sort|w_etichetta=questo algoritmo}}
[[Categoria:Algoritmi| ]]
{{Avanzamento|100%|4 marzo 2008}}
|