A classificação e ordenação de dados sempre foi importante, sabendo-se que a ordenação dos mesmos nos ajudam na tomada de decisões e na visualização de determinada informação que os dados apresentados gostariam de nos passar, por exemplo, imagine uma lista de 1 a 17, onde você não soubesse que a mesma tem 17 elementos e precisasse contar, e essa lista está desordenada, como no exemplo abaixo:
Nesse caso, obviamente você procuraria o maior valor sabendo que ele está contando de 1 em 1, porém se ordenássemos essa lista a compreensão de seu tamanho, do maior e do menor número, não seria mais simples? É exatamente o que os métodos de ordenação fazem no seu código. Começando com o mais simples entre eles o de Bubble Sort, ou método de troca.
O que é Bubble Sort?
Bubble sort é um meio de ordenação de valores dentro de um determinado vetor, ele tem como principio o método de troca, ordenando um vetor inteiro, fazendo comparações entre os seus elementos. o código abaixo representa a ordenação de um vetor utilizando esse método de troca, no exemplo utilizamos a linguagem C++.
A saída desse programa apresenta os valores na ordem crescente:
Além desse método temos outros métodos de seleção:
Programinha para download aqui.
A saída desse programa apresenta os valores na ordem crescente:
Se alterarmos o sinal de ">" por um de "<" no nosso código teríamos exatamente o oposto desse resultado, ou seja, os valores em ordem decrescente.
Além desse método temos outros métodos de seleção:
- Distribuição (Bucket Sort);
- Inserção;
- Intercalação;
Distribuição (bucket sort)
Esse método também é conhecido como Bucket Sort (tipo de balde) ele ganha esse nome por dividir e classificar um vetor em determinados recipientes finitos e pré selecionados, realmente como se fossem baldes e você estivesse colocando conteúdo dentro deles, que obviamente uma hora iriam se encher e não caberiam mais elementos dentro deles, ele se comporta de uma maneira linear.
Abaixo um código exemplificando o uso de Bucket sort na linguagem C++.
Ordenação por inserção (Insertion Sort)
Esse método seria mais comum se a necessidade fosse a mesma de um jogador de cartas tentando ordenar o baralho em sua própria mão, usando a inserção das cartas na onde ele precisar. Se torna eficiente quando o número de elementos no vetor não é muito grande, pois ele percorre todos os elementos do vetor, da esquerda para a direita ordenando de maneira linear.
Abaixo um exemplo de código utilizando esse método:
Sabendo da lógica e funcionamento desse método podemos agora elaborar um algoritmo que faça o que o exemplo acima nos mostra.
A intercalação dos dados somente irá funcionar caso implementarmos uma função que "misture" os valores.
A função acima "MERGESORT" faz a intercalação dos dados em determinado vetor, levando em consideração p (posição do primeiro vetor) menor q r(que servirá de parâmetro para a intercalação dos vetores) - 1, devido as propriedades de vetores que se iniciam na posição “0”.
Então galera espero que tenha ficado claro o que cada método de ordenação faz, abaixo os links que utilizei para fazer essa Maravilhosa e Linda postagem pra vocês!
Fontes:
http://www.facom.ufms.br/~lianaduenha/sites/default/files/aula06_apostila.pdf
http://wiki.icmc.usp.br/images/b/b3/SCC501Cap4.pdf
http://www.trabalhosfeitos.com/topicos/metodos-de-ordena%C3%A7%C3%A3o-distribui%C3%A7%C3%A3o/0
https://pt.wikipedia.org/wiki/Bucket_sort
https://pt.wikipedia.org/wiki/Insertion_sort
Esse método também é conhecido como Bucket Sort (tipo de balde) ele ganha esse nome por dividir e classificar um vetor em determinados recipientes finitos e pré selecionados, realmente como se fossem baldes e você estivesse colocando conteúdo dentro deles, que obviamente uma hora iriam se encher e não caberiam mais elementos dentro deles, ele se comporta de uma maneira linear.
Abaixo um código exemplificando o uso de Bucket sort na linguagem C++.
Esse método seria mais comum se a necessidade fosse a mesma de um jogador de cartas tentando ordenar o baralho em sua própria mão, usando a inserção das cartas na onde ele precisar. Se torna eficiente quando o número de elementos no vetor não é muito grande, pois ele percorre todos os elementos do vetor, da esquerda para a direita ordenando de maneira linear.
Abaixo um exemplo de código utilizando esse método:
No código acima declaramos
um vetor de sete posições, o mesmo percorre todos os elementos de forma linear
tentando ordená-los para que sigam um padrão de classificação.
Temos a seguinte saída do
programa:
Na pior das hipóteses podemos ter um vetor totalmente desordenado, o que causaria um tempo de processamento muito alto, podendo causar impacto na aplicação, por isso é importante se lembrar que esse método se aplica bem a vetores de pequena escala, para que não tenhamos perda na performance em sua utilização.
Ordenação por Intercalação
Nesse método usamos uma técnica de divisão de vetores, deixando determinado vetor x em duas partes, e assim desmembramos ele até que o menor número possível de grupo, a partir daí ordenamos os grupos deixando-os ordenados da forma que quisermos (crescente, decrescente), depois de cada grupo ordenado podemos então começar a uni-los novamente sem esquecer que a ordenação do mesmo deve continuar de modo a ordenar o vetor inteiro "por partes". A imagem abaixo ilustra a explicação:
Ordenação por Intercalação
Nesse método usamos uma técnica de divisão de vetores, deixando determinado vetor x em duas partes, e assim desmembramos ele até que o menor número possível de grupo, a partir daí ordenamos os grupos deixando-os ordenados da forma que quisermos (crescente, decrescente), depois de cada grupo ordenado podemos então começar a uni-los novamente sem esquecer que a ordenação do mesmo deve continuar de modo a ordenar o vetor inteiro "por partes". A imagem abaixo ilustra a explicação:
Sabendo da lógica e funcionamento desse método podemos agora elaborar um algoritmo que faça o que o exemplo acima nos mostra.
A intercalação dos dados somente irá funcionar caso implementarmos uma função que "misture" os valores.
A função acima "MERGESORT" faz a intercalação dos dados em determinado vetor, levando em consideração p (posição do primeiro vetor) menor q r(que servirá de parâmetro para a intercalação dos vetores) - 1, devido as propriedades de vetores que se iniciam na posição “0”.
Então galera espero que tenha ficado claro o que cada método de ordenação faz, abaixo os links que utilizei para fazer essa Maravilhosa e Linda postagem pra vocês!
Fontes:
http://www.facom.ufms.br/~lianaduenha/sites/default/files/aula06_apostila.pdf
http://wiki.icmc.usp.br/images/b/b3/SCC501Cap4.pdf
http://www.trabalhosfeitos.com/topicos/metodos-de-ordena%C3%A7%C3%A3o-distribui%C3%A7%C3%A3o/0
https://pt.wikipedia.org/wiki/Bucket_sort
https://pt.wikipedia.org/wiki/Insertion_sort
Nenhum comentário:
Postar um comentário