Comparação de algoritmos de classificação de trocas

Este artigo discute várias opções para classificar trocas e também descreve um aplicativo gráfico simples ( processing.js ) com exemplos de classificações.

Antes de ler, recomendo que você leia os artigos do usuário valemak :

→ Classificação de trocas
→ Classificação de bolha e Tudo-Tudo-Tudo
→ Tipo bobo e algum outro mais inteligente

Classificação da bolha

A opção mais simples é iterar a matriz do primeiro para o último, trocando (se necessário) elementos vizinhos.

→ Confira aqui


Para mover o controle deslizante, você precisa clicar no botão cinza no canto inferior esquerdo.
Ao clicar no botão, mova o controle deslizante um passo para a direita

slider++; 

A seguir, verificamos: chegamos ao final da matriz (depois saltamos para o início) e comparamos (trocamos) os elementos vizinhos


Como o Processing.js usa estruturas de dados Java, o código é traduzido para javascript ( link ); portanto, a declaração de uma matriz de instâncias da classe Module, responsável por renderizar elementos e inicializar as instâncias, acontece assim

A principal função de desenhar void draw () é um loop infinito no qual as instâncias de classe são classificadas

 for (Module mod : mods) { mod.display(); } 

Adicione a função randFoo () , que retorna valores aleatórios. Para garantir que os valores não se repitam, vamos adicioná-los a ArrayLis t na lista listRand e na função randFoo () , verifique se o novo número aleatório está na lista listRand

 int randFoo(){ newRand = int(random(1,11)); if(!listRand.contains(newRand) ) listRand.add(newRand ); else newRand=randFoo(); return newRand; } 

→ Confira aqui

Classificação de pixels

