COS-121
Estrutura de Dados e Algoritmos
2 Semestre de 2014
Professor Ricardo Farias
Aula 05
Tópicos desta aula.
Linguagem C
Ordenação dos Elementos de um Vetor - Algoritmo Bubble Sort
Ordenar é o ato de se colocar os elementos de uma sequência, em uma dada relação de ordem entre si, de acordo com um critério pré-estabelecido.
Os elementos do vetor devem ser trocados entre si para que fiquem na ordem desejada.
Vamos iniciar com um exemplo simples que apresenta a troca do conteúdo de duas variáveis inteira (sem pensar em vetor).
Exemplo:
#include
void trocar (int *px, int *py) {
int aux = *px;
*px = *py;
*py = aux;
}
void main(){
int x, y;
printf("\nValor para x? ");
scanf("%d",&x);
printf("\nValor para y? ");
scanf("%d",&y);
// mostrando os conteudos de x e y
printf("\nX = %d e Y = %d\n", x, y);
printf("\nTrocando...\n");
trocar (&x, &y);
printf("\nX = %d e Y = %d\n", x, y);
}
Método de Ordenação Bolha (Bubble Sort)
Algoritmo: Percorre várias vezes o vetor de maneira sequencial (passos). Em cada passo,
compara cada elemento no vetor com o seu sucessor (p[i] com p[i+1]) e troca o conteúdo das
posições em análise, caso não estejam na ordem desejada.
Observe a figura:
O elemento da posição 0 (valor 50) é comparado com o elemento da posição 1 (valor 30).
Como o objetivo é ordenar crescentemente, os conteúdos dos elemetos da posições 0 e 1 devem ser trocados.
Em seguida serão comparados os conteúdos dos elementos das posições 1 e 2:
Troca:
Elementos das posições 2 e 3:
Troca:
Elementos das posições 3 e 4:
Troca:
Apesar do vetor não estar ordenado ainda, observe que o maior elemento ficou na última posição:
O processo recomeça, porém ocorrerá entre as posições 0 e 3 (o elemento da posição 4 já está ordenado).
Elementos das posições 0 e 1.:
Não troca:
Elementos das posições 1 e 2.:
Troca:
Elementos das posições 2 e 3.:
Troca:
E o processo recomeça:
Troca:
Elementos das posições 1 e 2:
Troca:
Recomeça... Elementos das posições 0 e 1:
Troca:
Vetor Ordenado!
O processo de ordenação termina! Veja o algoritmo a seguir:
#include
#define t 5
void lerVet( int *p ){
int i;
for ( i=0; i 0; i-- ){
for ( j=0; j < i; j++ ){
if ( p[j] > p[j+1] )
trocar(p, j, j+1);
}
}
}
void main(){
int vet[t];
printf("\nDigite o conteudo do vetor:\n");
lerVet(vet);
printf("\nConteudo digitado para o vetor:\n");
mostrarVet(vet);
printf("\nOrdenando o vetor...\n");
bubbleSort(vet);
printf("\nConteudo do vetor ja ordenado:\n");
mostrarVet(vet);
}
Suponha que fosse um vetor da struct Produto, cujos membros são código e preço. Deseja-se ordenar em ordem crescente pelo código:
#include
#define t 3
struct Produto {
int cod;
float preco;
};
void lerVet( struct Produto *p ){
int i;
for ( i=0; icod);
printf("\tPreco? ");
scanf("%f",&p->preco);
p++;
}
}
void mostrarVet( struct Produto *p ){
int i;
for ( i=0; i < t; i++ ){
printf("\tCodigo: %d\n",p->cod);
printf("\tPreco.: %f\n\n",p->preco);
p++;
}
}
void trocar (struct Produto *pv, int x, int y) {
struct Produto aux = pv[x];
pv[x] = pv[y];
pv[y] = aux;
}
void bubbleSort( struct Produto *p){
int i, j;
for ( i=t-1; i > 0; i-- ){
for ( j=0; j < i; j++ ){
if ( p[j].cod > p[j+1].cod ) // A comparação é pelo membro cod da struct
trocar(p, j, j+1);
}
}
}
void main(){
struct Produto vet[t];
printf("\nDigite o conteudo do vetor:\n");
lerVet(vet);
printf("\nConteudo digitado para o vetor:\n");
mostrarVet(vet);
printf("\nOrdenando o vetor...\n");
bubbleSort(vet);
printf("\nConteudo do vetor ja ordenado:\n");
mostrarVet(vet);
}
E se desejássemos ordenar em ordem decrescente por preço? O que deveria ser alterado no código acima?