QUESTIONÁRIO 05 - ED II

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);

 

}