Clasificación de cubeta

Los elementos se distribuyen entre contenedores

Entonces, los elementos se clasifican dentro de cada bin

Ordenar por cubos, o ordenar por contenedores, es un algoritmo de clasificación que funciona distribuyendo los elementos de una matriz en varios cubos. Luego, cada depósito se clasifica individualmente, ya sea utilizando un algoritmo de clasificación diferente o aplicando recursivamente el algoritmo de clasificación de depósitos. Es un tipo de distribución, una generalización del tipo de casillero que permite múltiples claves por depósito, y es un primo del tipo radix en el tipo de dígito más a menos significativo. La clasificación de cubos se puede implementar con comparaciones y, por lo tanto, también se puede considerar un algoritmo de clasificación de comparación. La complejidad computacional depende del algoritmo utilizado para ordenar cada cubo, la cantidad de cubos que se usarán y si la entrada se distribuye uniformemente.

La ordenación por depósito funciona de la siguiente manera:

1. Establece una serie de "paquetes" inicialmente vacíos.
2. Scatter: Ir sobre la matriz original, poniendo cada objeto en su cubo.
3. Clasificar cada cubo no vacío.
4. Reunión: Visite los cubos en orden y ponga todos los elementos de nuevo en la matriz original.

Pseudocódigo

función baldeSort (array, k) escubos ← nuevo array de k listas vacías
M ← 1 + el valor máximo clave en el array
 para I = 0 a longitud (array) doinsertar array[i] en cubos[flor(k × array[i] / M)] para I = 0 a k do nextSort(buckets[i])
 retorno la concatenación de cubos[0],...., cubos[k]

Deje que matriz indique la matriz que se ordenará y k indicará la cantidad de cubos que se usarán. Se puede calcular el valor de clave máximo en tiempo lineal iterando sobre todas las claves una vez. La función Floor debe usarse para convertir un número flotante en un entero (y posiblemente también para convertir tipos de datos). La función nextSort es una función de clasificación que se utiliza para clasificar cada cubo. Convencionalmente, se usa la clasificación por inserción, pero también se pueden usar otros algoritmos, como clasificación por selección o clasificación por fusión. El uso de bucketSort en sí mismo como nextSort produce un tipo relativo de radix; en particular, el caso n = 2 corresponde a ordenación rápida (aunque potencialmente con malas opciones de pivote).

Análisis

Análisis del peor de los casos

Cuando la entrada contiene varias teclas que están cercanas entre sí (clustering), es probable que esos elementos se coloquen en el mismo cubo, lo que resulta en algunos cubos que contienen más elementos que el promedio. El peor escenario ocurre cuando todos los elementos se colocan en un solo cubo. El rendimiento general sería dominado por el algoritmo utilizado para ordenar cada cubo, por ejemplo O()n2){displaystyle O(n^{2}} Tipo de inserción o O()nlog⁡ ⁡ ()n)){displaystyle O(nlog(n)} algoritmos de comparación, como fusiones.

Análisis de casos promedio

Considere el caso de que la entrada se distribuya uniformemente. El primer paso, que es inicialización los cubos y encontrar el valor máximo clave en el array, se puede hacer en O()n){displaystyle O(n)} tiempo. Si la división y la multiplicación pueden hacerse en tiempo constante, entonces Esparcimiento cada elemento a su cubo también cuesta O()n){displaystyle O(n)}. Asumir tipo de inserción se utiliza para ordenar cada cubo, luego el tercer paso cuesta O().. i=1kni2){displaystyle O(textstyle sum ##{i=1} {k}displaystyle No., donde ni{displaystyle No. es la longitud del cubo indexado i{displaystyle i}. Puesto que estamos en relación con el tiempo promedio, la expectativa E()ni2){displaystyle E(n_{i}{2}} tiene que ser evaluado en su lugar. Vamos Xij{displaystyle X_{ij} ser la variable aleatoria que es 1{displaystyle 1} si el elemento j{displaystyle j} se coloca en el cubo i{displaystyle i}, y 0{displaystyle 0} De lo contrario. Tenemos ni=.. j=1nXij{displaystyle No, no.. Por lo tanto,

E()ni2)=E().. j=1nXij.. k=1nXik)=E().. j=1n.. k=1nXijXik)=E().. j=1nXij2)+E().. 1≤ ≤ j,k≤ ≤ n.. jل ل kXijXik){displaystyle {begin{aligned}E(n_{i}{2} {begin{aligned}E(sum} ¿Qué? ################################################################################################################################################################################################################################################################ - ¿Qué? ¿Por qué? ¿Por qué? Eleft(sum _{1leq j,kleq n}sum _{jneq ¿Qué?

La última línea separa la suma en el caso j=k{displaystyle j=k} y el caso jل ل k{displaystyle jneq k}. Desde la oportunidad de un objeto distribuido al cubo i{displaystyle i} es 1/k{displaystyle 1/k}, Xij{displaystyle X_{ij} es 1 con probabilidad 1/k{displaystyle 1/k} y 0 de lo contrario.

E()Xij2)=12⋅ ⋅ ()1k)+02⋅ ⋅ ()1− − 1k)=1k{displaystyle E(X_{y}{2})=1^{2}cdot left({frac {1}{k}}}}right)+0^{2}cdot left(1-{frac {1}{k}right)={frac}}{frac} {1}{k}}

