Ordenación adaptativa por montículo

En informática , el ordenamiento por montículo adaptativo es un algoritmo de ordenamiento basado en comparaciones perteneciente a la familia del ordenamiento adaptativo . Es una variante del ordenamiento por montículo que funciona mejor cuando los datos contienen un orden preexistente. Publicado por Christos Levcopoulos y Ola Petersson en 1992, el algoritmo utiliza una nueva medida de preordenamiento, Osc, como el número de oscilaciones. ^[¹^] En lugar de colocar todos los datos en el montículo como lo hacía el ordenamiento por montículo tradicional, el ordenamiento por montículo adaptativo solo toma una parte de los datos en el montículo, de modo que el tiempo de ejecución se reduce significativamente cuando el preordenamiento de los datos es alto. ^[¹^]

Ordenación por montones

El ordenamiento por montículo es un algoritmo de ordenamiento que utiliza una estructura de datos de montículo binario . El método trata un arreglo como un árbol binario completo y construye un montículo máximo/mínimo para lograr el ordenamiento. ^[²^] Generalmente implica los siguientes cuatro pasos.

Construir un Max-Heap (Min-Heap): colocar todos los datos en el montón de manera que todos los nodos sean mayores o iguales (menores o iguales para Min-Heap ) a cada uno de sus nodos hijos.
Intercambia el primer elemento del montón con el último elemento del montón.
Elimina el último elemento del montón y colócalo al final de la lista. Ajusta el montón para que el primer elemento quede en el lugar correcto.
Repita los pasos 2 y 3 hasta que el montón tenga un solo elemento. Coloque este último elemento al final de la lista y muestre la lista. Los datos de la lista estarán ordenados.

A continuación se muestra una implementación en C/C++ que construye un montón máximo (Max-Heap) y ordena el array una vez construido el montón.

/* Código de ejemplo de ordenación por montículo en AC/C++ que ordena un array en orden ascendente */// Una función que construye un árbol binario de montículo máximo void heapify ( int array [], int start , int end ) { int parent = start ; int child = parent * 2 + 1 ; while ( child <= end ) { if ( child + 1 <= end ) // cuando hay dos nodos hijos { if ( array [ child + 1 ] > array [ child ]) { child ++ ; // tomar el nodo hijo mayor } } if ( array [ parent ] > array [ child ]) { return ; // si el nodo padre es mayor, entonces ya está convertido en montículo } if ( array [ parent ] < array [ child ]) // cuando el nodo hijo es mayor que el nodo padre { swap ( array [ parent ], array [ child ]); // intercambiar el nodo padre y el hijo parent = child ; child = child * 2 + 1 ; // continuar el bucle, comparar el nodo hijo y sus nodos hijos } } }// Función heap_sort void heap_sort ( int array [], int len ) { for ( int i = len / 2 - 1 ; i >= 0 ; i -- ) // Paso 1: construir el montículo máximo { heapify ( array , i , len ); } for ( int i = len - 1 ; i >= 0 ; i -- ) // Paso 4: repetir los pasos 2 y 3 hasta terminar { swap ( array [ 0 ], array [ i ]); // Paso 2: colocar el máximo al final del array heapify ( array , 0 , i -1 ); // Paso 3: eliminar el máximo del árbol y volver a heapify } }int main () {//el array que se ordenará int array [] = { 42 , 1283 , 123 , 654 , 239847 , 45 , 97 , 85 , 763 , 90 , 770 , 616 , 328 , 1444 , 911 , 315 , 38 , 5040 , 1 }; int array_len = sizeof ( array ) / sizeof ( * array ); //longitud del arrayordenación_montón ( array , array_len );devolver 0 ; }

Medidas de preordenamiento

Las medidas de preordenamiento miden el orden existente en una secuencia dada. ^{[ 3 ]} Estas medidas de preordenamiento deciden la cantidad de datos que se colocarán en el montón durante el proceso de ordenamiento, así como el límite inferior del tiempo de ejecución. ^{[ 4 ]}

Oscilaciones ( Osc )

Para la secuencia $X=\langle x_{1},x_{2},x_{3},\dots,x_{n}\rangle$ , Cruz ( x _i ) se define como el número de aristas del gráfico de línea de X que son intersectadas por una línea horizontal que pasa por el punto ( i, x _i ). Matemáticamente, se define como ${\mathit {Cross}}(x_{i})=\{j\mid \min\{x_{j},x_{j+1}\}<x_{i}<\max\{x_{j},x_{j+1}\}{\text{ para }}1\leq j<n\}{\text{, para }}1\leq i\leq n$ . La oscilación ( Osc ) de X es simplemente el número total de intersecciones, definido como ${\mathit {Osc}}(x)=\textstyle \sum _{i=1}^{n}\displaystyle \lVert {\mathit {Cross}}(x_{i})\rVert$ . ^{[ 1 ]}

Otras medidas

Además de la medida original Osc, otras medidas conocidas incluyen el número de inversiones Inv , el número de ejecuciones Runs , el número de bloques Block y las medidas Max , Exc y Rem . La mayoría de estas diferentes medidas están relacionadas para la ordenación adaptativa por montículos. Algunas medidas dominan a las demás: todo algoritmo óptimo para Osc es óptimo para Inv y Runs; todo algoritmo óptimo para Inv es óptimo para Max; y todo algoritmo óptimo para Block es óptimo para Exc y Rem. ^{[ 4 ]}

Algoritmo

