Gnome-sort

De Viquipèdia
Dreceres ràpides: navegació, cerca

El gnome-sort és un algorisme d'ordenació del tipus bubble-sort bidireccional, recorrent les dades a ordenar en ziga-zaga

Té una història d'invenció quasi paral·lela, durant un temps va existir la polèmica sobre la seva invenció, finalment atribuïda a Hamid Sarbazi-Azad qui ho va desenvolupar en en any 2000 i al que va anomenar Stupid-sort .

Exemple de l'operativa pas a pas

Quan Dick Grune el va inventar (més correctament el va reinventar) i documentar.,[1] no va trobar proves que existís i en paraules seves, va dir d'ell "the simplest sort algorithm" [2] (és l'algorisme més simple) i potser tingui raó, doncs ho va descriure en només 4 línies de codi. Dick Grune es va basar en els gnoms de jardí holandès, en com es col·loquen en els testos (veure la referència anterior) i d'aquí també el nom que li va donar.

Netament és un algorisme de bombolla amb una clara particularitat: recorre la matriu a ordenar com una cremallera, en un va i vé , és a dir pot ser definit com un ordenament de bombolla bidireccional, que al seu torn són anomenats també cokctail shaker (agitador de còctels), per la forma en què treballa ...

Compleix estrictament parlant amb la complexitat O ( n ² ).

Descripció[modifica | modifica el codi]

L'algorisme comença comparant la primera parella de valors, si estan en ordre incrementa el punter i de nou fa la comparació, si no estan en ordre, es passa, el menor a l'esquerra i el major a la dreta, i es redueix el punter, ara la comparació és amb l'element anterior, si no hi ha un element anterior es passa al següent element. Quan el punter arriba l'extrem superior de l'array ja està totalment ordenat.

Quan compara cap amunt va sense fer intercanvis, és que el parell sota examen està ordenat entre si, i quan compara cap avall, va fent intercanvis. El procés apareix com un zigzagueig continu a banda i banda.

L'operació comença pel punter en el punt més baix i quan arriba a l'extrem superior ha acabat d'ordenar l'array.

Per a realitzar un ordenament invers n'hi ha prou canviar la decisió d'intercanvi dels elements, és a dir deixar els grans baix i els menors amunt.

Implementacions[modifica | modifica el codi]

Pseudocodi[modifica | modifica el codi]

i: = 1
j: = 2
 Mentre  i ≤ també - 1
 Si  a [i-1] ≤ a [i]
i: = j
j: = j+1
 Sinó 
intercanviar a [i-1] i a [i]
i: = i - 1
 If  i = 0
i: = 1
}

Codi en Vb.Net[modifica | modifica el codi]

Module Module1
 Private Sub swap (ByRef a As Integer, ByRef b As Integer)
 Dim temp As Integer
 temp = a
 a = b
 b = temp
 End Sub
 
 Private Sub gnomeSort (ByVal a () As Integer)
 Dim i As Integer
 i = 2
 
 While (i <= UBound (a))
 If (a (i - 1) <= a (i)) Then
 i = i+1
 Else
 swap (a (i - 1), a (i))
 i = i - 1
 If i = 1 Then
 i = 2
 End If
 End If
 End While
 
 End Sub
 
 Sub Main ()
 Dim VECT (50000) As Integer
 Dim X As Integer
 
 For x = 1 To UBound (VECT)
 VECT (X) = Cint (Rnd () * 50)
 Next
 gnomeSort (VECT)
 For X = 1 To UBound (VECT)
 Console.WriteLine (VECT (X))
 Next
 Console.ReadKey ()
 End Sub
End Module

Vegeu també[modifica | modifica el codi]

Referències[modifica | modifica el codi]

Enllaços externs[modifica | modifica el codi]