Implementazioni di algoritmi/Gnome sort: differenze tra le versioni

Contenuto cancellato Contenuto aggiunto
Ramac (discussione | contributi)
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 ==
{{Trasferimento|wb|Implementazioni}}
 
<source lang="C">
Line 49 ⟶ 50:
 
== Algoritmo in JAVA ==
{{Trasferimento|wb|Implementazioni}}
 
<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.
 
== CollegamentiAltri esterniprogetti ==
{{interprogetto|w=Gnome sort|w_etichetta=questo algoritmo}}
* [http://www.cs.vu.nl/~dick/gnomesort.html Gnome sort]
 
{{Ordinamento}}
[[Category:Algoritmi di ordinamento]]
 
[[Categoria:Algoritmi| ]]
[[de:Gnomesort]]
{{Avanzamento|100%|4 marzo 2008}}
[[en:Gnome sort]]
[[es:Gnome sort]]
[[pl:Sortowanie gnoma]]
[[pt:Gnome sort]]
[[tr:Cüce Sıralaması]]