Gnome sort

Gnome sort

El algoritmo de ordenación conocido como gNome_sort tiene una historia de invención cuasi paralela. Durante un tiempo existió la polémica sobre su invención, finalmente atribuída a Hamid Sarbazi-Azad quien lo desarrolló en en año 2000 y al que llamó Stupid sort (Ordenamiento estúpido).

Ejemplo de la operativa paso a paso

Cuando Dick Grune lo inventó (más apropiadamente, lo reinventó) y documentó.,[1] no halló evidencias de que existiera y en palabras suyas, dijo de él "the simplest sort algorithm"[2] (es el algoritmo más simple) y quizás tenga razón, pués lo describió en solo 4 líneas de código. Dick Grune se basó en los gnomos de jardín holandés, en como se colocan en los maceteros (ver la referencia anterior) y de ahí también el nombre que le dió.

Netamente es un algoritmo de burbuja con una clara particularidad: recorre el array a ordenar como una cremallera, en un va y ven, o bien puede ser definido como un ordenamiento de burbuja bidireccional, que a su vez son llamados también cokctail shaker (agitador de cocteles), por la forma en que trabaja...

Cumple estrictamente hablando con la complejidad O().


Contenido

Descripción

El algoritmo empieza comparando la primera pareja de valores, si están en orden incrementa el puntero y de nuevo realiza la comparación, si no están en orden, se pasa, el menor a la izquierda y el mayor a la derecha, y se reduce el puntero, ahora la comparación es con el elemento anterior, si no hay un elemento anterior se pasa al siguiente elemento. Cuando el puntero alcanza el extremo superior del array ya está totalmente ordenado.

Cuando compara hacia arriba va sin hacer intercambios, es que el par bajo examen está ordenado entre si, y cuando compara hacia abajo, va haciendo intercambios. El proceso aparece como un zigzagueo contínuo a un lado y otro.

La operación empieza por el puntero en el punto más bajo y cuando llega al extremo superior ha terminado de ordenar el array.

Para realizar un ordenamiento inverso basta cambiar la decisión de intercambio de los elementos, es decir dejar los mayores abajo y los menores arriba.

Implementaciones

Pseudocódigo

  i := 1
  j := 2
  mientras i ≤ tam - 1
    si a[i-1] ≤ a[i]
        i := j
        j := j + 1 
    sino
        intercambiar a[i-1] y a[i]
        i := i - 1
        if i = 0
          i := 1
 }

Código 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

Referencias


Wikimedia foundation. 2010.

Mira otros diccionarios:

  • Gnome sort — is a sorting algorithm which is similar to insertion sort, except that moving an element to its proper place is accomplished by a series of swaps, as in bubble sort. The name comes from the supposed behavior of the Dutch garden gnome in sorting a …   Wikipedia

  • Sort (Unix) — Pour les articles homonymes, voir sort. sort est une commande POSIX qui permet de trier les lignes de fichiers texte. Par défaut, sort affiche l ensemble des lignes des fichiers qu on lui passe en paramètre triées par ordre croissant de la table… …   Wikipédia en Français

  • Sort (Lerida) — Sort (Lérida) Demande de traduction Sort → …   Wikipédia en Français

  • Gnome — This article is about the humanoid creature. For the computing desktop environment, see GNOME. For the lawn ornament, see garden gnome. For other uses, see Gnome (disambiguation). A gnome /ˈnoʊm …   Wikipedia

  • Gnome-panel — infobox software name = gnome panel caption = gnome panel active developer = GNOME latest release version = 2.20 latest release date = 19 September 2007 operating system = Cross platform genre = Desktop environment platform = GNOME license = GNU… …   Wikipedia

  • sort (Unix) — Pour les articles homonymes, voir sort. sort est une commande POSIX qui permet de trier des fichiers ou leurs contenus. Par défaut, sort affiche l ensemble des lignes des fichiers qu on lui passe en paramètre triées par ordre croissant de la… …   Wikipédia en Français

  • Comb sort — Class Sorting algorithm Data structure Array Worst case performance O(n log n)[1] …   Wikipedia

  • Merge sort — Example of merge sort sorting a list of random dots. Class Sorting algorithm Data structure Array Worst case performance O(n log n) …   Wikipedia

  • Selection sort — Infobox Algorithm class=Sorting algorithm data=Array time= О(n²) space= О(n) total, O(1) auxiliary optimal=Not usuallySelection sort is a sorting algorithm, specifically an in place comparison sort. It has O( n 2) complexity, making it… …   Wikipedia

  • Counting sort — In computer science, counting sort is an algorithm for sorting a collection of objects according to keys that are small integers; that is, it is an integer sorting algorithm. It operates by counting the number of objects that have each distinct… …   Wikipedia

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”