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.,[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 (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é
Referències
Enllaços externs
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
