Clasificación de enanos
La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 1 de junio de 2021; la verificación requiere 1 edición .Gnome sort ( eng. Gnome sort ) es un algoritmo de clasificación similar a la clasificación por inserciones , pero a diferencia de este último, antes de insertar en el lugar correcto, se produce una serie de intercambios, como en la clasificación de burbujas . El nombre proviene del supuesto comportamiento de los gnomos de jardín al clasificar una línea de macetas de jardín.
La clasificación enana se basa en la técnica utilizada por el gnomo de jardín holandés común ( tuinkabouter holandés ). Este es el método por el cual un gnomo de jardín clasifica una línea de macetas. Esencialmente, mira las macetas de jardín actuales y anteriores: si están en el orden correcto, avanza una maceta; de lo contrario, las intercambia y retrocede una maceta. Condiciones de contorno: si no hay bote anterior, se avanza; si no hay otro bote, está acabado. dick grun
El algoritmo es conceptualmente simple y no requiere bucles anidados. tiempo de trabajo En la práctica, el algoritmo puede ejecutarse tan rápido como la ordenación por inserción.
El algoritmo encuentra el primer lugar donde dos elementos vecinos están en el orden incorrecto y los intercambia. Aprovecha el hecho de que un intercambio puede producir un nuevo par en el orden incorrecto justo antes o después de los elementos intercambiados. No permite ordenar los elementos después de la posición actual, por lo que solo es necesario verificar la posición antes de los elementos reorganizados.
Descripción
A continuación se muestra el pseudocódigo de clasificación . Esta es una versión optimizada que utiliza la variable j para permitir avanzar hasta donde se quedó antes de moverse hacia la izquierda, evitando iteraciones y comparaciones innecesarias:
Ejemplo:
Si queremos ordenar una matriz con elementos [4] [2] [7] [3] de mayor a menor, ocurrirá lo siguiente durante las iteraciones del bucle while:
- [4] [2] [7] [3] (estado inicial: i == 1, j == 2);
- [4] [2] [7] [3] (no pasó nada, pero ahora i == 2, j == 3);
- [4] [7] [2] [3] (intercambiar a[2] y a[1], ahora i == 1 y j == 3 todavía);
- [7] [4] [2] [3] (intercambiar a[1] y a[0], ahora i == 3, j == 4);
- [7] [4] [3] [2] (intercambiar a[3] y a[2], ahora i == 2, j == 4);
- [7] [4] [3] [2] (no pasó nada, pero ahora i == 4, j == 5);
- el ciclo se acaba porque i no es < 4.
Optimización
Como resultado de la optimización de gnome, la clasificación se transforma naturalmente en clasificación por inserción . Cada vez que "gnomo" alcanza un nuevo número, todos los valores a la izquierda de "gnomo" ya están ordenados.
Enlaces
- Descripción del método y listado de programas de clasificación de gnomos .
| Algoritmos de clasificación | |
|---|---|
| Teoría | Complejidad O notación relación de orden Ordenar tipos sostenible Interno Externo |
| Intercambio | |
| Elección | |
| inserciones | |
| fusión | |
| sin comparaciones | |
| híbrido | |
| Otro | |
| poco práctico | |