As linguagens de programações atuais, esbanjam praticidade quando o assunto é ordenação de listas.
Com pouquíssimas linhas como mostrado aqui em posts anteriores, podemos ordenar nossas listas.
Para quem gosta de brincar com algoritmos, vamos desenvolver neste pequeno tutorial o Algoritmo Bubble Sort, bastante conhecido.
É interessante se conhecer a forma de aplicar tais algoritmos, pois não é em todas linguagens que temos tanta praticidade para ordenar listas.
Conhecer um algoritmo de ordenação, como o Bubble Sort, por exemplo, é uma boa ideia quando se trabalha programando para dispositivos com capacidades computacionais reduzidas como microcontroladores.
Conhecendo o Algoritmo Bubble Sort
No vídeo abaixo, um grupo de dança demonstra de forma muito bem humorada o funcionamento do Algoritmo Bubble Sort:
O algoritmo consiste basicamente em ordenar um vetor de n posições, a partir de pequenas partes do mesmo.
O algoritmo varre o vetor, ordenando os pares. Como demonstra a figura abaixo:
Mais informações podem ser encontradas no Site da Wikipedia.
Bubble Sort com JAVA
Abaixo, descrevemos um código que carrega um vetor carregado com números aleatoriamente.
/**
* Preenche o vetor com numeros aleatórios
*/
for (int i = 0; i < vetor.length; i++) {
vetor[i] = (int) (Math.random() * 100);
}
Após executa um método que exibe o vetor (ainda fora de ordem) na tela.
/**
* Metodo que recebe um vetor e exibe o mesmo na tela
*/
private void exibeVetor(int[] v) {
System.out.println("\n");
for (int i = 0; i < v.length; i++) {
System.out.print(v[i] + " ");
}
}
Agora é hora da mágica! O método abaixo ordena o vetor, verificando os valores contidos nos índices e comparando-os com os valores do próximo índice. Caso o valor do índice atual for menor do que do índice posterior, ele inverte a posição dos mesmos, com o auxilio de uma variável de controle.
/**
* Metodo responsavel por varrer o vetor e ordenar os pares
*/
private void ordenaBubbleSort(int[] v) {
for (int i = 0; i < v.length; i++) {
/**
* Caso o índice atual do vetor for o ultimo, não precisa ordenar
*/
if (i != v.length - 1) {
/**
* Verifica se os valores não estão em ordem crescente
*/
if (!(v[i] <= v[i + 1])) {
/**
* atribui o valor do indice a uma variavel temporaria
*/
int valorTemp = v[i];
/**
* coloca o valor do proximo indice no indice atual
*/
v[i] = v[i + 1];
/**
* atribui o valor da variavel temporaria no proximo indice
*/
v[i + 1] = valorTemp;
}
}
}
if (!isVetorOrdenado(v)) {
ordenaBubbleSort(v);
}
}
O método abaixo verifica se o vetor esta em ordem.
/**
* Metodo que verifica se o vetor está em ordem
* Retorna 'true' se estiver atualizado
*/
private boolean isVetorOrdenado(int[] v) {
for (int i = 0; i < v.length; i++) {
/**
* Caso o índice atual do vetor for o ultimo, não precisa ordenar
*/
if (i != v.length - 1) {
/**
* Verifica se o indice atual e o próximo estão ordenados;
*
* Caso estejam, checa os proximos indices
*/
if (!(v[i] <= v[i + 1])) {
return false;
}
}
}
return true;
}
Finalmente, acrescentamos o trecho abaixo, no final do método ordenaBubbleSort(), de forma a definir se é ou não necessária a recursão.
if (!isVetorOrdenado(v)) {
ordenaBubbleSort(v);
}
Após, evocamos finalmente o método exibeVetor() para mostrá-lo na tela.
Abaixo a classe completa, já com o método main();
package bubblesort;
public class BubbleSort {
/**
* Constante com o tamanho do vetor a ser criado
*/
public static final int TAMANHO_VETOR = 11;
public static void main(String[] args) {
BubbleSort bubbleSort = new BubbleSort();
int[] vetor = new int[TAMANHO_VETOR];
/**
* Preenche o vetor com numeros aleatórios
*/
for (int i = 0; i < vetor.length; i++) {
vetor[i] = (int) (Math.random() * 100);
}
bubbleSort.exibeVetor(vetor);
bubbleSort.ordenaBubbleSort(vetor);
bubbleSort.exibeVetor(vetor);
}
/**
* Metodo responsavel por varrer o vetor e ordenar os pares
*/
private void ordenaBubbleSort(int[] v) {
for (int i = 0; i < v.length; i++) {
/**
* Caso o índice atual do vetor for o ultimo, não precisa ordenar
*/
if (i != v.length - 1) {
/**
* Verifica se os valores não estão em ordem crescente
*/
if (!(v[i] <= v[i + 1])) {
/**
* atribui o valor do indice a uma variavel temporaria
*/
int valorTemp = v[i];
/**
* coloca o valor do proximo indice no indice atual
*/
v[i] = v[i + 1];
/**
* atribui o valor da variavel temporaria no proximo indice
*/
v[i + 1] = valorTemp;
}
}
}
if (!isVetorOrdenado(v)) {
ordenaBubbleSort(v);
}
}
/**
* Metodo que verifica se o vetor está em ordem
* Retorna 'true' se estiver atualizado
*/
private boolean isVetorOrdenado(int[] v) {
for (int i = 0; i < v.length; i++) {
/**
* Caso o índice atual do vetor for o ultimo, não precisa ordenar
*/
if (i != v.length - 1) {
/**
* Verifica se o indice atual e o próximo estão ordenados;
*
* Caso estejam, checa os proximos indices
*/
if (!(v[i] <= v[i + 1])) {
return false;
}
}
}
return true;
}
/**
* Metodo que recebe um vetor e exibe o mesmo na tela
*/
private void exibeVetor(int[] v) {
System.out.println("\n");
for (int i = 0; i < v.length; i++) {
System.out.print(v[i] + " ");
}
}
}
Nenhum comentário:
Postar um comentário