O número de tipos mais ou menos diferentes um do outro é garantido em mais de cem. Entre eles, existem subgrupos de algoritmos que são minimamente diferentes um do outro, coincidindo em alguma idéia principal geral. De fato, em anos diferentes, pessoas diferentes criam as mesmas classificações novamente, diferindo em detalhes não muito fundamentais.
Essa ideia algorítmica é encontrada com mais frequência do que outras.
Cada elemento é inserido
aproximadamente no local da matriz em que deve estar localizado. Acontece uma matriz
quase ordenada . À qual a classificação por inserções é aplicada (é mais eficaz para o processamento de matrizes quase ordenadas) ou áreas não ordenadas locais são processadas recursivamente pelo mesmo algoritmo.
Este artigo foi escrito com o apoio da EDISON, que desenvolve uma ampla gama de soluções para uma variedade de tarefas: desde programas para experimentação online de roupas de lojas multimarcas até um sistema de transmissão de LED entre embarcações fluviais e marítimas .
Adoramos a teoria dos algoritmos! ;-)
Para avaliar aproximadamente onde você deseja colocar o elemento, é necessário descobrir o quanto ele difere do elemento médio da matriz. Para fazer isso, você precisa conhecer os valores dos elementos mínimo e máximo e o tamanho da matriz.
A matriz classificada deve ter dados realmente aleatórios. Todos os inventores deste método vêm com a mesma fórmula:
k é o local aproximado da matriz em que o elemento
A (
i ) deve ser
min ,
max - valores dos elementos mínimo e máximo na matriz
ATamanho - o número de elementos na matriz
AAqui está uma ideia tão geral. Vamos ver em quais variações esse algoritmo nasceu várias vezes.
Classificação Rei Salomão :: Ordem Salomão
Este método (e seu belo nome) foi
proposto pelo usuário do
V2008n há cerca de 5 anos. Tudo tem seu tempo, “o tempo de espalhar pedras e o tempo de coletar pedras” (as palavras do rei Salomão do livro de Eclesiastes) - e no algoritmo, é exatamente isso que acontece. Primeiro, com a ajuda da fórmula, dispersamos os elementos nos locais desejados na matriz. Como a fórmula fornece um lugar não exato, mas aproximado, vários elementos que se aproximam em valor reivindicam algumas posições ao mesmo tempo. Esses grupos de elementos locais são classificados por inserções e depois montados na ordem final.
Classificação de interpolação
"Não há nada novo sob o sol", para citar o mesmo autor novamente. A Wikipedia descreve a classificação por interpolação, reminiscentemente suspeita da classificação de Salomão. Cada "pilha de pedras" é uma pequena matriz dinâmica adicional, onde estão localizados elementos de importância semelhante. A principal diferença é que, após a “dispersão de pedras”, esses grupos locais de elementos não classificados são classificados não por inserções, mas pela classificação por interpolação (recursivamente ou em loop).
Uma matriz ordenada é um conjunto de dados discreto que pode ser considerado como um conjunto finito de valores conhecidos de uma determinada função desconhecida. Na verdade, uma distribuição aproximada do ponto de vista da matemática computacional - isso é interpolação.
Classificação de interpolação JavaScript - loopbackArray.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); } } } } };
Classificação de interpolação JavaScript - versão 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();}
Classificação de histograma :: Classificação de histograma
Essa é uma otimização da classificação por interpolação, que conta o número de elementos pertencentes a grupos não classificados locais. Essa contagem permite inserir itens não classificados diretamente na matriz resultante (em vez de agrupá-los em pequenas matrizes separadas).
Classificação da barra JavaScript 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];} } } };
Classificação de tag de interpolação
Para otimizar ainda mais a sobrecarga, é proposto aqui não lembrar o número de elementos de importância semelhante em grupos não classificados, mas simplesmente marcar o início desses grupos com sinalizadores Verdadeiro / Falso. True significa que o subgrupo já está classificado e False significa que ainda não está.
Classificação de interpolação marcada com JavaScript Array.prototype.InterpolaionTagSort = function() { var end = this.length; if(end > 1) { var start = 0 ; var Tag = new Array(end);
Classificação de tag de interpolação (no local)
Se os valores dos elementos na matriz não forem repetidos e distribuídos uniformemente (grosso modo - se os dados na forma classificada forem algo como uma progressão aritmética), você poderá classificar em uma passagem, classificando no lugar certo, sem mover os elementos para matrizes intermediárias.
Classificar por interpolação com rótulos (no local) em 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; } } };
Classificação do Flash :: Flashsort
Uma vez,
escrevi sobre seleção, que foi inventada pelo professor de biofísica Neubert em 1998.
O professor sugeriu distribuir os elementos em várias classes separadas (a participação na classe é determinada pelo tamanho do elemento). Com isso em mente, a fórmula fica assim:
Em vez de Tamanho (tamanho da matriz), a fórmula indica
m - o número de classes pelas quais distribuímos os elementos da matriz. A fórmula não calcula a chave na matriz em que o elemento deve ser lançado, mas o número da classe à qual o elemento pertence.
Essa classificação não é ruim, pois é mais econômica em termos de memória adicional. A redistribuição de elementos ocorre no local. Somente a localização de classes é armazenada separadamente (bem, se você olhar de um ângulo diferente, o número de elementos pertencentes a uma classe específica é armazenado separadamente).
Bem, o resto é a mesma música.
Classificação Flash em 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();
Classificação aproximada :: classificação do Proxmap
Essa classificação é a mais antiga dentre as mencionadas aqui; foi introduzida em 1980 pelo professor Thomas Standish, da Universidade da Califórnia. Na aparência, parece ser significativamente diferente, mas se você olhar de perto, tudo será o mesmo.
O algoritmo opera com um conceito como um
acerto - um determinado número que é próximo em valor a algum elemento da matriz.
Para determinar se um elemento da matriz é um acerto, uma
função aproximada é aplicada ao elemento.
O professor Standish classificou matrizes de números reais. A função de aproximação era arredondar para baixo os números reais para um número inteiro.
Ou seja, por exemplo, se a matriz contiver elementos 2.8, 2, 2.1, 2.6 etc. então uma batida para esses números será deuce.
Procedimento geral:
- Aplicamos uma função aproximada a cada elemento, determinando qual ocorrência corresponde ao próximo elemento.
- Assim, para cada ocorrência, podemos calcular o número de elementos correspondentes a essa ocorrência.
- Sabendo o número de elementos para todos os hits, determinamos a localização dos hits (bordas à esquerda) na matriz.
- Conhecendo a localização dos hits, determinamos a localização de cada elemento.
- Depois de determinar a localização do elemento, tentamos inseri-lo em seu lugar na matriz. Se o local já estiver ocupado, movemos os vizinhos para a direita (se o elemento for menor que eles) para abrir espaço para o elemento. Ou, à direita, inserimos o próprio elemento (se for mais que vizinho).
Como uma função de aproximação, você pode atribuir qualquer um com base na natureza geral dos dados na matriz. Nas implementações modernas dessa classificação, as ocorrências geralmente são determinadas não mordiscando a parte fracionária, mas usando nossa fórmula favorita.
Classificação por aproximação do 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];} } }
Classificação de inserção de classificação de hash :: Classificação de hash
Bem, encerraremos nossa análise com o algoritmo
sugerido pelo habraiser
bobbyKdas há 6 anos. Este é um algoritmo híbrido no qual, além da distribuição e inserções, a mesclagem também é adicionada.
- A matriz é recursivamente dividida ao meio, até que, em algum momento, o tamanho das meias-sub-matrizes atinja o tamanho mínimo (o autor não possui mais de 500 elementos).
- No nível mais baixo de recursão, um algoritmo familiar é aplicado a cada semi-matriz - usando a mesma fórmula, ocorre uma distribuição aproximada dentro da matriz, com a classificação por inserções de seções locais não classificadas.
- Após o arranjo das duas metades, subarrays, elas se fundem.
- O ponto 3 (mesclagem de metades-subarranjos classificados) é repetido ao elevar os níveis de recursão até o topo, quando a matriz original é combinada de duas metades.
Classificar por inserção de hash em Java import java.util.Arrays; import java.util.Date; import java.util.Random; public class HashSort {
A própria fórmula é chamada de função hash, e a matriz auxiliar para distribuição aproximada é chamada de tabela hash.
Referências
Interpolação e Histograma ,
Flash ,
Proxmap
Salomão ,
Tabela De Hash ,
FlashArtigos da série:
A classificação por aproximação apareceu no aplicativo AlgoLab Excel (nesse caso, na matriz inicial não classificada, a parte fracionária aleatória é anexada aos números inteiros). Solomon e Flash estão lá há muito tempo, mas ainda não implementaram interpolação, hash e histograma.