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 . Exemple de l'operativa pas a pas
Quan Dick Grune el va inventar (més correctament el va reinventar) i documentar.,Url = http://xlinux.nist.gov/dads/HTML/gnomeSort.html no va trobar proves que existís i en paraules seves, va dir d'ell "the simplest sort algorithm" http://dickgrune.com/Programs/gnomesort.html (és l'algorisme més simple) i potser tingui raó, ja que 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 la matriu 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
Referències
Enllaços externs Dictionary of Algorithms and Data Structures del NIST Comparativa de diferents algorismes d'ordenació
Categoria:Algorismes d'ordenació