Clasificación por cubos

Cuando la entrada contiene varias claves cercanas entre sí (agrupación), es probable que esos elementos se coloquen en el mismo cubo, lo que da como resultado que algunos cubos contengan más elementos de lo normal. El peor escenario se produce cuando todos los elementos se colocan en un solo cubo. En ese caso, el rendimiento general estaría dominado por el algoritmo utilizado para ordenar cada cubo, por ejemplo${\displaystyle O(n^{2})}$ordenación por inserción o${\displaystyle O(n\log(n))}$algoritmos de ordenación por comparación , como la ordenación por fusión .

Consideremos el caso en que la entrada se distribuye uniformemente. El primer paso, que consiste en inicializar los cubos y encontrar el valor máximo de la clave en el array, se puede realizar en${\displaystyle O(n)}$tiempo. Si la división y la multiplicación se pueden realizar en tiempo constante, entonces dispersar cada elemento en su cubo también cuesta.${\displaystyle O(n)}$. Supongamos que se utiliza el ordenamiento por inserción para ordenar cada cubo, entonces el tercer paso cuesta${\displaystyle O(\textstyle \sum _ {i=1}^{k}\displaystyle n_ {i}^{2})}$, dónde${\displaystyle n_{i}}$es la longitud del cubo indexado${\displaystyle i}$. Dado que nos referimos al tiempo promedio, la expectativa${\displaystyle E(n_{i}^{2})}$en su lugar debe evaluarse.${\displaystyle X_{ij}}$sea ​​la variable aleatoria que es${\displaystyle 1}$si elemento${\displaystyle j}$se coloca en el cubo${\displaystyle i}$, y${\displaystyle 0}$de lo contrario. Tenemos${\displaystyle n_{i}=\sum _{j=1}^{n}X_{ij}}$. Por lo tanto,

${\displaystyle {\begin{aligned}E(n_{i}^{2})&=E\left(\sum _{j=1}^{n}X_{ij}\sum _{l=1}^{n}X_{il}\right)\\&=E\left(\sum _{j=1}^{n}\sum _{l=1}^{n}X_{ij}X_{il}\right)\\&=E\left(\sum _{j=1}^{n}X_{ij}^{2}\right)+E\left(\sum _{1\leq j,l\leq n}\sum _{j\neq l}X_{ij}X_{il}\right).\end{aligned}}}$

La última línea separa la suma en el caso${\displaystyle j=l}$y el caso${\displaystyle j\neq l}$. Dado que la probabilidad de que un objeto se distribuya al cubo es baja.${\displaystyle i}$es${\displaystyle 1/k}$,${\displaystyle X_{ij}}$es 1 con probabilidad${\displaystyle 1/k}$y 0 en caso contrario.

${\displaystyle E(X_{ij}^{2})=1^{2}\cdot \left({\frac {1}{k}}\right)+0^{2}\cdot \left(1-{\frac {1}{k}}\right)={\frac {1}{k}}}$

${\displaystyle E(X_{ij}X_{ik})=1\cdot \left({\frac {1}{k}}\right)\left({\frac {1}{k}}\right)={\frac {1}{k^{2}}}}$

Con la suma, sería

${\displaystyle E\left(\sum _{j=1}^{n}X_{ij}^{2}\right)+E\left(\sum _{1\leq j,k\leq n}\sum _{j\neq k}X_{ij}X_{ik}\right)=n\cdot {\frac {1}{k}}+n(n-1)\cdot {\frac {1}{k^{2}}}={\frac {n^{2}+nk-n}{k^{2}}}}$

Finalmente, la complejidad sería${\displaystyle O\left(\sum _{i=1}^{k}E(n_{i}^{2})\right)=O\left(\sum _{i=1}^{k}{\frac {n^{2}+nk-n}{k^{2}}}\right)=O\left({\frac {n^{2}}{k}}+n\right)}$.

El último paso del algoritmo de ordenación por cubetas, que consiste en concatenar todos los objetos ordenados en cada cubeta, requiere${\displaystyle O(k)}$tiempo. Por lo tanto, la complejidad total es${\displaystyle O\left(n+{\frac {n^{2}}{k}}+k\right)}$. Tenga en cuenta que si k se elige como${\displaystyle k=\Theta (n)}$, luego se ejecuta la ordenación por cubetas en${\displaystyle O(n)}$tiempo promedio, dada una entrada distribuida uniformemente. ^{[ 1 ]}

La variante más común del algoritmo de ordenación por cubetas opera sobre una lista de n entradas numéricas entre cero y un valor máximo M , dividiendo el rango de valores en b cubetas, cada una de tamaño M / b . Si cada cubeta se ordena mediante el algoritmo de ordenación por inserción , se puede demostrar que la ordenación se ejecuta en tiempo lineal esperado (donde se toma el promedio sobre todas las entradas posibles). ^{[ 3 ]} Sin embargo, el rendimiento de esta ordenación se degrada con la agrupación; si muchos valores aparecen muy cerca unos de otros, todos caerán en una sola cubeta y se ordenarán lentamente. Esta degradación del rendimiento se evita en el algoritmo original de ordenación por cubetas asumiendo que la entrada se genera mediante un proceso aleatorio que distribuye los elementos uniformemente en el intervalo [0,1) . ^{[ 1 ]}

De forma similar al algoritmo de ordenación por cubetas genérico descrito anteriormente, ProxmapSort funciona dividiendo una matriz de claves en submatrices mediante una función de "clave de mapa" que conserva un orden parcial de las claves. A medida que cada clave se agrega a su submatriz, se utiliza la ordenación por inserción para mantenerla ordenada, de modo que toda la matriz quede ordenada cuando ProxmapSort finaliza. ProxmapSort se diferencia de la ordenación por cubetas en el uso de la clave de mapa para ubicar los datos aproximadamente donde les corresponde en el orden ordenado, generando un "proxmap" (un mapeo de proximidad) de las claves.

Otra variante del algoritmo de ordenación por cubetas, conocida como ordenación por histograma o ordenación por conteo, añade una pasada inicial que cuenta el número de elementos que caerán en cada cubeta mediante un arreglo de conteo. ^{[ 4 ]} Con esta información, los valores del arreglo se pueden organizar en una secuencia de cubetas in situ mediante una secuencia de intercambios, sin generar sobrecarga de espacio para el almacenamiento de cubetas.

El algoritmo de ordenación del cartero es una variante del algoritmo de ordenación por cubetas que aprovecha una estructura jerárquica de elementos, generalmente descrita por un conjunto de atributos. Este es el algoritmo que utilizan las máquinas clasificadoras de correos : el correo se clasifica primero entre nacional e internacional; luego por estado, provincia o territorio; luego por oficina de correos de destino; luego por rutas, etc. Dado que las claves no se comparan entre sí, el tiempo de clasificación es O( cn ), donde c depende del tamaño de la clave y del número de cubetas. Esto es similar a un algoritmo de ordenación por radix que funciona "de arriba hacia abajo" o "de arriba al dígito más significativo primero". ^{[ 5 ] [ 6 ]}

El algoritmo de ordenación por mezcla ^{[ 7 ]} es una variante del algoritmo de ordenación por cubetas que comienza eliminando el primer octavo de los n elementos a ordenar, los ordena recursivamente y los coloca en un arreglo. Esto crea n /8 "cubetas" en las que se distribuyen los 7/8 elementos restantes. Cada "cubeta" se ordena y las "cubetas" se concatenan en un arreglo ordenado.