Ordenación por interpolación

1. Establezca una matriz de longitud de cubeta para registrar la longitud de la cubeta sin ordenar. Inicialícela con la longitud de la matriz original.
2. [Ordenación principal] Si se vacía el array de longitud de cubeta, la ordenación se completa. De lo contrario, se ejecuta la función Divide.
3. [Función Divide] Extrae el cubo al final del array de longitud de cubo. Encuentra los valores máximo y mínimo en el cubo. Si el valor máximo es igual al valor mínimo, el cubo está ordenado, así que detén la función Divide.
4. Crea una matriz bidimensional con todos los cubos vacíos. Divide los datos en los cubos según el número de interpolación.
5. Después de dividir en cubetas, agregue la longitud de cada cubeta a la matriz de longitud de cubeta. Luego, vuelva a colocar los elementos de todas las cubetas que no estén vacías en la matriz original, uno por uno.
6. Volver a [Ordenar principal].

El NIST describe la ordenación por histograma como un refinamiento eficiente de 3 pasadas de un algoritmo de ordenación por cubetas. ^{[ 2 ]}

1. En la primera pasada se cuenta el número de elementos de cada cubo en una matriz auxiliar y, a continuación, se realiza un total acumulado de manera que cada entrada auxiliar sea igual al número de elementos anteriores.
2. La segunda pasada coloca cada elemento en su categoría correspondiente según la entrada auxiliar para la clave de ese elemento.
3. La última pasada ordena cada cubo.

Código JavaScript:

