Algoritmos de Classificação e Ordenação 

Salve padawan, feliz dia do Programador no artigo de hoje, neste agradável e calorento domingo de finais de inverno vamos falar sobre algoritmos de classificação, no seu dia a dia de trabalho, provavelmente o líder da equipe de desenvolvimento, irá comentar e solicitar que deve desenvolver um aplicativo que classifique uma determinada quantidade informações.

Veras que curiosamente 90% do software produzido em sua carreira, consiste em balance lines e classificações de dados, coisas bem maçantes, mas muito importante afinal para tomar a decisões os gestores dependem da informação, quanto melhor mais eficaz a decisão.

Por isso deve sempre garantir a ordenação, a duplicação e a fiabilidade dos outputs de nosso programa, independente a origem Web / Big Data / Cloude / Mobile e ou captura local. Está preparado para este mergulho?

Existem dois tipos de algoritmo de ordenação divididos em diversos subdivisões: Simples e Complexas, o escopo deste artigo é o método Simples e suas subdivisões: Insertion, sort, Selection sort, Bubble sort, Comb sort e Bogo sort.

O que significa Ordenação e Classificação de Arrays?

Como fazemos isto desde a mais terna idade, não nos apercebemos da complexidade de classificar e ordenar uma lista de dados. Nos humanos ao batermos os olhos, rapidamente nosso cérebro, ordena, classifica e rearranja uma lista.

Porém o computador necessita de ajuda, necessita que codifiques a maneira exata de como fazer, através de passo a passo, normalmente utilizando pseudocódigo, fluxogramas e por fim código na linguagem de programação de sua preferência.

Num exemplo simples, veja a seguinte lista 6,3,2,1,7,8,9,0. Tente elaborar um algoritmo que ordene a lista exemplo de forma crescente, partindo do 0 até o 9. Agora pense num algoritmo para ordem decrescente do 9 ao 0. Outra vez, agora ordene a lista primeiros pelos pares do menor para o maior e os impares do maior para menor.

Sentiu o drama? Complexo? Por isso as mentes brilhantes na engenharia de software criaram ao longo do tempo, metodologias de criarem algoritmos para auxiliarem em cada solução.

O que são os Métodos Simples e Complexo?

Esta classificação surgiu devido a complexidade dos códigos envolvidos, explicitamente o Simples, é mais fácil para os novatos, gerando algoritmos mais fáceis de codificar e de entender, não necessitando de cálculos complexos.

O Método Complexo como o próprio nome diz, tem algoritmos mais elaborados, porém muito mais velozes e performáticos, exigindo mais raciocínio logico e conhecimento de programação.

Este preparado? O tiozão vai tentar ser claro e simples, se eu viajar muito ou complicar demais, chama no discord ou nos comentários, com isso refinamos, lapidamos e deixamos o artigo mais claro e acessível.

Tipos de ordenações simples

Este artigo não é exaustivo, dentro do método simples listarei os 4 mais comumente usados:

• Insertion Sort
• Selection Sort
• Bubble Sort
• Bogo Sort

Método de Ordenação Insertion Sort

Um dos métodos mais fáceis de codificar, performático para pequenas quantidades de dados, este método funciona através de inserção e comparação de itens. Um inconveniente é forçar a leitura do array inteiro, gerando N realocações a depender do grau de distribuição dos elementos.

Ele funciona selecionando o item a ser inserido e comparando-o com o item na lista, se for maior, insere na posição N+1, lendo os próximos itens e comparando com a posição 1 até encontrar o menor ou final da lista.

Um inconveniente é que este procedimento é repetido na ordem N X N (pior caso),( (N x) N / 4)) caso médio e N para o melhor caso, por isso para grandes quantidades de dados movimentados sua performance cai sensivelmente, indicando a utilização de outro algoritmo.

A sua principal vantagem é ser de fácil implementação, fácil manutenção e utiliza pouca memória em tempo de execução, limitando-se a uma comparação, um ponteiros e duas listas, porém gera muitas trocas e rebalanceamento.

Método de Ordenação Selection Sort

