Clasificación de bloque

Ordenación por bloques (Pocket sort, basket sort, ing. Bucket sort ): algoritmo de clasificación , en el que los elementos ordenados se distribuyen entre un número finito de bloques separados (bolsillos, canastas) de modo que todos los elementos en cada bloque siguiente en orden sean siempre más (o menos) que en el anterior. Luego, cada bloque se ordena por separado, ya sea recursivamente por el mismo método o por uno diferente. Luego, los elementos se vuelven a colocar en la matriz . Este tipo de clasificación puede tener un tiempo de ejecución lineal.

Este algoritmo requiere conocimiento sobre la naturaleza de los datos que se van a clasificar, más allá de las funciones de "comparar" e "intercambiar", lo suficiente para la clasificación por combinación, la clasificación en montón, la clasificación rápida, la clasificación por shell y la clasificación por inserción.

Ventajas: pertenece a la clase de algoritmos rápidos con tiempo de ejecución lineal O(N) (en buenos datos de entrada).

Inconvenientes: se degrada mucho con un gran número de elementos poco diferentes, o en la función fallida de obtener el número de cesta a partir del contenido del elemento. En algunos de estos casos, para las cadenas que se producen en las implementaciones del algoritmo de compresión BWT basado en la clasificación de cadenas , resulta que la ordenación rápida de cadenas de Sedgwick es mucho más rápida que la ordenación por bloques en velocidad.

Algoritmo

Si los elementos de entrada se distribuyen uniformemente , entonces el tiempo de ejecución esperado del algoritmo de clasificación de bolsillo es lineal. Esto es posible debido a ciertas suposiciones sobre los datos de entrada. Pocketsort asume que los datos de entrada se distribuyen uniformemente en el intervalo [0, 1) .

La idea del algoritmo es dividir el segmento [0, 1) en n segmentos idénticos (bolsillos) y dividir n valores de entrada en estos bolsillos. Dado que los números de entrada se distribuyen de manera uniforme, se supone que cada casilla caerá en una pequeña cantidad de números. Luego, los números en los bolsillos se ordenan secuencialmente. Se obtiene una matriz ordenada enumerando secuencialmente los elementos de cada bolsillo.

Pseudocódigo

función cubo-ordenar (A, n) es cubetas ← nueva matriz de n elementos vacíos for i = 0 to (length(A)-1) inserte A [i] al final de la matriz cubetas[msbits(A[i], k)] for i = 0 to n - 1 do siguiente orden(cubetas[i]) devuelve cubos de concatenación de matrices [0], ..., cubos [n-1]

La entrada de la función de clasificación de depósitos es una matriz clasificable (lista, colección, etc.) A y el número de bloques - n .

La matriz de cubos es una matriz de matrices (una matriz de listas, una matriz de colecciones, etc.) que coinciden con la naturaleza de los elementos de A .

La función msbits(x,k) está estrechamente relacionada con el número de bloques - n (devuelve un valor de 0 a n) y, en general, devuelve los k bits más significativos de x ( floor(x/2^(size (x)-k ))) ). Se pueden usar varias funciones como msbits(x,k) que coincidan con la naturaleza de los datos ordenados y permitan dividir la matriz A en n bloques. Por ejemplo, para los caracteres AZ, esto podría ser una coincidencia con los números de letra 0-25, o devolver el código de la primera letra (0-255) para el juego de caracteres ASCII; para números [0, 1) puede ser la función floor(n*A[i]) , y para un conjunto arbitrario de números en el intervalo [a, b) puede ser la función floor (n*(A[i] ]-a)/(ba )) .

La función next-sort también implementa un algoritmo de clasificación para cada bloque creado en el primer paso. El uso recursivo de bucket-sort como next-sort convierte este algoritmo en un tipo radix . En el caso de n = 2 , corresponde a quicksort (aunque con una elección de pivote potencialmente mala).

Grado de dificultad

Estimemos la complejidad del algoritmo de ordenación de bloques para el caso en que la ordenación por inserción se utiliza como algoritmo de ordenación de bloques ( próxima ordenación a partir del pseudocódigo) .

Para estimar la complejidad del algoritmo, introduzcamos una variable aleatoria n i , que indica el número de elementos que caerán en el bolsillo B[i]. El tiempo de ejecución de la ordenación por inserción es . $O\izquierda(n^{2}\derecha)$

El tiempo de ejecución del algoritmo de clasificación de bolsillo es

$T(n)=\Theta(n)+\sum_{{i=0}}^{{n-1}}O(n_{i}^{2})$

Calculemos la expectativa matemática de ambas partes de la igualdad:

$M\left(T(n)\right)=M\left(\Theta (n)+\sum_{{i=0}}^{{n-1}}O(n_{i}^{2} )\right)=\Theta (n)+\sum_{{i=0}}^{{n-1}}O\left(M(n_{i}^{2})\right)$

Encontremos el valor . $M(n_{i}^{2})$

Introduzcamos una variable aleatoria , que es igual a 1 si cae en el i -ésimo bolsillo, y 0 en caso contrario: $X_{{ij}}$ A[j]

$n_{i}=\sum_{{j=1}}^{n}X_{{ij}}$

${\begin{matriz}M\left(n_{i}^{2}\right)=&M\left[\left(\sum_{{j=1}}^{n}X_{{ij}}\ derecha)^{2}\derecha]=M\izquierda[\sum_{{j=1}}^{n}\sum_{{k=1}}^{n}X_{{ij}}X_{ {ik}}\right]=\\\ &\sum_{{j=1}}^{n}M\left[X_{{ij}}^{2}\right]+\sum_{1 \leq j\leq n}}\ \sum _{{{1\leq k\leq n,k\neq j}}M\left[X_{{ij}}X_{{ik}}\right]\end{ matriz}}$

$M\left[X_{{ij}}^{2}\right]=1\cdot {\frac {1}{n}}+0\cdot \left(1-{\frac {1}{n}} \right)={\frac{1}{n}}$

Si k ≠ j , X ij y X ik son independientes, entonces:

$M\left[X_{{ij}}X_{{ik}}\right]=M\left[X_{{ij}}\right]M\left[X_{{ik}}\right]={\frac {1}{n^{2}}}$

De este modo

$M\left(n_{i}^{2}\right)=\sum_{{j=1}}^{{n}}{\frac {1}{n}}+\sum_{{1\ leq j\leq n}}\ \sum _{{{1\leq k\leq n,k\neq j}}{\frac {1}{n^{2}}}=2-{\frac {1} {norte}}$

Entonces, el tiempo de ejecución esperado del algoritmo de clasificación de bolsillo es

$\Theta (n)+n\cdot O(2-1/n)=\Theta (n)$

Literatura

Kormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Capítulo 8 Clasificación en tiempo lineal // Algoritmos: construcción y análisis, 2.ª edición = Introducción a los algoritmos, segunda edición. - M .: "Williams" , 2005. - S. 230 - 234. - ISBN 5-8459-0857-4 .

Véase también

Lista de algoritmos de clasificación

Enlaces

Visualizer1 es un subprograma de Java.
Visualizer2 es un subprograma de Java.

Algoritmos de clasificación
Teoría	Complejidad O notación relación de orden Ordenar tipos sostenible Interno Externo
Intercambio	burbuja Emocionante enanos Rápido Peine Clasificación par-impar bit a bit
Elección	Elección Piramidal Suave
inserciones	inserciones cáscara árbol
fusión	fusión
sin comparaciones	Contando bloquear
híbrido	introsorteo Timsort
Otro	topológico redes bitón
poco práctico	Bogosort Tipo de títere tortita lento