Bubble sort. O bubble sort apresentado na Figura 6.15 é ineficaz no caso de arrays grandes. Faça as modificações simples descritas a seguir para melhorar o desempenho do bubble sort.
a) Após a primeira passada, o maior número estará certamente no elemento de número mais alto do array; após a segunda passada, os dois maiores números estarão ‘no lugar’ e assim por diante. Em vez de nove comparações em cada passada, modifique o bubble sort para que sejam feitas oito comparações na segunda passada, sete na terceira e assim por diante.
b) Os dados no array talvez já estejam na ordem correta, ou na ordem quase correta, portanto, por que fazer nove passadas se menos que isso já seria suficiente? Modifique a ordenação para verificar, ao final de cada passada, se alguma troca foi feita. Se nenhuma troca tiver sido feita, então os dados já deverão estar na ordem certa, de modo que o programa deverá ser concluído. Se foram feitas trocas, então, pelo menos mais uma passada será necessária
Passo 1
Fala Galera!!! Exercício TOPZERA para ficar craque em arrays. Vamos junto resolver essa parada.
Antes de começar precisamos saber sobre o “bubble sort”. Bom, essa é uma técnica usada para ordenar os valores nos elementos do array. A técnica possui esse nome, pois os valores menores gradualmente sobem como ‘bolhas’ até o topo do array, como bolhas de ar que sobem para a superfície da água, enquanto os valores maiores vão para o fundo do array.
A técnica é fazer várias passadas pelo array. A cada passada, pares sucessivos de elementos são comparados. Se um par está em ordem crescente (ou se os valores forem idênticos), deixamos os valores como estão. Se um par está em ordem decrescente, seus valores são trocados no array.
Passo 2
Bom, agora que já sabemos como a técnica funciona, vamos escrever nosso programa.
Primeiro vamos definir um tamanho máximo de 10 elementos para nosso array e atribuir valores de 10 a 1 de forma decrescente. A lógica do nosso programa será ordenar nosso array para que os números fiquem na ordem crescente.
Nesse exercício teremos que melhorar a técnica do bubble sort, para que ao final de cada passada, o programa possa verificar se alguma troca foi feita. Caso nenhuma troca tenha sido feita, então os dados já deverão estar na ordem certa, e assim concluir o programa. E no caso de ter acontecido a troca o programa deverá continuar.
Essa modificação é necessária para que o programa ordene com o menor número possível de passadas.
Passo 3
Agora que já temos toda a lógica do programa e quais os comandos ele deverá executar. Partiu escrever nosso código. De começo vamos precisar de algumas variáveis necessárias para executar os comandos, principalmente para guardas os elementos trocados do array e também para sinalizar se já foi feita uma troca ou não, e caso não tenha feito, realizar um
break. O começo do nosso programa vai ficar da seguinte forma:
#include
#define MAX 10
/* função main inicia a execução do programa */
int main( void )
{
/* inicializa a */
int a[ MAX ] = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
int pass; /* contador de passada */
int i; /* contador de comparação */
int troca; /* verificar se foi feita a troca */
int hold; /* local temporário usado para trocar elementos do array */
printf("Itens de dados na ordem original\n");
Todas essas variáveis deverão estar dentro de uma estrutura de repetição para fazer o controle da quantidade de passadas realizadas.
Passo 4
Usando as estruturas de repetições para percorrer nosso array, de forma, que vamos ordenando e no final retornar o array com os elementos na ordem crescente. O restante do nosso programa ficará da seguinte forma:
/* bubble sort */
/* loop para controlar número de passadas */
for ( pass = 1; pass
troca = 0;
/* loop para controlar número de comparações por passada */
for( i =0; i
/* compara elementos adjacentes e os troca se o primeiro
elemento for maior que o segundo elemento */
if (a[i] > a[ i + 1 ]){
troca = 1;
hold = a[i];
a[i] = a[ i + 1 ];
a[ i +1 ] = hold;
} /* fim do if */
} /*fim do for */
printf("Depois do passo %d: ", pass);
/* mostrar array depois do passo atual */
for ( i = 0; i
printf (" %d", a[i]);
} /* fim do for */
printf("\n");
/* break caso não tenho feito troca */
if ( !troca ){
break;
} /* fim do if */
} /* fim do for */
printf(" \nItens de dados em ordem crescente\n");
/* imprime array ordenado */
for (i = 0; i
printf("%4d", a[i]);
} /* fim do for */
printf("\n");
return 0;
}
Agora é só juntar tudo, e teremos o nosso programa finalizado!!!!
Resposta
O nosso programa final ficará da seguinte forma:
Prontinho Galera!!! Finalizamos mais um, até o próximo.