El número de tipos más o menos diferentes entre sí está garantizado en más de cien. Entre ellos hay subgrupos de algoritmos que son mínimamente diferentes entre sí, coincidiendo en alguna idea principal general. De hecho, en diferentes años, diferentes personas presentan las mismas clasificaciones de nuevo, que difieren en detalles no muy fundamentales.
Tal idea algorítmica se encuentra con más frecuencia que otras.
Cada elemento se ingresa
aproximadamente en ese lugar de la matriz donde debe ubicarse. Resulta una matriz
casi ordenada . A lo que se aplica la clasificación por inserciones (es más eficaz para procesar matrices casi ordenadas) o las áreas locales no ordenadas se procesan recursivamente por el mismo algoritmo.
Este artículo fue escrito con el apoyo de EDISON, que desarrolla una amplia gama de soluciones para una variedad de tareas: desde programas para probar en línea ropa de tiendas multimarca hasta un sistema de transmisión LED entre embarcaciones fluviales y marítimas .
¡Nos encanta la teoría de los algoritmos! ;-)
Para evaluar aproximadamente dónde desea colocar el elemento, debe averiguar cuánto difiere del elemento promedio de la matriz. Para hacer esto, necesita conocer los valores de los elementos mínimo y máximo, y el tamaño de la matriz.
Se supone que la matriz ordenada tiene datos realmente aleatorios. Todos los inventores de este método llegan a la misma fórmula:
k es el lugar aproximado en la matriz donde debería estar el elemento
A (
i )
min ,
max : valores de los elementos mínimo y máximo en la matriz
ATamaño : el número de elementos en la matriz
AAquí hay una idea tan general. Veamos en qué variaciones nació este algoritmo una y otra vez.
Clasificación del Rey Salomón :: Clasificación de Salomón
Este método (y su hermoso nombre) fue
propuesto por el usuario de
V2008n hace aproximadamente 5 años. Todo tiene su tiempo, "el tiempo de esparcir piedras y el tiempo de recoger piedras" (las palabras del Rey Salomón del libro de Eclesiastés), y en el algoritmo, esto es exactamente lo que sucede. Primero, con la ayuda de la fórmula, dispersamos los elementos en los lugares deseados de la matriz. Dado que la fórmula no proporciona un lugar exacto, sino aproximado, varios elementos que están cerca uno del otro en valor reclaman algunas posiciones a la vez. Estos grupos de elementos locales se ordenan por inserciones y luego se ensamblan en el orden final.
Tipo de interpolación
"No hay nada nuevo bajo el sol", para citar nuevamente al mismo autor. Wikipedia describe la clasificación por interpolación, que recuerda sospechosamente a la clasificación de Salomón. Cada "pila de piedras" es una pequeña matriz dinámica adicional, donde se encuentran elementos de importancia similar. La principal diferencia es que después de "piedras de dispersión", estos grupos locales de elementos sin clasificar no se ordenan por inserciones, sino por interpolación (recursivamente o en un bucle).
Una matriz ordenada es un conjunto de datos discretos que puede considerarse como un conjunto finito de valores conocidos de una determinada función desconocida. En realidad, una distribución aproximada desde el punto de vista de las matemáticas computacionales: esto es interpolación.
Clasificación de interpolación de JavaScript: bucle invertidoArray.prototype.interpolationSort = function() { var divideSize = new Array(); var end = this.length; divideSize[0] = end; while(divideSize.length > 0) {divide(this);} function divide(A) { var size = divideSize.pop(); var start = end - size; var min = A[start]; var max = A[start]; var temp = 0; 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); for(var i = 0; i < size; i++) {bucket[i] = new Array();} for(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); } } } } };
Clasificación de interpolación de JavaScript: versión recursiva Array.prototype.bucketSort = function() { 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.floor(((this[i] - min) / (max - min)) * (size - 1)); bucket[interpolation].push(this[i]); } for(var i = 0; i < size; i++) { if(bucket[i].length > 1) {bucket[i].bucketSort();}
Histogram sort :: Histogram sort
Esta es una optimización de la clasificación por interpolación, que cuenta el número de elementos que pertenecen a grupos locales sin clasificar. Este recuento le permite insertar elementos sin clasificar directamente en la matriz resultante (en lugar de agruparlos en pequeñas matrices separadas).
JavaScript Bar Sort Array.prototype.histogramSort = function() { var end = this.length; var sortedArray = new Array(end); var interpolation = new Array(end); var hitCount = new Array(end); var divideSize = new Array(); divideSize[0] = end; while(divideSize.length > 0) {distribute(this);} function distribute(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 { for(var i = start; i < end; i++){hitCount[i] = 0;} for(var i = start; i < end; i++) { interpolation[i] = start + Math.floor(((A[i] - min) / (max - min)) * (size - 1)); hitCount[interpolation[i]]++; } for(var i = start; i < end; i++) { if(hitCount[i] > 0){divideSize.push(hitCount[i]);} } hitCount[end - 1] = end - hitCount[end - 1]; for(var i = end - 1; i > start; i--) { hitCount[i - 1] = hitCount[i] - hitCount[i - 1]; } for(var i = start; i < end; i++) { sortedArray[hitCount[interpolation[i]]] = A[i]; hitCount[interpolation[i]]++; } for(var i = start; i < end; i++) {A[i] = sortedArray[i];} } } };
Tipo de etiqueta de interpolación
Para optimizar aún más la sobrecarga, aquí se propone no recordar el número de elementos de importancia similar en grupos sin clasificar, sino simplemente marcar el comienzo de estos grupos con banderas de Verdadero / Falso. Verdadero significa que el subgrupo ya está ordenado, y Falso significa que aún no lo está.
Clasificación de interpolación etiquetada con JavaScript Array.prototype.InterpolaionTagSort = function() { var end = this.length; if(end > 1) { var start = 0 ; var Tag = new Array(end);
Tipo de etiqueta de interpolación (en el lugar)
Si los valores de los elementos en la matriz no se repiten y se distribuyen de manera uniforme (en términos generales, si los datos en forma ordenada son algo así como una progresión aritmética), puede ordenar en una pasada, ordenando en su lugar, sin mover los elementos a matrices intermedias.
Ordenar por interpolación con etiquetas (en su lugar) en JavaScript Array.prototype.InPlaceTagSort = function() { 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.floor(((this[i] - min) / (max - min)) * (n - 1)); temp = this[i]; this[i] = this[p]; this[p] = temp; Tag[p] = true; } } };
Flash Ordenar :: Flashsort
Érase una vez,
escribí sobre la clasificación, que fue inventada por el profesor de biofísica Neubert en 1998.
El profesor sugirió distribuir los elementos en varias clases separadas (la membresía de la clase está determinada por el tamaño del elemento). Con esto en mente, la fórmula se ve así:
En lugar de Tamaño (tamaño de matriz), la fórmula indica
m - el número de clases por las cuales distribuimos los elementos de la matriz. La fórmula no calcula la clave en la matriz donde se debe lanzar el elemento, sino el número de clase al que pertenece el elemento.
Esta clasificación no es mala porque es más económica con respecto a la memoria adicional. La redistribución de elementos ocurre en el lugar. Solo la localización de clases se almacena por separado (bueno, si se mira desde un ángulo diferente, el número de elementos que pertenecen a una clase en particular se almacena por separado).
Bueno, el resto es la misma canción.
Clasificación de Flash en Java class FlashSort { static int n; static int m; static int[] a; static int[] l; public static void flashSort(int size) { n = size; generateRandomArray(); long start = System.currentTimeMillis(); partialFlashSort(); long mid = System.currentTimeMillis(); insertionSort(); long end = System.currentTimeMillis();
Clasificación aproximada :: Clasificación de mapa de proximidad
Esta clasificación es la más antigua de las mencionadas aquí; fue introducida en 1980 por el profesor Thomas Standish de la Universidad de California. En apariencia, parece ser significativamente diferente, pero si miras de cerca, todo es igual.
El algoritmo funciona con un concepto como un
hit : un número determinado que tiene un valor cercano a algún elemento de la matriz.
Para determinar si un elemento de matriz es un hit, se aplica una
función aproximada al elemento.
El profesor Standish ordenó matrices de números reales. La función aproximada era redondear los números reales a un número entero.
Es decir, por ejemplo, si la matriz contiene elementos 2.8, 2, 2.1, 2.6, etc. entonces un éxito para estos números será deuce.
Procedimiento general:
- Aplicamos una función aproximada a cada elemento, determinando qué hit corresponde al siguiente elemento.
- Por lo tanto, para cada golpe, podemos calcular el número de elementos correspondientes a este golpe.
- Conociendo el número de elementos para todos los hits, determinamos la localización de los hits (bordes a la izquierda) en la matriz.
- Conociendo la localización de golpes, determinamos la localización de cada elemento.
- Una vez determinada la localización del elemento, intentamos insertarlo en su lugar en la matriz. Si el lugar ya está ocupado, movemos a los vecinos a la derecha (si el elemento es más pequeño que ellos) para dejar espacio para el elemento. O a la derecha insertamos el elemento en sí (si es más que vecinos).
Como una función aproximada, puede asignar cualquiera en función de la naturaleza general de los datos en la matriz. En las implementaciones modernas de esta clasificación, los resultados generalmente se determinan no mordisqueando la parte fraccional, sino usando nuestra fórmula favorita.
Tipo de aproximación de JavaScript Array.prototype.ProxmapSort = function() { var start = 0; var end = this.length; var A2 = new Array(end); var MapKey = new Array(end); var hitCount = new Array(end); for(var i = start; i < end; i++) {hitCount[i] = 0;} var min = this[start]; var max = this[start]; for (var i = start+1; i < end; i++){ if (this[i] < min) { min = this[i]; } else { if(this[i] > max) {max = this[i];} } }
Clasificación de inserción de clasificación de hash :: Clasificación de hash
Bueno, terminaremos nuestra revisión con el algoritmo
que el habraiser de
bobbyKdas sugirió hace 6 años. Este es un algoritmo híbrido en el que, además de la distribución y las inserciones, también se agrega la fusión.
- La matriz se divide recursivamente por la mitad, hasta que en algún momento el tamaño de las medias subcadenas alcanza el tamaño mínimo (el autor no tiene más de 500 elementos).
- En el nivel de recursión más bajo, se aplica un algoritmo familiar a cada medio subcampo: con la misma fórmula, se produce una distribución aproximada dentro del subcampo, con la clasificación por insertos de secciones locales sin clasificar.
- Después de la disposición de las dos mitades de las submatrices, se fusionan.
- El punto 3 (fusión de mitades-subarreglos ordenados) se repite al subir a través de los niveles de recursión hasta la parte superior, cuando la matriz original se combina a partir de dos mitades.
Ordenar por inserción hash en Java import java.util.Arrays; import java.util.Date; import java.util.Random; public class HashSort {
La fórmula en sí se llama función hash, y la matriz auxiliar para distribución aproximada se llama tabla hash.
Referencias
Interpolación e histograma ,
Flash ,
Proxmap
Solomon ,
Hash Table ,
FlashArtículos de la serie:
La ordenación por aproximación apareció en la aplicación AlgoLab Excel (en este caso, en la matriz inicial sin clasificar, la parte fraccional aleatoria se agrega a los enteros). Solomon y Flash han estado allí durante mucho tiempo, pero aún no han implementado la interpolación, el hash y el histograma.