El tipo gnomo (denominado tipo estúpido ) es un algoritmo de clasificación propuesto originalmente por el científico informático iraní Hamid Sarbazi-Azad (profesor de informática e ingeniería en la Universidad de Tecnología de Sharif ) [1] en 2000. El tipo se llamó primero tipo estúpido [2] (que no debe confundirse con bogosort ), y luego descrito por Dick Grune y nombrado tipo gnomo . [3]
Clase | Algoritmo de clasificación |
---|---|
Estructura de datos | Formación |
Rendimiento en el peor de los casos | |
Rendimiento en el mejor de los casos | |
Rendimiento medio | |
Complejidad espacial en el peor de los casos | auxiliar |
La ordenación gnome es un algoritmo de ordenación que es similar a la ordenación por inserción en el sentido de que funciona con un elemento a la vez, pero lleva el elemento al lugar correcto mediante una serie de intercambios, similar a una ordenación de burbujas . Es conceptualmente simple y no requiere bucles anidados . El tiempo de ejecución promedio es O ( n 2 ) pero tiende hacia O ( n ) si la lista está inicialmente casi ordenada. [4] [nota 1]
El algoritmo encuentra el primer lugar donde dos elementos adyacentes están en el orden incorrecto y los intercambia. Aprovecha el hecho de que realizar un intercambio puede introducir un nuevo par adyacente desordenado junto a los elementos intercambiados previamente. No asume que los elementos adelante de la posición actual estén ordenados, por lo que solo necesita verificar la posición directamente anterior a los elementos intercambiados.
Descripción
Dick Grune describió el método de clasificación con la siguiente historia: [3]
Gnome Sort se basa en la técnica utilizada por el gnomo de jardín holandés estándar (Du .: tuinkabouter ).
Así es como un gnomo de jardín ordena una línea de macetas .
Básicamente, mira la maceta junto a él y la anterior; si están en el orden correcto, da un paso hacia adelante, de lo contrario, los cambia y da un paso hacia atrás.
Condiciones de contorno: si no hay bote previo, da un paso hacia adelante; si no hay una olla a su lado, está listo.- "Gnome Sort - El algoritmo de ordenación más simple". Dickgrune.com
Código
Aquí hay un pseudocódigo para la ordenación gnome usando una matriz de base cero :
procedimiento gnomeSort (a []): pos: = 0 while pos si (pos == 0 o a [pos]> = a [pos-1]): pos: = pos + 1 demás: intercambiar una [pos] y una [pos-1] pos: = pos - 1
Ejemplo
Dada una matriz no ordenada, a = [5, 3, 2, 4], la ordenación gnome realiza los siguientes pasos durante el ciclo while. La posición actual se resalta en negrita y se indica como un valor de la variable pos
.
Mejoramiento
La clasificación gnome puede optimizarse introduciendo una variable para almacenar la posición antes de volver al principio de la lista. Con esta optimización, la ordenación gnome se convertiría en una variante de la ordenación por inserción .
Aquí hay un pseudocódigo para una ordenación gnome optimizada usando una matriz de base cero :
procedimiento optimizadoGnomeSort (a []): para pos en 1 a longitud (a): gnomeSort (a, pos)procedimiento gnomeSort (a [], upperBound): pos: = límite superior while pos> 0 y a [pos-1]> a [pos]: intercambiar una [pos-1] y una [pos] pos: = pos - 1
Notas
- ^ Casi ordenado significa que cada elemento de la lista no está lejos de su posición correcta (no más allá de una pequeña distancia constante).
Referencias
- ^ Hamid, Sarbazi-Azad. "Página de perfil de Hamid Sarbazi-Azad" . Archivado desde el original el 16 de octubre de 2018 . Consultado el 16 de octubre de 2018 .
- ^ Sarbazi-Azad, Hamid (2 de octubre de 2000). "Stupid Sort: un nuevo algoritmo de clasificación" (PDF) . Boletín de noticias . Departamento de Ciencias de la Computación, Univ. of Glasgow (599): 4. Archivado (PDF) desde el original el 7 de marzo de 2012 . Consultado el 25 de noviembre de 2014 .
- ^ a b "Gnome Sort - El algoritmo de clasificación más simple" . Dickgrune.com . 2000-10-02. Archivado desde el original el 31 de agosto de 2017 . Consultado el 20 de julio de 2017 .
- ^ Paul E. Black. "tipo gnomo" . Diccionario de algoritmos y estructuras de datos . Instituto Nacional de Estándares y Tecnología de EE. UU. Archivado desde el original el 11 de agosto de 2011 . Consultado el 20 de agosto de 2011 .