A classificação de pixels (aqui) é uma implementação da classificação de bolhas.
Mudaremos os pixels mais quentes / mais claros para um lado e os mais escuros / mais frios para o outro

 void draw(){ while (i <= height) { c=get(i,j); //    cTemp=c; //      i++; //     c=get(i,j); //     if(cTemp>c) { //   fill(c); //    rect(i-1,j,1,1); fill(cTemp); rect(i,j,1,1); } } if(mousePressed) { if(j>=width) j=0; } //      if(i >= height) {j++; i=0;} } 

→ Confira aqui
Para começar a classificar, clique na imagem e mantenha pressionado o botão.
Você pode ler mais sobre a classificação de pixels aqui .
Vídeo sobre a classificação de pixels no canal oficial The Coding Train aqui

Limitador e bandeira

Você pode reduzir o número de iterações se não iterar sobre os itens já classificados. Para fazer isso, adicione um limitador ao final da matriz, que mudará para o início da matriz após cada iteração

 if(slider>=limiter) { slider=1; limiter--; if(limiter<1) limiter=1; } 

→ Confira aqui

Outra maneira de reduzir o número de bustos pode ser encontrada no artigo Bubble Sort (Wikipedia). Se durante a passagem da matriz nunca trocamos os elementos vizinhos, a matriz é classificada e o ciclo pode ser concluído (condição Iverson ).

Adicione um sinalizador de bandeira , que é levantado quando encontramos alguns elementos que precisam ser trocados. Se o sinalizador for levantado, itere sobre a matriz novamente. Caso contrário, termine o ciclo. O estado do sinalizador é exibido no console



→ Confira aqui

Se você colocar um limitador à esquerda e usar um elemento com um limitador como referência / mínimo, obteremos a classificação por seleção.

Adicione a variável min na qual o valor mínimo será carregado. Suponha que inicialmente o elemento mais à esquerda seja mínimo: durante a primeira passagem da matriz, se um elemento for menor que o mínimo, salvaremos esse elemento na variável min

 if(mods[slider-1].rectHight < min){ min=mods[slider-1].rectHight; } 

então troque o primeiro elemento e o mínimo

 if (mods[limiterL-1].rectHight>min) { vTemp= mods[limiterL-1].rectHight; mods[limiterL-1].rectHight=mods[slider-1].rectHight; mods[slider-1].rectHight=vTemp; } 

Se o controle deslizante atingir a borda direita da matriz, o limitador se moverá um passo para a direita e o controle deslizante se moverá para o limitador

 if(slider==moduleSize){ if(limiterL<moduleSize) limiterL++; min=mods[limiterL-1].rectHight; incPaddle=limiterL-1; } 

→ Confira aqui
O número de medidas pode ser reduzido se, no início da pesquisa, compararmos (trocarmos) o elemento atual e o elemento mais à direita da matriz

 if(mods[limiterL-1].rectHight>mods[moduleSize-1].rectHight) { vTemp=mods[limiterL-1].rectHight; mods[limiterL-1].rectHight=mods[moduleSize-1].rectHight; mods[moduleSize-1].rectHight=vTemp; } 

Então você não pode verificar o elemento mais à direita da matriz

 //if(slider==moduleSize){ if(slider==moduleSize-1){ //if(limiterL<moduleSize) limiterL++; limiterL++; min=mods[limiterL-1].rectHight; slider=limiterL-1; } // slider++; if(slider<moduleSize) slider++; 

→ Confira aqui

Aqui você pode adicionar a classificação da parte direita da matriz em ordem decrescente, adicionando o elemento máximo max - obtemos a classificação do shaker por seleção. Veja a seção sobre classificação dos shakers no final do artigo.

Classificação rápida

O mecanismo de seleção de elemento de suporte também é usado na classificação rápida. Esse algoritmo envolve a seleção do elemento de referência inicial com o qual todos os outros elementos da matriz são comparados. O tempo de execução do algoritmo depende da escolha do elemento inicial. No gif acima, o elemento inicial é o número 3 . Você pode ler mais sobre como escolher o elemento de suporte inicial no artigo (Wikipedia).
Um vídeo sobre classificação rápida está disponível no canal oficial do youtube dos idiomas de processamento e p5.js. Aqui você pode ver a visualização do algoritmo.
Se o primeiro elemento for básico, você poderá inserir elementos menores que o básico à sua frente, a matriz será dividida em duas partes, os elementos à esquerda serão menores que o básico, à direita - mais. Para esse método, consulte a seção sobre classificação por inserções abaixo.

Classificação dos Anões

Essencialmente, o gnomo examina os próximos e anteriores vasos de jardim: se estiverem na ordem correta, ele avança um vaso, caso contrário, ele os troca e recua um vaso.

Depois de levantar o sinalizador, salve a coordenada do controle deslizante na variável limitadorR e retorne o controle deslizante para o início da matriz em etapas

 slider--; 

Uma vez no início da matriz, redefina o sinalizador e coloque o controle deslizante na célula com a coordenada que salvamos na variável limitatorR

 if(slider==0){ flag=false; slider=limiterR; } 

→ Confira aqui

Ao alterar esse algoritmo, obtemos " classificação por inserções ".
Na classificação por inserções, o elemento de referência / mínimo é selecionado e, na parte não classificada da matriz, o elemento é selecionado, menor que a referência e inserido antes da referência

Vamos ter o mínimo de troca de elementos com os anteriores, até o de referência, e assim por diante. inserido na frente da referência.
Adicionar uma condição

 if(slider==limiterR-1 && mods[slider-1].rectHight<mods[limiterR-1].rectHight){ flag=false; slider=limiterR; } 

→ Confira aqui


Classificação de inserção "rápida"

Nesse algoritmo, o array é dividido em duas partes pelo elemento de suporte.
Seja o primeiro elemento a referência: compare, começando pelo segundo, os elementos da matriz com a referência, se um elemento for menor que a referência

 if(mods[slider-1].rectHight < mods[pivot-1].rectHight) 

insira o elemento encontrado antes da referência

 if(mods[slider-1].rectHight < mods[pivot-1].rectHight){ flag=true; //   vTemp= mods[slider-1].rectHight; mods[slider-1].rectHight=mods[slider-2].rectHight; mods[slider-2].rectHight=vTemp; } 

Se a bandeira estiver levantada, mova o controle deslizante para a esquerda em etapas até encontrarmos o elemento de suporte

 if(flag){ slider--; if(slider<pivot){ flag=false; //   pivot++; slider=pivot; } } 

T.O. a matriz é dividida em duas partes, à esquerda - os elementos são menores que a referência, à direita - mais

→ Confira aqui

Se, após cada enumeração, as coordenadas do elemento de suporte forem salvas em pivotsArr array, quando o elemento de referência atinge a borda direita, obtemos um array classificado por nível / etapa. Os elementos em cada próximo nível serão maiores que os elementos no nível anterior. Os limites dos níveis serão contidos em add. pivotsArr array
Cada vez que você clica no botão, enviaremos o array pivotsArr para o console

 for(int i=0;i<pivotsArr.length;i++){ print(" "); print(pivotsArr[i]); print(" "); } 

Adicione a função aleatória randFoo () ao final do programa.

→ Confira aqui

Agora você precisa classificar os elementos de cada nível separadamente (resta apenas adicionar a condição para finalizar o ciclo)

→ Confira aqui
Essa classificação pode ser descrita como classificação por nível.
, porque após cada enumeração, os dados numéricos são organizados em níveis, os números de cada próximo nível excedem os números do anterior.

Classificação ímpar

Vamos mover o controle deslizante em duas etapas, comparando elementos vizinhos

 slider=slider+2; 

T.O. comparamos os elementos 0 e 1, 2 e 3, 4 e 5, 6 e 7, etc.
Se o controle deslizante atingir a borda da matriz, deixe o limitador mover um passo para a esquerda e o controle deslizante para o início da matriz.
Em seguida, comparamos os elementos 1 e 2, 3 e 4, 5 e 6, 7 e 8, etc.
Tendo atingido o limitador, mudamos um passo para a direita e colocamos o controle deslizante no início da matriz.

→ Confira aqui

Classificar escova de cabelo

Deixe o controle deslizante no início da matriz e o delimitador correto no final. Compare elementos (swap). Movemos o limitador um passo para a esquerda e salvamos seu índice na variável limiterStore

 if(limiter==moduleSize) { limiter = limiterStore-1; limiterStore = limiter; slider=1; } 

Mova o controle deslizante com a parada até o final da matriz em etapas

 if(limiter!=moduleSize) { //  limiter     limiter++; slider++; } 

Tendo atingido o final da matriz como um limitador, coloque o controle deslizante no início da matriz e coloque o limitador em limititerStore-1

 if(limiter==moduleSize) { limiter = limiterStore-1; limiterStore = limiter; slider=1; } 

→ Confira aqui

Shaker sort

Adicione o limitador esquerdo limiterL ao início da matriz.
Deixe a bandeira aparecer quando o controle deslizante atingir o limitador direito limitatorR , então o limitador se move um passo para a esquerda. Além disso, quando a bandeira é levantada, o controle deslizante se move em etapas para o limitador esquerdo do limitador L - o limitador se move um passo para a direita - o controle deslizante se move em passos para a direita


→ Confira aqui

Shaker ordenar por escolha
Adicione à classificação de bolhas com o limitador direito o limitador esquerdo. A cada deslocamento do controle deslizante para a direita, verificamos (swap) o que é maior - o elemento ou limitador atual

 if(mods[slider-1].rectHight<mods[limiterL-1].rectHight){ vTemp= mods[slider-1].rectHight; mods[slider-1].rectHight=mods[limiterL-1].rectHight; mods[limiterL-1].rectHight=vTemp; } 

Quando o controle deslizante atinge o limitador direito do limitador R , o limitador direito move um passo para a esquerda, o limitador esquerdo move um passo para a direita e o controle deslizante retorna para o limitador esquerdo

 if(slider>=limiterR){ limiterL++; slider=limiterL; limiterR--; } 

→ Confira aqui

PS É aqui que um aplicativo é descrito, o que torna o estudo de algoritmos e estruturas de dados muito mais interessantes .
Outra visualização de vários algoritmos e estruturas de dados.
Este artigo menciona outro site onde você pode ver como os dados são classificados por diferentes algoritmos.
Este artigo faz uma avaliação da complexidade da classificação de bolhas.
Mais informações sobre a avaliação da complexidade podem ser lidas aqui , aqui , aqui , aqui .