El ordenamiento por montículo adaptativo es una variante del ordenamiento por montículo que busca la optimalidad ( asintóticamente óptima ) con respecto al límite inferior derivado con la medida de preordenamiento aprovechando el orden existente en los datos. En el ordenamiento por montículo, para un dato $X=\langle x_{1},x_{2},x_{3},\dots,x_{n}\rangle$ , colocamos todos los n elementos en el montón y luego seguimos extrayendo el máximo (o mínimo) n veces. Dado que el tiempo de cada acción de extracción del máximo es logarítmico en el tamaño del montón, el tiempo total de ejecución de la ordenación estándar por montón es $\color {Blue}O(n\log n)$ . ^{[ 2 ]} Para la ordenación adaptativa por montículo, en lugar de colocar todos los elementos en el montículo, solo se colocarán en el montículo los máximos posibles de los datos (candidatos a máximo) de manera que se requieran menos ejecuciones cuando cada vez que intentamos localizar el máximo (o mínimo).

Primero, se construye un árbol cartesiano a partir de la entrada en $O(n)$ El algoritmo ordena los datos en un árbol binario, haciendo que cada nodo sea mayor (o menor) que todos sus nodos hijos. La raíz del árbol cartesiano se inserta en un montón binario vacío. A continuación, se extrae repetidamente el máximo del montón binario, se recupera el máximo del árbol cartesiano y se añaden sus hijos izquierdo y derecho (si los hay), que también son árboles cartesianos, al montón binario. Si la entrada ya está casi ordenada, los árboles cartesianos estarán muy desequilibrados, con pocos nodos que tengan hijos izquierdo y derecho, lo que hará que el montón binario permanezca pequeño y permitirá que el algoritmo ordene más rápidamente. $O(n\log n)$ para entradas que ya están casi ordenadas. ^{[ 5 ]}

A continuación se muestra una implementación en pseudocódigo: ^{[ 1 ]}

Entrada: una matriz de n elementos que necesitan ser ordenados. Construye el árbol cartesiano l ( x ) Inserta la raíz de l ( x ) en un montón. para i = de 1 a n { Realizar ExtractMax en el montón si el elemento máximo extraído tiene algún hijo en l ( x ) { recuperar los niños en l ( x ) insertar el elemento hijo en el montón } }

Desventajas

A pesar de décadas de investigación, aún existe una brecha entre la teoría del ordenamiento adaptativo por montículos y su uso práctico. Debido a que el algoritmo utiliza árboles cartesianos y manipulación de punteros, tiene una baja eficiencia de caché y altos requisitos de memoria, lo que deteriora el rendimiento de las implementaciones. ^{[ 4 ]}

Véase también

Referencias

1 2 3 4 Levcopoulos, C.; Petersson, O. (1993-05-01). "Adaptive Heapsort". Journal of Algorithms . 14 (3): 395– 413. doi : 10.1006/jagm.1993.1021 . ISSN 0196-6774 .
1 2 Schaffer, R.; Sedgewick, R. (1993-07-01). "El análisis de Heapsort". Journal of Algorithms . 15 (1): 76– 100. doi : 10.1006/jagm.1993.1031 . ISSN 0196-6774 .
↑ Mannila, Heikki (abril de 1985). "Medidas de preordenamiento y algoritmos de ordenamiento óptimos". IEEE Transactions on Computers . C-34 (4): 318– 325. doi : 10.1109/TC.1985.5009382 . ISSN 0018-9340 .
1 2 3 Edelkamp, Stefan; Elmasry, Amr; Katajainen, Jyrki (2011). "Dos realizaciones óptimas de factor constante del algoritmo de ordenación por montículos adaptativo". En Iliopoulos, Costas S.; Smyth, William F. (eds.). Algoritmos combinatorios . Notas de clase en ciencias de la computación. Vol. 7056. Springer Berlin Heidelberg. pp. 195–208 . doi : 10.1007/978-3-642-25011-8_16 . ISBN 9783642250118. S2CID 10325857 .
↑ "Archivo de código interesante" . www.keithschwarz.com . Consultado el 31 de octubre de 2019 .

[:0-1] 1 2 3 4 Levcopoulos, C.; Petersson, O. (1993-05-01). "Adaptive Heapsort". Journal of Algorithms . 14 (3): 395– 413. doi : 10.1006/jagm.1993.1021 . ISSN 0196-6774 .

[:1-2] 1 2 Schaffer, R.; Sedgewick, R. (1993-07-01). "El análisis de Heapsort". Journal of Algorithms . 15 (1): 76– 100. doi : 10.1006/jagm.1993.1031 . ISSN 0196-6774 .

[3] Mannila, Heikki (abril de 1985). "Medidas de preordenamiento y algoritmos de ordenamiento óptimos". IEEE Transactions on Computers . C-34 (4): 318– 325. doi : 10.1109/TC.1985.5009382 . ISSN 0018-9340 .

[:2-4] 1 2 3 Edelkamp, Stefan; Elmasry, Amr; Katajainen, Jyrki (2011). "Dos realizaciones óptimas de factor constante del algoritmo de ordenación por montículos adaptativo". En Iliopoulos, Costas S.; Smyth, William F. (eds.). Algoritmos combinatorios . Notas de clase en ciencias de la computación. Vol. 7056. Springer Berlin Heidelberg. pp. 195–208 . doi : 10.1007/978-3-642-25011-8_16 . ISBN 9783642250118. S2CID 10325857 .

[5] "Archivo de código interesante" . www.keithschwarz.com . Consultado el 31 de octubre de 2019 .

[ 3 ]

[ 5 ]