ORDENAÇÃO E MÉTODO BOLHA
1) Ordenar é um processo de rearranjar um conjunto de objetos em uma ordem ascendente/crescente ou descendente/decrescente. Qual a importância da ordenação para qualquer processo e para informática? Dê exemplos práticos de utilização. Defina a complexidade dos métodos de ordenação e a sua classificação.
Resposta:
Ordenam-se os dados para ganharmos velocidade na execução de tarefas. Dados ordenados consomem menos tempo de processamento.
2) Qual é a classificação dos métodos de ordenação? Qual a diferença entre eles? Quais são os métodos de ordenação mais utilizados ou principais?Resposta:
Tipos de algoritmos de ordenação
• Por troca: Troca os elementos ordenando-os
• Por seleção: Seleciona o menor elemento, o segundo menor e assim por diante
• Por inserção: Reinsere os elementos na estrutura reordenando os mesmosExemplos:
Método Bolha (BubbleSort): Troca os elementos de um arrayPercorre todo array x-1 vezes, onde x é o tamanho do array, trocando os elementos adjacentes, se estiverem desordenados
Método Seleção (SelectionSort): Seleciona o elemento de menor valor e o troca pelo primeiro. Faz-se o mesmo com os elementos restantes.
Executa-se o processo tantas vezes quanto o número de elementos no array menos um – varre o array a partir dos elementos ainda não ordenados
Método Inserção (InsertionSort): Reinsere os elementos no array reordenando o mesmo
Ordena os dois primeiros elementos
Do terceiro elemento em diante, os valores são inseridos em relação aos elementos já ordenados.
3) A ordenação pelo método bolha é um dos mais simples. Qual a principal característica do método ou como ele funciona?
Resposta:
A ideia é percorrer o vetor diversas vezes, a cada passagem fazendo flutuar para o topo o menor elemento da sequência. Os valores maiores afundam para o fundo (fim do vetor). Essa movimentação lembra a forma como as bolhas em um tanque de água procuram seu próprio nível, e disso vem o nome do algoritmo.
A técnica consiste em sequencialmente cada um dos elementos do vetor, comparando os elementos vizinhos entre si. Caso estejam fora de ordem, os mesmo trocam de posição (swap).
Procede-se assim até o final do vetor. Na primeira “varredura” o último elemento do vetor estará no seu devido lugar (caso a ordenação seja crescente, ele é o maior de todos).
A segunda “varredura” é análoga à primeira e vai até o penúltimo elemento.
O processo é repetido até que tenham sido feitas tantas “varreduras” quanto o número de elementos a serem classificados menos um.
Ao final o vetor estará classificado segundo o processo escolhido.
4) Qual é a classificação do método bolha? Qual o seu grau de complexidade?
Resposta:
O Método Bolha possui uma Classificação por “troca”. Seu Grau de Complexidade é considerado Simples, pois trabalha como um único modo: Ele compara todos os pares de elementos consecutivos e enquanto houverem pares não ordenados, ele continuará varrendo e operando. Assim que uma varredura não retorna nenhum par desordenado, o Vetor está pronto.
5) Dê exemplo de aplicação do método bolha, com as comparações, trocas e interações.
Resposta:
Exemplo:
método da bolha, pode ser aplicado a uma lista de números, consistindo, inicialmente, na comparação entre os dois primeiros números ( os das posições 1 e 2 ). Se o da posição 1 for maior que o da posição 2, efetuamos uma troca. Caso contrário eles permanecem em suas posições originais. Em seguida, comparamos os das posições 2 e 3 e agimos como antes: só efetuamos a troca se o da posição 2 for maior que o da posição 3, e assim por diante com os números das posições 3 e 4, 4 e 5, ... até efetuarmos a comparação entre aqueles que ocupam as posições 7 e 8.
Com isso deslocamos o maior deles para a última posição ( a posição 8, mais à direita ). O maior número, por assim dizer, "borbulha" para a posição "mais elevada", como as bolhas, em um líquido, elevam-se para a sua superfície. A simulação adiante ilustra o processo completo para o leitor. Como nas simulações anteriores, os números que estarão sendo comparados serão representados em vermelho e aqueles que já tenham atingido sua posição final, em azul.
Situação inicial: 37, 22, 47, 81, 16, 59, 47, 64
PRIMEIRO PASSO: Efetuar as comparações antes descritas, com a finalidade de colocar o maior dos números na posição 8:
1ª comparação: 22, 37, 47, 81, 16, 59, 47, 64 Trocaram-se 22 com 37
2ª comparação: 22, 37, 47, 81, 16, 59, 47, 64 Permanecem, pois 37<47
3ª comparação: 22, 37, 47, 81, 16, 59, 47, 64 Permanecem, pois 47<81
4ª comparação: 22, 37, 47, 16, 81, 59, 47, 64 Trocaram-se 16 com 81
5ª comparação: 22, 37, 47, 16, 59, 81, 47, 64 Trocaram-se 59 com 81
6ª comparação: 22, 37, 47, 16, 59, 47, 81, 64 Trocaram-se 47 com 81
7ª comparação: 22, 37, 47, 16, 59, 47, 64, 81 Trocaram-se 64 com 81
Com a seqüência de comparações e trocas anteriores, o número 81 (o maior da lista) "borbulhou" para a posição 8.
SEGUNDO PASSO: Tomando-se a situação final do passo anterior como inicial, vamos fazer "borbulhar" um segundo número (menor ou igual ao que já se encontra na posição 8) para a posição 7:
Situação inicial: 22, 37, 47, 16, 59, 47, 64, 81
1ª comparação: 22, 37, 47, 16, 59, 47, 64, 81 Permanecem, pois 22<37
2ª comparação: 22, 37, 47, 16, 59, 47, 64, 81 Permanecem, pois 37<47
3ª comparação: 22, 37, 16, 47, 59, 47, 64, 81 Trocaram-se 16 com 47
4ª comparação: 22, 37, 16, 47, 59, 47, 64, 81 Permanecem, pois 47<59
5ª comparação: 22, 37, 16, 47, 47, 59, 64, 81 Trocaram-se 47 com 59
6ª comparação: 22, 37, 16, 47, 47, 59, 64, 81 Permanecem, pois 59<64
Encerra-se o segundo passo, com a posição 7 ocupada pelo número 64.
TERCEIRO PASSO: Como o leitor já percebeu, nosso objetivo é transferir um número ( menor ou igual ao 64 ) para a posição 6, partindo da última seqüência do passo anterior.
Situação inicial: 22, 37, 16, 47, 47, 59, 64, 81
1ª comparação: 22, 37, 16, 47, 47, 59, 64, 81 Permanecem, pois 22<37
2ª comparação: 22, 16, 37, 47, 47, 59, 64, 81 Trocaram-se 37 com 16
3ª comparação: 22, 16, 37, 47, 47, 59, 64, 81 Permanecem, pois 37<47
4ª comparação: 22, 16, 37, 47, 47, 59, 64, 81 Permanecem, pois 47=47
5ª comparação: 22, 16, 37, 47, 47, 59, 64, 81 Permanecem, pois 47<59
Encerra-se o passo com o número 59 na sexta posição.
QUARTO PASSO: Preencher a quinta posição com um número menor ou igual àquele que se encontra na posição 6:
Situação inicial: 22, 16, 37, 47, 47, 59, 64, 81
1ª comparação: 16, 22, 37, 47, 47, 59, 64, 81 Trocaram-se 22 com 16
2ª comparação: 16, 22, 37, 47, 47, 59, 64, 81 Permanecem, pois 22<37
3ª comparação: 16, 22, 37, 47, 47, 59, 64, 81 Permanecem, pois 37<47
4ª comparação: 16, 22, 37, 47, 47, 59, 64, 81 Permanecem, pois 47=47
QUINTO PASSO: Preencher a quarta posição com um número menor ou igual àquele que se encontra na posição 5:
Situação inicial: 16, 22, 37, 47, 47, 59, 64, 81
1ª comparação: 16, 22, 37, 47, 47, 59, 64, 81 Permanecem, pois 16<22
2ª comparação: 16, 22, 37, 47, 47, 59, 64, 81 Permanecem, pois 22<37
3ª comparação: 16, 22, 37, 47, 47, 59, 64, 81 Permanecem, pois 37<47
SEXTO PASSO: Preencher a terceira posição com um número menor ou igual àquele que se encontra na posição 4:
Situação inicial: 16, 22, 37, 47, 47, 59, 64, 81
1ª comparação: 16, 22, 37, 47, 47, 59, 64, 81 Permanecem, pois 16<22
2ª comparação: 16, 22, 37, 47, 47, 59, 64, 81 Permanecem, pois 22<37
SÉTIMO PASSO: Preencher a segunda posição com um número menor ou igual àquele que se encontra na posição 3:
Situação inicial: 16, 22, 37, 47, 47, 59, 64, 81
1ª comparação: 16, 22, 37, 47, 47, 59, 64, 81 Permanecem, pois 16<22
O processo finaliza com a seqüência ORDENADA.
6) Demonstre o código-fonte do método bolha e comente o mesmo.
Resposta:
/* Algoritmo de ordenação Bubble Sort */
#include <stdio.h>
/* Definição da função bubble_sort */
void bubble_sort (int vet[], int max) {
int flag, i, aux;
do {
flag = 0;
for (i = 0; i < (max - 1); i++) {
/* Verfica se o vetor está em ordem, no caso ele coloca em ordem crescente, para decrescente trocar '>' por '<' */
if (vet[i] > vet[i+1]) {
/* Caso não esteja, ordena */
aux = vet[i];
vet[i] = vet[i+1];
vet[i+1] = aux;
flag =1;
}
}
/* Repete enquanto algum valor estiver fora de ordem */
} while (flag == 1);
/* Imprime o vetor ordenado em ordem crescente */
for (i = 0; i < max; i++) {
printf ("%d ",vet[i]);
}
printf ("\n");
}
main () {
int max, i;
/* Lê o total de números do vetor */
scanf ("%d", &max);
/* Define o vetor com o número max de algarismos */
int vetor[max];
for (i = 0; i < max; i++) {
/* Lê cada indice do vetor */
scanf ("%d",&vetor[i]);
}
/* Dentro dessa função o vetor será ordenado */
bubble_sort (vetor, max);
}
