Aprendendo a escolher bem o que por em ordem - O algoritmo Selection Sort

Olá ! Meu nome é João Paulo Maida e bem-vindos ao blog Preciso Estudar Sempre.

Ordenar é de fato uma tarefa que às vezes nos deixa de cabelos em pé. Na literatura existem vários algoritmos que podem nos ajudar, cada um com suas características. As opções são tantas que o problema muda de achar uma solução para qual solução escolher.

Como já vimos aqui em várias situações, o que vai determinar a solução necessária para um certo problema é, de fato, o problema. Logo, se velocidade é o seu problema vá para o Quick Sort, mas se o problema for lidar com partes já ordenadas, use o Insertion Sort (clique aqui para dar uma lida), e assim segue.

Um dos algoritmos primordiais ensinados, seja na faculdade ou no cursinho técnico, é o Bubble Sort (clique aqui). Ele, junto com Insertion Sort e Selection Sort, compõem uma categoria conhecida como “Algoritmos de ordenação simples”. Não vá achando que simples signifique inútil. Ao contrário, esses algoritmos servem como base para algoritmos mais complexos como Quick Sort, Merge Sort e Shell Sort. O que difere a categoria dos básicos para dos complexos são as técnicas e estruturas de programação utilizadas.

Nosso foco hoje será exclusivamente o Selection Sort para assim fechar a categoria dos simples. Abordaremos seu conceito, sua implementação e características.

Imagine que exista uma fileira de lápis que possuem vários tamanhos e você quer por eles em ordem porque, assim como eu, tem TOC.

Figura 1 - Lápis desordenados

Para ordenar esses lápis utilizando a técnica do Selection Sort marcamos o primeiro lápis (à esquerda) com um marcador indicando que aquele é o menor lápis encontrado no momento. Após isso, verificamos um após o outro até o fim, a fim de encontrar algum lápis menor. Quando encontrado, é marcado como o menor lápis encontrado até o momento, mas a busca continua até o fim do conjunto. Caso algum lápis menor ainda seja encontrado, o marcador é movido para este. Caso contrário, a troca já pode ser feita e, o ciclo de ordenação do primeiro lápis está concluído. O marcador vai para o segundo lápis do conjunto. 

No exemplo acima, o menor lápis encontrado em uma primeira instância seria o quarto, porém finalmente o sétimo seria revelado como o menor de todos. Os marcadores iriam ser movidos do primeiro para o quarto e posteriormente para o sétimo. Após finalizado o ciclo, o marcador voltaria para o segundo lápis para assim iniciar um novo ciclo, e este processo se repete até o conjunto todo estar ordenado.

A Figura 2 é um GIF animado que mostra todo o processo sendo feito.

Figura 2 - Funcionamento do algoritmo SelectionSort

Visto que já cobrimos toda a parte teórica do assunto, podemos partir para a prática.

Quem acompanha o blog sabe que eu sempre escolho a linguagem Java como alvo das minhas implementações, mas como o grande Mário Sérgio Cortela já diz:

Mudar é complicado mas acomodar é perecer (Cortella, Mário Sérgio).

Vamos implementar o nosso algoritmo em Javascript, afinal de contas é uma linguagem que funciona em todos os navegadores de todos os dispositivos, sejam eles computadores, notebooks, celulares ou tablets; e não é necessário um ambiente tão complexo de execução igual ao do Java.

1 2 3 4 5 6 7 8 9

for(out=0; out<qtd-1; out++){ marcador = out; //primeiro elemento marcado for(ins=out+1; ins<qtd; ins++){ //varro os itens a direita procurando o menor de todos if(valores[ins] < valores[marcador]){ //encontrado item menor ? marcador = ins; //move o marcador } } _trocar(out, marcador); //acabaram os dois laços então posso fazer a troca }

(LAFORE, ROBERT)

Note que o algoritmo é bem simples, não há nada extremamente complexo. Os dois laços for orquestram o processo descrito nos parágrafos acima. O primeiro começando do início e o segundo iniciando a partir do ponto de partida do primeiro, ou seja, se o primeiro laço começa em 0, o segundo começará em 1. Contudo, note que o primeiro laço só vai até qtd-1, porque ? Porque não ir até qtd ?

A resposta é simples se pararmos para analisar a situação como um todo. Com as consecutivas trocas dos valores, os maiores (no caso de ordenação crescente) são sempre jogados para o fim e o maior valor terá seu lugar trocado com alguém menor que ele, ocupando assim o último lugar. Por tais motivos não é necessário que o laço mais externo percorra todas posições do array.

Os nomes das variáveis controladoras de laço foram escolhidas devido ao fato de existirem um laço externo e um interno, logo respectivamente out e ins. O resto do código está bem claro e dispensa maiores explicações.

A ordenação por seleção executa o mesmo número de comparações que a ordenação pelo método bolha: N*(N-1)/2. Para grandes valores de N, os tempos de comparação predominarão, portanto a ordenação por seleção executa em tempo de O(n²), exatamente como a ordenação em bolha. Contudo, ela tende a ser bem mais rápida porque há poucas trocas. Para valores menos de N, a ordenação por seleção pode ser de fato mais rápida, especialmente se os tempos de troca forem muitos maiores que os tempos de comparação (LAFORE, ROBERT).

Chegamos ao fim de mais um post meus amigos. Espero que tenham gostado. Caso tenham sentido falta de algum detalhe, deixe nos comentários.

Até a próxima minha boa gente ! 😘

Leia nossa postagem anterior: Cuidado com os comentários, eles são perigosos !!!

Dúvidas !? Sugestões ?! Críticas ou elogios ?!

Deixe aí nos comentários, envie um e-mail ou uma mensagem na nossa página do Facebook.

Download no GoogleDrive: clique aqui
Download no Dropbox: clique aqui

E-mail: precisoestudarsempre@gmail.com
Facebook: https://www.facebook.com/precisoestudarsempre/
Canal Preciso Estudar Sempre: https://www.youtube.com/channel/UCUoW8dS38rXr0a5jWU57etA

Referências

Cortella, Mário Sérgio; Mudar é complicado? Acomodar é perecer.; https://www.youtube.com/watch?v=Ry3_5Pl8qmk

LAFORE, ROBERT; Estruturas de Dados e Algoritmos em Java; 2004