Gnome-sort

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 l'any 2000 i al que va anomenar Stupid-sort .

Quan Dick Grune el va inventar (més correctament el va reinventar) i documentar., no va trobar proves que existís i en paraules seves, va dir d'ell "the simplest sort algorithm" (é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 (vegeu 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ó

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

Pseudocodi

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

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é

• Bubble-sort

Enllaços externs

• Dictionary of Algorithms and Data Structures del NIST (anglès)
• Comparativa de diferents algorismes d'ordenació Arxivat 2016-01-13 a Wayback Machine. (anglès)