E()XijXik)=1⋅ ⋅ ()1k)()1k)=1k2{displaystyle E(X_{ij}X_{ik})=1cdot left({frac {1}{k}}right)left({frac {1}{k}right)={frac {1}{k^{2}}}}}}}}}}}}}}}}}}}} {

Con la suma, sería

E().. j=1nXij2)+E().. 1≤ ≤ j,k≤ ≤ n.. jل ل kXijXik)=n⋅ ⋅ 1k+n()n− − 1)⋅ ⋅ 1k2=n2+nk− − nk2{displaystyle Eleft(sum _{j=1}{n}X_{ij}{2}right)+ Eleft(sum _{1leq j,kleq n}sum _{jneq k}X_{ij}X_{ik}right)=ncdot {frac {1}{k}+n(n-1)cdot {frac {1}{2}={frac} {fn}} {fn}}

Finalmente, la complejidad sería O().. i=1kE()ni2))=O().. i=1kn2+nk− − nk2)=O()n2k+n){displaystyle Oleft(sum) ¿Por qué? ¿Por qué? {fn}fn}derecha)=Oleft {n^{2} {k}}+nright)}.

El último paso del balde, que es concatenating todos los objetos ordenados en cada cubo, requiere O()k){displaystyle O(k)} tiempo. Por lo tanto, la complejidad total es O()n+n2k+k){displaystyle Oleft(n+{frac {n^{2}{k}kright)}. Tenga en cuenta que si k es elegido k=.. ()n){displaystyle k=Theta (n)}, entonces el balde corre O()n){displaystyle O(n)} tiempo promedio, dada una entrada distribuida uniformemente.

Optimizaciones

Una optimización común es volver a colocar los elementos no ordenados de los cubos en la matriz original primero, luego ejecutar la ordenación por inserción sobre la matriz completa; Debido a que el tiempo de ejecución de la clasificación por inserción se basa en la distancia a la que se encuentra cada elemento de su posición final, la cantidad de comparaciones sigue siendo relativamente pequeña y la jerarquía de la memoria se aprovecha mejor almacenando la lista de forma contigua en la memoria.

Si la distribución de entrada es conocida o puede ser estimada, los cubos se pueden elegir a menudo que contienen densidad constante (en lugar de simplemente tener tamaño constante). Esto permite O()n){displaystyle O(n)} complejidad media del tiempo, incluso sin entrada distribuida uniformemente.

Variantes

Ordenación de cubeta genérica

La variante más común de ordenación de depósitos opera en una lista de n entradas numéricas entre cero y algún valor máximo M y divide el rango de valores en n cubos de tamaño M/n. Si cada cubo se ordena mediante la ordenación por inserción, se puede mostrar que la ordenación se ejecuta en el tiempo lineal esperado (donde el promedio se toma de todas las entradas posibles). Sin embargo, el rendimiento de este tipo se degrada con la agrupación en clústeres; si hay muchos valores juntos, todos caerán en un solo cubo y se ordenarán lentamente. Esta degradación del rendimiento se evita en el algoritmo de ordenación de depósito original al suponer que la entrada se genera mediante un proceso aleatorio que distribuye los elementos de manera uniforme en el intervalo [0,1).

