Ordenación por interpolación

Algoritmo de ordenación en informática

La ordenación por interpolación es un algoritmo de ordenación que es un tipo de ordenación por categorías . Utiliza una fórmula de interpolación para asignar datos a las categorías. Una fórmula de interpolación general es:

Interpolación = INT(((Array[i] - min) / (max - min)) * (ArraySize - 1))

Algoritmo

Ordenación por interpolación (o ordenación por histograma). ^[1] Es un algoritmo de ordenación que utiliza la fórmula de interpolación para dispersar los datos divide y vencerás . La ordenación por interpolación también es una variante del algoritmo de ordenación por cubos . ^[2] El método de ordenación por interpolación utiliza una matriz de longitudes de cubos de registros correspondientes a la columna de números originales. Al operar la matriz de longitud de mantenimiento, se puede evitar que el algoritmo recursivo cambie la complejidad del espacio debido al apilamiento de memoria. El registro de segmentación de la matriz de longitud puede usar una función secundaria para declarar y eliminar dinámicamente el espacio de memoria de la matriz . La complejidad del espacio requerida para controlar el programa recursivo es . Contiene una matriz bidimensional de memorias asignadas dinámicamente y una matriz de longitudes de registros. Sin embargo, la complejidad de ejecución aún se puede mantener como un método de ordenación eficiente de . ^[3] La matriz de memoria asignada dinámicamente se puede implementar mediante lista enlazada , pila , cola , matriz asociativa , estructura de árbol , etc. Un objeto de matriz como JavaScript es aplicable. La diferencia en la estructura de datos está relacionada con la velocidad de acceso a los datos y, por lo tanto, el tiempo necesario para la clasificación . Cuando los valores en la matriz ordenada se distribuyen uniformemente aproximadamente en la progresión aritmética , el tiempo lineal del ordenamiento por interpolación es . ^[4] ${\displaystyle O(n^{2})}$ ${\displaystyle O(3n)}$ ${\displaystyle O(n+k)}$ ${\displaystyle O(n)}$

Algoritmo de ordenación por interpolación

1. Establezca una matriz de longitud de contenedor para registrar la longitud del contenedor sin clasificar. Inicialice en la longitud de la matriz original.
2. [Ordenamiento principal] Si se borra la matriz de longitud de contenedor y se completa el ordenamiento, ejecute [Función de división] si no se borra.
3. [Función de división] Ejecuta la función de división extrayendo una longitud de contenedor del final de la matriz de longitud de contenedor. Encuentra los valores máximo y mínimo en el contenedor. Si el valor máximo es igual al valor mínimo, se completa la ordenación para detener la función de división.
4. Crea una matriz bidimensional con todos los cubos vacíos. Divide los cubos según el número de interpolación.
5. Después de dividir en los contenedores, inserte la longitud de los contenedores en la matriz de longitud de contenedor y vuelva a colocar los elementos en la matriz original uno por uno de todos los contenedores que no estén vacíos.
6. Regresar a [Ordenamiento principal].

Algoritmo de ordenación de histogramas

La definición del NIST: Un refinamiento eficiente de tres pasos de un algoritmo de ordenamiento de cubos. ^[5]

1. El primer paso cuenta la cantidad de elementos de cada contenedor en una matriz auxiliar y luego hace un total acumulado de modo que cada entrada auxiliar sea la cantidad de elementos anteriores.
2. La segunda pasada coloca cada artículo en su contenedor correspondiente de acuerdo con la entrada auxiliar de la clave de ese artículo.
3. La última pasada clasifica cada cubo.

Práctica

Implementación de ordenación por interpolación

Código JavaScript:

Matriz . prototipo . interpolationSort = function () { var divideSize = new Array (); var fin = this . longitud ; divideSize [ 0 ] = fin ; mientras ( divideSize . longitud > 0 ) { dividir ( this ); } // Repetir la función dividir en ArrayList función dividir ( A ) { var tamaño = divideSize . pop (); var inicio = fin - tamaño ; var min = A [ inicio ]; var max = A [ inicio ]; para ( var i = inicio + 1 ; i < fin ; i ++ ) { si ( A [ i ] < min ) { min = A [ i ]; } de lo contrario { si ( A [ i ] > max ) { max = A [ i ]; } } } si ( min == max ) { fin = fin - tamaño ; } de lo contrario { var p = 0 ; var bucket = new Array ( tamaño ); para ( var i = 0 ; i < tamaño ; i ++ ) { bucket [ i ] = new Array (); } para ( var i = inicio ;                                                                                                                         i < fin ; i ++ ) { p = Math.piso ( (( A [ i ] -min ) / ( max - min ) ) * ( tamaño - 1 )); cubo [ p ] .push ( A [ i ] ); } para ( var i = 0 ; i < tamaño ; i ++ ) { si ( cubo [ i ] .longitud > 0 ) { para ( var j = 0 ; j < cubo [ i ] .longitud ; j ++ ) { A [ inicio ++ ] = cubo [ i ][ j ] ; } dividirTamaño.push ( cubo [ i ] .longitud ) ; } } } } } ;                                                         

Método recursivo de ordenación por interpolación

Complejidad espacial en el peor de los casos: ${\displaystyle O(n^{2})}$

Matriz . prototipo . interpolaciónSort = función () { //-- Fecha de edición: 2019/08/31 --// var inicio = 0 ; var tamaño = this . longitud ; var mínimo = this [ 0 ]; var máximo = this [ 0 ]; para ( var i = 1 ; i < tamaño ; i ++ ) { si ( this [ i ] < mínimo ) { mínimo = this [ i ]; } de lo contrario { si ( this [ i ] > máximo ) { máximo = this [ i ];} } } si ( mínimo ! = máximo ) { var cubo = nueva Matriz ( tamaño ); para ( var i = 0 ; i < tamaño ; i ++ ) { cubo [ i ] = nueva Matriz (); } var interpolación = 0 ; para ( var i = 0 ; i < tamaño ; i ++ ) { interpolación = Math . piso ((( este [ i ] - min ) / ( máximo - min )) * ( tamaño - 1 )); cubo [ interpolación ]. empujar ( este [ i ]); } para ( var i = 0 ; i < tamaño ;                                                                                                               i ++ ) { if ( bucket [ i ]. length > 1 ) { bucket [ i ]. interpolationSort (); } // Recursión para ( var j = 0 ; j < bucket [ i ]. length ; j ++ ) { this [ start ++ ] = bucket [ i ][ j ]; } } } } ;                         

Implementación de ordenación por histograma

Matriz . prototipo . histogramaSort = función () { //-- Fecha de edición: 14/11/2019 --// var fin = esta . longitud ; var sortedArray = nueva Matriz ( fin ); var interpolación = nueva Matriz ( fin ); var hitCount = nueva Matriz ( fin ); var divideSize = nueva Matriz ( fin ); divideSize [ 0 ] = fin ; mientras ( divideSize . longitud > 0 ) { distribuir ( esta ); } // Repetir la función distribuir en la Matriz función distribuir ( A ) { var tamaño = divideSize . pop (); var inicio = fin - tamaño ; var min = A [ inicio ]; var max = A [ inicio ]; para ( var i = inicio + 1 ; i < fin ; i ++ ) { si ( A [ i ] < min ) { min = A [ i ]; } else { if ( A [ i ] > max ) { max = A [ i ]; } } } if ( min == max ) { end = end - size ; } else { for ( var i = start ; i < end ; i ++ ) {                                                                                                                     hitCount [ i ] = 0 ; } para ( var i = inicio ; i < fin ; i ++ ) { interpolación [ i ] = inicio + Math.floor ( (( A [ i ] - min ) / ( max - min ) ) * ( tamaño - 1 )); hitCount [ interpolación [ i ]] ++ ; } para ( var i = inicio ; i < fin ; i ++ ) { si ( hitCount [ i ] > 0 ) { dividirSize.push ( hitCount [ i ]) ; } } hitCount [ fin - 1 ] = fin - hitCount [ fin - 1 ] ; para ( var i = fin - 1 ; i > inicio ; i -- ) { hitCount [ i - 1 ] = hitCount [ i ] - hitCount [ i - 1 ] ; } para ( var i = inicio ; i < fin ; i ++ ) { sortedArray [ hitCount [ interpolación [ i ]]] = A [ i ]; hitCount [ interpolación [ i ]] ++ ; } para ( var i = inicio ; i < fin                                                                                                ; i ++ ) { A [ i ] = matrizordenada [ i ]; } } } } ;        

Variante

Ordenación de etiquetas por interpolación

La clasificación por etiquetas de interpolación es una variante de la clasificación por interpolación. Al aplicar el método de clasificación y división de contenedores, los datos de la matriz se distribuyen en un número limitado de contenedores mediante una fórmula de interpolación matemática y, a continuación, el contenedor procesa de forma recursiva el programa de procesamiento original hasta que se completa la clasificación.

La ordenación por etiquetas de interpolación es un método de ordenación recursiva para la ordenación por interpolación. Para evitar el desbordamiento de apilamiento causado por la recursión, la memoria se bloquea. En su lugar, utilice una matriz de etiquetas de tipo de datos booleanos para operar la función recursiva para liberar la memoria. El espacio de memoria adicional requerido es cercano a . Contiene una matriz bidimensional de memoria asignada dinámicamente y una matriz de etiquetas de tipo de datos booleanos. La pila, la cola, la matriz asociativa y la estructura de árbol se pueden implementar como contenedores. ${\displaystyle 2n+(n)bits}$

Como el objeto de matriz de JavaScript es adecuado para este método de ordenación, la diferencia en la estructura de datos está relacionada con la velocidad de acceso a los datos y, por lo tanto, el tiempo necesario para la ordenación. El tiempo lineal Θ(n) se utiliza cuando los valores de la matriz que se va a ordenar están distribuidos de manera uniforme. El algoritmo de ordenación por cubos no limita la ordenación al límite inferior de . La complejidad del rendimiento promedio de la ordenación por etiquetas de interpolación es . ^[3] ${\displaystyle O(nlogn)}$ ${\displaystyle O(n+k)}$

Algoritmo de ordenación de etiquetas por interpolación

1. Establezca una matriz de etiquetas igual al tamaño de la matriz original e inicialícela con un valor falso.
2. [Ordenación principal] Determina si se han ordenado todos los contenedores de la matriz original. Si la ordenación no se ha completado, se ejecuta la [función de división].
3. [Función de división] Encuentra los valores máximo y mínimo en el contenedor. Si el valor máximo es igual al valor mínimo, se completa la clasificación y se detiene la división.
4. Crea una matriz bidimensional con todos los cubos vacíos. Divide los cubos según el número de interpolación.
5. Después de dividir en el contenedor, marque la posición inicial del contenedor como un valor verdadero en la matriz de etiquetas y vuelva a colocar los elementos en la matriz original uno por uno desde todos los contenedores que no estén vacíos.
6. Regresar a [Ordenamiento principal].

Práctica

Código JavaScript:

Array . prototipo . InterpolaionTagSort = function () { // Whale Chen acepta la "Licencia CC BY-SA 3.0 de Wikipedia". Fecha de firma: 2019-06-21 // var end = this . length ; if ( end > 1 ) { var start = 0 ; var Tag = new Array ( end ); // Paso 1 del algoritmo for ( var i = 0 ; i < end ; i ++ ) { Tag [ i ] = false ; } Divide ( this ); } while ( end > 1 ) { // Paso 2 del algoritmo while ( Tag [ -- start ] == false ) { } // Encuentra el inicio del siguiente depósito Divide ( this ); }                                                             función Dividir ( A ) { var min = A [ inicio ]; var max = A [ inicio ]; para ( var i = inicio + 1 ; i < fin ; i ++ ) { si ( A [ i ] < min ) { min = A [ i ]; } de lo contrario { si ( A [ i ] > max ) { max = A [ i ]; } } } si ( min == max ) { fin = inicio ; } // Algoritmo paso-3 Comienza para ser el final del siguiente depósito de lo contrario { var interpolación = 0 ; var tamaño = fin - inicio ; var Depósito = new Array ( tamaño ); // Algoritmo paso-4 para ( var i = 0 ; i < tamaño ; i ++ ) { Depósito [ i ] = new Array (); } para ( var i = inicio ; i < fin ; i ++ ) { interpolación = Math . piso ((( A [ i ] - min ) / ( max - min )) * ( tamaño - 1 )); Cubo [ interpolación ] .push ( A [ i ]); } para ( var i = 0 ; i                                                                                                                                      < tamaño ; i ++ ) { if ( Bucket [ i ] .length > 0 ) { // Algoritmo paso 5 Tag [ start ] = true ; for ( var j = 0 ; j < Bucket [ i ] .length ; j ++ ) { A [ start ++ ] = Bucket [ i ][ j ]; } } } } } // Algoritmo paso 6 };                                   

Ordenación de etiquetas por interpolación en el lugar

La ordenación por interpolación de etiquetas en el lugar es un algoritmo de ordenación por interpolación en el lugar. La ordenación por interpolación de etiquetas en el lugar puede lograr la ordenación con solo N intercambios manteniendo N etiquetas de bits; sin embargo, la matriz que se va a ordenar debe ser una secuencia de números enteros continua y no repetida, o la serie debe estar completamente distribuida de manera uniforme para aproximarse al número de progresión aritmética .

Los datos de la columna de factores no deben repetirse. Por ejemplo, la clasificación de 0 a 100 se puede realizar en un solo paso. El número de intercambios es: , la complejidad del tiempo de cálculo es: , y la peor complejidad espacial es . Si las características de la serie cumplen los requisitos condicionales de este método de clasificación: "La matriz es un entero continuo o una progresión aritmética que no se repite", la clasificación por etiquetas de interpolación en el lugar será un excelente método de clasificación que es extremadamente rápido y ahorra espacio de memoria. ${\displaystyle O(n)}$ ${\displaystyle O(n)}$ ${\displaystyle O(n)bits}$

Algoritmo de ordenamiento de etiquetas por interpolación in situ

La ordenación por etiquetas de interpolación en el lugar ordena series de números enteros consecutivos no repetitivos, solo una matriz de etiquetas de tipo de datos booleanos con la misma longitud que la matriz original, la matriz calcula la interpolación de los datos desde el principio y la interpolación apunta a una nueva posición de la matriz. La posición que se ha intercambiado se marca como verdadera en la posición correspondiente de la matriz de etiquetas y se incrementa hasta que se ordena el final de la matriz.

Proceso del algoritmo:

1. Establezca un número igual de matrices de etiquetas para inicializar con valores falsos.
2. Visita la matriz cuando tag[i] es falso, calcula la posición correspondiente a la interpolación=p.
3. Intercambie a[i] y a[p], deje que tag[p] = verdadero.
4. El recorrido se ha completado y la clasificación se ha completado.

Práctica

Código JavaScript:

Matriz . prototipo . InPlaceTagSort = function () { // Fecha de edición: 2019-07-02 var n = this . length ; var Tag = new Array ( n ); for ( i = 0 ; i < n ; i ++ ) { Tag [ i ] = false ; } var min = this [ 0 ]; var max = this [ 0 ]; for ( i = 1 ; i < n ; i ++ ) { if ( this [ i ] < min ) { min = this [ i ]; } else { if ( this [ i ] > max ) { max = this [ i ]; } } } var p = 0 ; var temp = 0 ; for ( i = 0 ; i < n ; i ++ ) { while ( Tag [ i ] == false ) { p = Math . piso ((( este [ i ] - min ) / ( máximo - min )) * ( n - 1 )); temp = este [ i ]; este [ i ] = este [ p ]; este [ p ] = temp ; Etiqueta [ p ] = verdadero                                                                                                                  ; } } }; necesitaSortArray . InPlaceTagSort ();     

El origen de la clasificación in situ realizada en tiempo O(n)

En su libro "Análisis matemático de algoritmos", Donald Knuth señaló que "... la investigación sobre la complejidad computacional es una forma interesante de afinar nuestras herramientas para los problemas más rutinarios que enfrentamos día a día". ^[6]

Knuth señaló además que, con respecto al problema de clasificación, la permutación in situ efectiva en el tiempo está inherentemente conectada con el problema de encontrar los líderes del ciclo, y las permutaciones in situ podrían realizarse fácilmente a tiempo si se nos permitiera manipular bits de "etiqueta" adicionales que especifiquen cuánto de la permutación se ha llevado a cabo en un momento dado. Sin esos bits de etiqueta, concluye, "parece razonable conjeturar que cada algoritmo requerirá para la permutación in situ al menos pasos en promedio". ^[6] ${\displaystyle O(n)}$ ${\displaystyle n}$ ${\displaystyle n\log n}$

La clasificación de etiquetas por interpolación in situ es uno de los algoritmos de clasificación que el profesor Donald Knuth dijo: "manipular bits de "etiqueta" adicionales... encontrar los líderes del ciclo y las permutaciones in situ podrían realizarse fácilmente a tiempo". ${\displaystyle n}$ ${\displaystyle O(n)}$

Método de clasificación similar

1. Clasificación flash
2. Ordenación de mapas de proximidad
3. Clasificación de la bandera estadounidense

Ordenación por cubos que combina otros métodos de ordenación y un algoritmo recursivo

La ordenación por cubos se puede combinar con otros métodos de ordenación para completar la ordenación. Si se ordena por cubos y por inserción, también es un método de ordenación bastante eficiente. Pero cuando la serie muestra una gran desviación del valor: por ejemplo, cuando el valor máximo de la serie es mayor que N veces el siguiente valor más grande. Después de que se procesa la serie de columnas, la distribución es que todos los elementos excepto el valor máximo caen en el mismo cubo. El segundo método de ordenación utiliza la ordenación por inserción. Puede hacer que la complejidad de ejecución caiga en . Esto ha perdido el significado y el rendimiento de alta velocidad del uso de la ordenación por cubos. ${\displaystyle O(n^{2})}$

La ordenación por interpolación es una forma de utilizar recursivamente la ordenación por cubos. Después de realizar la recursión, siga utilizando la ordenación por cubos para dispersar la serie. Esto puede evitar la situación anterior. Si desea que la complejidad de ejecución de la ordenación por interpolación recursiva caiga en , es necesario presentar una amplificación factorial en toda la serie. De hecho, hay muy pocas posibilidades de que se produzca una serie de distribuciones especiales. ${\displaystyle O(n^{2})}$

Referencias

1. Algoritmo NIST. "ordenación por interpolación". Definición: Véase ordenación por histograma.
2. Ordenación del histograma ^{[ referencia circular ]}
3. 桶排序 (clasificación de cubos) ^{[ referencia circular ]}
4. Análisis de casos promedio de clasificación de cubos ^{[ referencia circular ]}
5. Algoritmo NIST. "Ordenación por histograma". Definición: Un refinamiento eficiente de tres pasos de un algoritmo de ordenación por cubos.
6. Karl-Dietrich Neubert (1998). "El algoritmo FlashSort" . Consultado el 6 de noviembre de 2007 .

Enlaces externos

• interpolacionOrdenar.html
• histogramaOrdenar.html
• El algoritmo FlashSort
• Análisis matemático de algoritmos
• http://www.drdobbs.com/database/the-flashsort1-algorithm/184410496
• 桶排序遞迴方式演算法 Clasificación de cubos Método recursivo. Ballena Chen 16/09/2012
• 插值標簽排序演算法 Algoritmo de clasificación de etiquetas de interpolación. Ballena Chen 24/03/2013
• Ordenación por interpolación (versión Pascal disponible)
• Plataforma de prueba de ordenamiento de matrices JavaScript de w3schools