En los tipos de distribución, los elementos se distribuyen y redistribuyen en clases hasta que se ordena la matriz.
En el caso más general, esto ocurre aproximadamente de la misma manera. Los elementos están dispersos por clases según algún criterio. Si esto no conduce a la ordenación de la matriz, los atributos de la clase se refinan y los elementos se vuelven a dispersar a las clases refinadas. Y esto sucede hasta que la matriz se ordena.
En las clasificaciones por distribución, casi siempre no hay comparaciones de elementos entre ellos y sus intercambios. Lo principal es si el elemento pertenece a una determinada clase o no, su comparación con otros elementos rara vez juega un papel.
Típicamente, estos tipos tienen una complejidad de tiempo lineal (en lugar de logarítmica, como ocurre con los tipos eficientes de intercambios, fusiones, elecciones o inserciones). Además, los algoritmos de esta clase casi siempre requieren mucha memoria adicional, ya que los elementos agrupados por clases deben almacenarse en algún lugar.
Los tipos de distribución son buenos para clasificar enteros y cadenas. Ordenar números reales con ellos suele ser inconveniente. Además, la distribución ordena perfectamente los arreglos que consisten en números repetidos: cuantas más repeticiones, menos clases diferentes se requieren.
Este artículo fue escrito con el apoyo de EDISON.
Opinión del cliente: 10 plus de programadores de EDISON
Esto es interesante y útil para saber: programador de desayuno
Considere un algoritmo que demuestre de manera más convexa las propiedades anteriores.
Tipo de cubo :: Tipo de cubo
Otros nombres son clasificación de cestas, clasificación de bloques, clasificación de bolsillo.
Dispersamos los números en canastas, luego en cada canasta nos dispersamos en canastas más pequeñas, y así sucesivamente, hasta que en algún nivel de la canasta solo hay los mismos elementos. Luego, desde esas cestas del nivel más bajo, es fácil restaurar la matriz en un estado ordenado.
Vamos a explicar con un ejemplo específico. Digamos que tenemos una matriz desordenada. Se sabe que esta matriz contiene números del 1 al 8.
Lanzamos estos números en 2 grupos: los números del 1 al 4 caen en un grupo, del 5 al 8 en el segundo, luego distribuimos los números en la primera canasta en dos canastas: en un número 1 y 2, y en el otro 3 y 4. También distribuimos estas canastas en canastas de bast, que ya contienen números del mismo tamaño. A esa canasta grande que contiene números del 5 al 8, aplicamos una recursión similar.
Luego, desde pequeñas cestas, cada una de las cuales contiene los mismos números, devolvemos los elementos a la matriz principal en orden de precedencia.
La clasificación nuclear de esta forma no es particularmente aplicable en la práctica, pero demuestra de manera estándar cómo funcionan en general todas las clasificaciones por distribución.
Clasificación de Thanos :: Clasificación de Thanos
A veces me envían clases de autor y este es solo un caso. El autor Andrei Danilin lo llamó "clasificación rusa en mitades", sin embargo, lo denominé clasificación de Thanos. O, si procedemos formalmente de los métodos utilizados, podemos llamar a su ordenamiento aritmético medio.
La media aritmética de los elementos se calcula en la matriz y luego todos los elementos se distribuyen en 2 grupos. Los elementos más pequeños que (o igual a) la media aritmética van a un grupo, más grandes que la media aritmética al segundo grupo. Luego, las mismas acciones se aplican recursivamente a ambos grupos, y así hasta el final.
¿Y qué hay del titanio loco? Si se trata de una matriz aleatoria, entonces, en general, el elemento, en comparación con la media aritmética, tiene una probabilidad de 50/50 de ir a uno de los dos grupos.
Por cierto, en Internet me encontré con otro algoritmo cómico con el mismo nombre. Si la matriz no está ordenada, haga clic en el Guante Infinito y envíe la mitad de los elementos de la matriz seleccionados al azar a la inexistencia. Si los supervivientes forman una matriz ordenada, entonces su gran misión puede considerarse cumplida. Si aún no lo está, puede hacer algunos clics más.
Pero volvamos a nuestras clasificaciones de distribución. Todos ellos se pueden dividir en solo dos grupos:
recuento y
ordenación por bits . Bueno, si lo desea, también puede resaltar
clasificaciones de bits de conteo , es decir, los que pueden atribuirse a ambos.
También hay algoritmos híbridos (estos son aquellos que usan métodos de diferentes clases, por ejemplo, la clasificación de Tim es una mezcla de clasificación de fusión e inserción, la clasificación introspectiva es una clasificación rápida que se clasifica en grupos, etc.), incluidas las clasificaciones de distribución Sin embargo, los híbridos son una sección separada. Sobre ellos más tarde.
Miles de clasificación y media aritmética se relacionan con las clases de conteo.
Clases de conteo
La idea básica es que contamos cuántos números hay en cada clase.
Conteo de clasificación :: Conteo de clasificación
Contamos cuántas veces se produce uno u otro número en la matriz. Conociendo estas cantidades, formamos rápidamente una matriz ya ordenada.
Para esta clasificación, necesita saber el mínimo y el máximo en la matriz. Luego, las claves se generan para la matriz auxiliar, en la que arreglamos qué y cuántas veces nos reunimos.
Código de Python:
def CountingSort(array, mn, mx): count = defaultdict(int) for i in array: count[i] += 1 result = [] for j in range(mn,mx+1): result += [j]* count[j] return result
Clasificación de palomas :: Clasificación de palomas
Pasamos por la matriz, si se encuentra un nuevo número, entonces iniciamos el contador (como la clave de la lista auxiliar) de este número. Si el número no se encuentra por primera vez, entonces el incremento para este contador simplemente se activa.
La diferencia con el método anterior es que al ordenar por conteo, inmediatamente comenzamos contadores para todos los números posibles que pueden ocurrir en la matriz (podemos permitirlo si se conocen el máximo y el mínimo en la matriz). Algunos números nunca aparecen y sus contadores muestran cero. En la clasificación de palomas, comenzamos contadores solo para aquellos números que realmente ocurren en la matriz. Se utiliza una matriz en la clasificación de contadores para contadores, y se utiliza una lista doblemente vinculada en la clasificación de palomas, que le permite agregar nuevos contadores sobre la marcha.
Este método a veces se denomina
clasificación de Dirichlet , porque el algoritmo en sí mismo es una ilustración de varias consecuencias del principio de Dirichlet.
Si N objetos se distribuyen entre M contenedores y N> M, entonces al menos un contenedor contiene más de un elemento.
Código de Python:
def PigeOnHoleSort(a): mi = min(a) size = max(a) - mi + 1 holes = [0] * size for x in a: holes[x - mi] += 1 i = 0 for count in range(size): while holes[count] > 0: holes[count] -= 1 a[i] = count + mi i += 1
Clasificación de bits
Distribuimos los números dependiendo de qué dígito se encuentre en una categoría particular del número. Si hacemos esto varias veces para diferentes dígitos, de repente obtenemos una matriz ordenada.
Orden de bits de bajo orden :: LSD radix sort
Nos movemos de los dígitos más bajos a los más antiguos y en cada iteración distribuimos los elementos de la matriz dependiendo de qué dígito esté en el dígito.
Después de la siguiente distribución, devolvemos los elementos a la matriz principal en el orden en que los elementos caen en las clases durante la próxima redistribución.
Para las clasificaciones bit a bit, es importante que se considere que los elementos tienen el mismo número de dígitos. Si el número real de dígitos es diferente, entonces el problema se resuelve agregando ceros adicionales como dígitos más altos.
Clasificación de bits de alto orden :: Clasificación de radios MSD
Primero, distribuimos entre los rangos superiores, de los cuales pasamos a los más jóvenes.
Esta opción es más difícil de implementar, ya que la transición a los dígitos más bajos se realiza de forma recursiva dentro de las clases, y no entre todos los elementos de la matriz.
Pero esta complejidad se ve recompensada por el hecho de que MSD es más rápido que LSD. Al pasar de los dígitos más bajos a los más antiguos, debe procesar todos los dígitos de todos los números para ordenarlos correctamente. Si pasa de mayor a menor, de hecho, no tiene que procesar todos los dígitos de todos los números, el estado ordenado, como regla, es anterior.
La mayoría de las clasificaciones bit a bit son una variación del MSD más eficiente. Esto es especialmente útil para ordenar cadenas; para esto, generalmente se usa un árbol de sufijos. Analizaremos en uno de los siguientes artículos.
Contando clasificaciones bit a bit
A veces, la clasificación de distribución es simultáneamente contable y bit a bit.
Bead Sort :: Bead sort
Otros nombres del algoritmo: clasificación de ábaco, clasificación por gravedad.
Ya escribí sobre esta clasificación un par de veces (
1 ,
2 ), así que seré breve, solo la esencia.
Supongamos que cada número en una matriz es un conjunto de bolas, el número de bolas es el valor de un número. Si ordenamos los números entre sí como filas horizontales de estas bolas y luego las empujamos verticalmente, obtenemos una matriz ordenada.
El truco aquí es que representamos cada número usando bolas en un sistema de números unarios. Y, de hecho, simplemente contamos cuántas veces todos los números tienen cada dígito.
BeadSort en Python en una línea:
Después de un tiempo, analizaremos clasificaciones más complejas de conteo de bits, entre las cuales la clasificación de la
bandera estadounidense ocupa un lugar destacado.
Referencias
Cuchara /
Cucharones ,
Conteo /
Casillero /
Dirichlet ,
Radix /
Descargas ,
GranoArtículos de la serie:
La aplicación AlgoLab Excel se ha actualizado significativamente. Algunos algoritmos del artículo de hoy aparecieron allí por primera vez. Actualiza quién está usando.