Ordenar mapa de proximidad

De forma similar a la ordenación de depósitos genéricos descrita anteriormente, ProxmapSort funciona dividiendo una matriz de claves en subarreglos mediante el uso de una "clave de mapa" función que conserva un ordenamiento parcial de las teclas; a medida que cada clave se agrega a su subarreglo, la ordenación por inserción se usa para mantener ese subarreglo ordenado, lo que da como resultado que todo el arreglo se ordene cuando se completa ProxmapSort. ProxmapSort se diferencia de las clasificaciones por depósito en el uso de la clave de mapa para colocar los datos aproximadamente donde pertenecen en el orden ordenado, produciendo un "proxmap" — un mapeo de proximidad — de las claves.

Ordenar histograma

Otra variante de ordenación de cubetas conocida como ordenación por histograma o clasificación por conteo agrega un paso inicial que cuenta la cantidad de elementos que caerán en cada cubeta usando una matriz de conteo. Con esta información, los valores de la matriz se pueden organizar en una secuencia de cubos en el lugar mediante una secuencia de intercambios, sin dejar espacio adicional para el almacenamiento de cubos.

Tipo de cartero

La clasificación del cartero es una variante de la clasificación por depósito que aprovecha una estructura jerárquica de elementos, normalmente descrita por un conjunto de atributos. Este es el algoritmo que utilizan las clasificadoras de cartas en las oficinas de correos: el correo se clasifica primero entre nacional e internacional; luego por estado, provincia o territorio; luego por la 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 la cantidad de cubos. Esto es similar a una ordenación radix que funciona "de arriba hacia abajo" o "el dígito más significativo primero."

Orden aleatorio

La clasificación aleatoria es una variante de la clasificación por cubos que comienza eliminando el primer 1/8 de los n elementos que se clasificarán, los clasifica recursivamente y los coloca en una matriz. Esto crea n/8 "depósitos" a la que se reparten los 7/8 restantes de las partidas. Cada "cubo" luego se clasifica y los "cubos" se concatenan en una matriz ordenada.

Comparación con otros algoritmos de clasificación

La ordenación por cubo puede verse como una generalización de la ordenación por conteo; de hecho, si cada cubeta tiene el tamaño 1, la clasificación de cubeta degenera a clasificación por conteo. El tamaño de depósito variable del tipo de depósito le permite usar memoria O(n) en lugar de memoria O(M), donde M es el número de distintos valores; a cambio, deja de contar el comportamiento en el peor de los casos de tipo O(n + M).

La ordenación por cubo con dos cubos es efectivamente una versión de ordenación rápida en la que el valor pivote siempre se selecciona para que sea el valor medio del rango de valores. Si bien esta opción es efectiva para entradas distribuidas uniformemente, otros medios para elegir el pivote en la ordenación rápida, como los pivotes seleccionados al azar, lo hacen más resistente a la agrupación en la distribución de entrada.

El algoritmo mergesort n-way también comienza distribuyendo la lista en n sublistas y clasificando cada una; sin embargo, las sublistas creadas por mergesort tienen rangos de valores superpuestos y, por lo tanto, no se pueden volver a combinar mediante una concatenación simple como en la ordenación por categorías. En su lugar, deben intercalarse mediante un algoritmo de combinación. Sin embargo, este gasto adicional se ve contrarrestado por la fase de dispersión más simple y la capacidad de garantizar que cada sublista tenga el mismo tamaño, lo que proporciona un buen límite de tiempo en el peor de los casos.

La ordenación radix de arriba hacia abajo se puede ver como un caso especial de ordenación por cubeta donde tanto el rango de valores como el número de cubetas están restringidos a ser una potencia de dos. En consecuencia, el tamaño de cada depósito también es una potencia de dos y el procedimiento se puede aplicar de forma recursiva. Este enfoque puede acelerar la fase de dispersión, ya que solo necesitamos examinar un prefijo de la representación de bits de cada elemento para determinar su cubo.