Um método de complexidade media, onde a sua execução necessita de N x N, em qualquer situação, pois ele funciona através da ordenação de uma lista, efetuada através de dois laços for e uma comparação, onde movemos o menor item para o início da lista e reposicionamos o ponteiro sucessivamente até o fim da lista.

Sua performance é baixa para listas grandes, obrigando inúmeras comparações e não tem reaproveitamento de ponteiro, forçando o uso de cpu e memória, porém para pequenas listas é o melhor a ser utilizado, pois usa o mínimo de código e alocação de memória.

Método de Ordenação Bubble Sort

Um nome divertido para um método de ordenação excêntrico, evoluindo de simples para uma complexidade quadrática conforme o tamanho da lista. Tem esse nome, devido a característica do processamento, que empurra os itens maiores para o topo através da “flutuação”, lembrando o movimento das bolhas de sabão.

Seu funcionamento vai percorrendo a lista e comparando os itens de 2 em 2, 4 em 4 a depender da implementação e com isso ordenando a lista, até que nenhum item seja movimentado

Método de Ordenação Bogo Sort

É baseado na reordenação aleatória dos elementos, coloquei este método a título de curiosidade acadêmica, pois não é eficiente e provavelmente nunca iras codifica-lo, pois é meio absurdico e anedótico. Seu nome deriva de quantum bogodynamics, também chamado de CaseSort e jocosamente de Estou com Sort, pois usa a probabilidade para ordenar uma lista, sendo totalmente ineficiente e usar muitíssima memória e CPU.

Quem ficou curioso, recomendo googlearem o Teorema do Macaco Infinito e surpreendam-se com as combinações infinitas, que podem gerar resultados interessantes.

Bônus

Grato pela paciência vamos falar sobre as mais comuns dos algoritmos de seleção e ordenação, com os conhecimentos adquiridos neste artigo pode usar qualquer um deles:

Método de Ordenação Balance Line

O balance line funciona classificando e ordenando duas listas, iniciando os dois ponteiro e comparando-o s, a partir deste ponto navegamos na lista 1 ou na lista 2, até parear os itens, reiniciando o fluxo até o final do arquivo. Para o seu bom funcionamento a premissa básica é que as duas listas estejam ordenadas pela mesma ordem. Desta forma podemos fazer o merge das informações de maneira eficiente e rápida.

1. Verificar listas
1.1. Posicionar ponteiro primeiro da lista 1
1.2. Posicionar ponteiro primeiro da lista 2
1.3. Se não haver dados em alguma das listas, encerra a classificacao
2. Faz comparação com os ponteiros lidos das listas (realizar o balance-line)
2.1. Se item da lista 1 igual ao item da lista 2
  2.1.1. Inserir item lista 2 na lista lista 1
  2.1.2. Posicionar no proximo ponteiro lista 2
2.2. Se item Lista 1 maior que item da lista 2, 
  2.2.1. Inserir item lista 2 na lista lista 1
  2.1.2. Posicionar no proximo ponteiro lista 2
2.3. Se item Lista 1 menor que item da Lista 2
  2.3.1. Posicionar no proximo ponteiro lista 1

Conclusão 

O objetivo deste artigo foi apresentar de forma interativa os conceitos sobre classificação de listas e arrays, apresentado os principais algoritmos simples para uso no cotidiano do desenvolvimento de software, lembrando que em praticamente todas as aplicações desenvolvidas necessitaremos de ordenar ou reordenar alguma informação.

Por fins didáticos apresentei as versões resumidas e deixo ao jovem padawan, a missão de explorar e descobrir maiores informações testando sua utilização em codificação e vendo qual o melhor método para as suas necessidades.

Espero ter ajudado ate o próximo artigo.

 Mais momento jabá, para distrair, visite meu vídeo e veja para onde fui desta vez: https://www.youtube.com/watch?v=Puld-d0JVIM

Bom curso a todos.

 https://www.linkedin.com/in/vagnerbellacosa/

 https://github.com/VagnerBellacosa/

Pode me dar uma ajudinha no YouTube?

 https://www.youtube.com/user/vagnerbellacosa