Gnome sort

De WikiLingua.net

L'algoritmo d'ordenació conegut com gNome_sort va ser inventat per Dick Grune i en paraules seves "the simplest sort algorithm" (és l'algoritmo més simple) i potser tingui raó.

Netamente és un algoritmo de bombolla amb una clara particularidad: recorre l'array a ordenar com una cremallera, en un va i veuen, o bé pot ser definit com un ordenament de bombolla bidireccional, que al seu torn són anomenats també cokctail shaker (agitador de cocteles), per la forma en què treballa...

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

[editar] Descripció

Després d'iniciar-se l'array compara parelles d'elements i intercanvia el menor pel major, a l'aconseguir l'extrem de l'array, diposita el major, marca un punter final en una unitat menys i inverteix el sentit de les comparacions, va descendint des del penúltim fins al primer element, allí diposita el menor trobat augmenta punter d'inici amb valor 1, i novament torna a realitzar comparacions ascendint... el bucle acaba quan els dos punters es diferencien en una unitat, és a dir acaba en el centre de l'array o subarray.

[editar] Implementaciones

[editar] Pseudocódigo

  funció gnomeSort(a\[0..tam-1]) {
  i := 1
  j := 2
  mentre i ≤ tam - 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
 }

[editar] Codi en Java

public class gnome
{
    public static void gnomeSort(int[] v)
    {
        int i = 1, aux= 0;
        while(i < v.length)
        {
            if (i == 0 || v [i-1] <= v [i])
                i++;
            else
            {
                aux = v [i - 1];
                v[i - 1] = v[i];
                v[i] = aux ;
                i --;
            }
        }
    }
 
    public static void main (String [] aaa)
    {
        gnomeSort(int[]);
    }
}

[editar] Codi en Visual Basic

S'assumeix un array públic i a la funció se li passen 2 paràmetres, que indiquen 2 elements dintre de l'array, si els elements són els extrems de l'array, ordenaria completament l'array, si els elements són índexs internedios, ordenaria el tram d'array comprès entre ambdós elements inclusivament

Ordena un array d'àmbit públic amb el mètode gNome, realitza prèviament un control de desbordamiento:

NOTA: canviada la capçalera dels comentaris per a no renyir-se amb wiki

Function fOrdenGnome(ordMin As Long, ordMax As Long) As string
   if ordMin < Lbound(array) or ordMin > Ubound(array) then return "ordMin fos de límits"        
   if ordMax < Lbound(array) or ordMax > Ubound(array) then return "ordMax fos de límits" 
                                                        -
   Dim topIni As Integer       -punter indicador d'elements ordenats a l'inici
   Dim topFin As Integer       -punter indicador d'elements ordenats a la fi
   Dim indices As Long         -quantitat d'itemes en joc 
   Dim dir As Integer          -especifica al punter l'adreça d'avanç
   Dim dirL As Integer         -punter que transforma un element absolut en el seu antecessor quan avança cap a a baix
   Dim dirU As Integer         -punter que transforma un element absolut en el seu successor quan avança cap a a dalt
   Dim i As Long               -el punter base
                                                        -
   topIni = ordMin                         -valors previs
   topFin = ordMax
   indices = ordMax - ordMin + 1
   dir = 1
   dirU = 1
   dirL = 0
                                                         -
   Do          
       Do
           If array(i + dirL) > array(i + dirU) Then
               call fSwap2(i + dirL, i + dirU)
           End If
           i = i + dir                                   -incrementa el punter local
       Loop Until i = topIni Or i = topFin   -comprova si es va arribar a un extrem o un altre
       If dir = 1 Then                       -si l'adreça era cap a a dalt s'augmenta el topall superior 
           topFin = topFin - 1
           dirL = -1: dirU = 0                           -invertim els punters locals per a fer la comparacón en la forma: i-1 > i
       Else                                        -si l'adreça era cap a a baix s'augmenta el topall inferior 
           topIni = topIni + 1                     
           dirL = 0: dirU = 1                            -invertim els punters locals per a fer la comparacón en la forma: i > i+1
       End If
       dir = dir * (-1)                                  -després d'aconseguir un topall rebotamos cap a l'altre costat
       i = i + dir                                       -i ajustem el punter en la nova adreça  
   Loop While (topFin - topIni) > 2                -anem estrenyent el cèrcol, acaba quan s'arriba al centro fi-ini=1
                                                         -
   return "OK"
End Function

-intercanvia el valor de 2 variables, d'un array d'àmbit públic entre si
function fSwap2(indiceA as long,indiceB as long) as string  
   dim temp as long
                                            -
   -if indiceA < Lbound(array) or indiceA> Ubound(array) then return "indiceA fos de límits" 'comprova integritat de límits 
   -if indiceB < Lbound(array) or indiceB> Lbound(array) then return "indiceB fos de límits" 
                                            -
   temp=array(indiceA)                      -una variable temporal conté el valor d'indiceA
   array(indiceA)=array(indiceB)            -indiceA adopta el valor d'indiceB
   array(indiceB)=temp                      -indiceB pren el valor que originalmente estava en indiceA 
                                            -
   return "OK"                        -retorna sense errors
end function

[editar] Codi en Python

def gnomesort(a )/a) :
    n = len(a )/a ) - 1
    while n:
        if a \[n - 1] > a \[n]:
            a \[n - 1], a \[n] = a \[n], a \[n - 1]
            if n + 1 < len(a )/a) : n += 1
            else: n -= 1
        else: n -= 1