Array . prototype . interpolationSort = function () { var divideSize = new Array (); var end = this . length ; divideSize [ 0 ] = end ; while ( divideSize . length > 0 ) { divide ( this ); } // Repetir la función divide a ArrayList function divide ( A ) { var size = divideSize . pop (); var start = end - size ; var min = A [ start ]; var max = A [ start ]; for ( var i = start + 1 ; i < end ; i ++ ) { if ( A [ i ] < min ) { min = A [ i ]; } else { if ( A [ i ] > max ) { max = A [ i ]; } } } if ( min == max ) { end = end - size ; } else { var p = 0 ; var bucket = new Array ( size ); para ( var i = 0 ; i < size ; i ++ ) { bucket [ i ] = new Array (); } para ( var i = start ;i < end ; i ++ ) { p = Math . floor ((( A [ i ] - min ) / ( max - min ) ) * ( size - 1 )); bucket [ p ]. push ( A [ i ]); } for ( var i = 0 ; i < size ; i ++ ) { if ( bucket [ i ]. length > 0 ) { for ( var j = 0 ; j < bucket [ i ]. length ; j ++ ) { A [ start ++ ] = bucket [ i ][ j ]; } divideSize . push ( bucket [ i ]. length ); } } } } };

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

Array . prototype . interpolationSort = function () { //-- Edit date:2019/08/31 --// var start = 0 ; var size = this . length ; var min = this [ 0 ]; var max = this [ 0 ]; for ( var i = 1 ; i < size ; i ++ ) { if ( this [ i ] < min ) { min = this [ i ]; } else { if ( this [ i ] > max ) { max = this [ i ];} } } if ( min != max ) { var bucket = new Array ( size ); for ( var i = 0 ; i < size ; i ++ ) { bucket [ i ] = new Array (); } var interpolation = 0 ; for ( var i = 0 ; i < size ; i ++ ) { interpolation = Math . piso ((( this [ i ] - min ) / ( max - min )) * ( size - 1 )); cubo [ interpolación ]. push ( this [ i ]); } para ( var i = 0 ; i < size ;i ++ ) { if ( bucket [ i ]. length > 1 ) { bucket [ i ]. interpolationSort (); } // Recursión for ( var j = 0 ; j < bucket [ i ]. length ; j ++ ) { this [ start ++ ] = bucket [ i ][ j ]; } } } };

La ordenación por etiquetas de interpolación es una variante recursiva de la ordenación por interpolación. Después de distribuir los datos del array en grupos mediante una función de interpolación, cada grupo ejecuta recursivamente el algoritmo original hasta que se completa la ordenación.

Para evitar el desbordamiento de pila causado por la recursión, utilice una matriz de etiquetas de tipo de datos booleano para operar la función recursiva y liberar la memoria. El espacio de memoria adicional requerido es cercano a bits. Contiene una matriz bidimensional de memoria asignada dinámicamente y una matriz de etiquetas de tipo de datos booleano. Los cubos se pueden implementar utilizando una pila, una cola, una matriz asociativa o una estructura de árbol.${\displaystyle 2n+(n)}$

Al igual que la ordenación por interpolación, la ordenación por etiquetas de interpolación se ejecuta en tiempo lineal cuando los valores en el array a ordenar están distribuidos uniformemente. El algoritmo de ordenación por cubetas no limita la ordenación al límite inferior de . La complejidad de rendimiento promedio de la ordenación por etiquetas de interpolación es .${\displaystyle O(n)}$${\displaystyle O(n\ log\ n)}$${\displaystyle O(n+k)}$

Array . prototype . InterpolaionTagSort = function () { // Whale Chen acepta la "Licencia Wikipedia CC BY-SA 3.0". 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 cubo Divide ( this ); }función Divide ( A ) { var min = A [ inicio ]; var max = A [ inicio ]; para ( var i = inicio + 1 ; i < fin ; i ++ ) { si ( A [ i ] < min ) { min = A [ i ]; } si no { si ( A [ i ] > max ) { max = A [ i ]; } } } si ( min == max ) { fin = inicio ; } // Paso 3 del algoritmo: Comienza para ser el final del siguiente cubo si no { var interpolación = 0 ; var tamaño = fin - inicio ; var Cubo = nuevo Array ( tamaño ); // Paso 4 del algoritmo para ( var i = 0 ; i < tamaño ; i ++ ) { Cubo [ i ] = nuevo Array (); } para ( var i = inicio ; i < fin ; i ++ ) { interpolación = Math . piso ((( A [ i ] - min ) / ( max - min )) * ( tamaño - 1 )); Cubo [ interpolación ]. empujar ( A [ i ]); } para ( var i = 0 ; i< tamaño ; i ++ ) { if ( Bucket [ i ]. length > 0 ) { // Paso 5 del algoritmo Tag [ start ] = true ; for ( var j = 0 ; j < Bucket [ i ]. length ; j ++ ) { A [ start ++ ] = Bucket [ i ][ j ]; } } } } } // Paso 6 del algoritmo };

El algoritmo de ordenación por interpolación in situ es una variante del algoritmo de ordenación por interpolación. Ordena series de enteros consecutivos no repetitivos. Permite la ordenación con solo N intercambios, manteniendo N etiquetas de bits, lo que ahorra tiempo y memoria. Sin embargo, el arreglo a ordenar debe ser una secuencia continua de enteros o una progresión aritmética no repetitiva.

Los datos de la columna del factor no deben repetirse. Por ejemplo, la ordenación de 0 a 100 se puede realizar en una sola pasada. El número de intercambios es: , la complejidad temporal del cálculo es: , y la complejidad espacial máxima es de bits.${\displaystyle O(n)}$${\displaystyle O(n)}$${\displaystyle O(n)}$

Este algoritmo utiliza únicamente un array de etiquetas adicional. Este array tiene la misma longitud que el array original y es de tipo booleano. Para cada elemento no intercambiado, el algoritmo calcula una nueva posición interpolada p e intercambia los dos elementos del array. El array de etiquetas se marca como verdadero en la posición p , y el algoritmo se incrementa hasta llegar al último elemento, momento en el que el array queda ordenado.

Proceso del algoritmo:

1. Establezca un número igual de matrices de etiquetas para inicializarlas con valores falsos.
2. Visita el array cuando tag[i] sea falso, calcula la posición correspondiente a interpolación=p.
3. Intercambia a[i] y a[p], sea tag[p] = verdadero.
4. El recorrido está completo y la clasificación también.

Array . prototype . InPlaceTagSort = function () { // Edit Date: 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 ((( this [ i ] - min ) / ( max - min )) * ( n - 1 )); temp = this [ i ]; this [ i ] = this [ p ]; this [ p ] = temp ; Tag [ p ] = true; } } }; necesitaSortArray . InPlaceTagSort ();