Bolha e Quicksort

Prévia do material em texto

Faculdade de Computação
Estruturas e Bancos de Dados
8a. Aula Prática: Métodos de Ordenação (Bolha e Quicksort)
O método da Bolha (bubblesort) é um algoritmo de ordenação simples. Realiza pelo menos 
n² comparações para ordenar n elementos. Ele é um dos mais simples algoritmos de 
ordenação conhecidos, porém é considerado ineficiente na ordenação de um conjunto muito 
extenso de itens.
 
O método da Bolha pode ser resumido em:
1. Comparar dois elementos adjacentes: se o primeiro é maior do que o segundo, ambos 
são trocados. 
2. Realizar a comparação/troca definida no item 1 para todos os pares de elementos 
adjacentes, começando com os dois primeiros e terminando com os dois últimos. Neste 
ponto o último elemento é o maior. 
3. Repetir o passo 2 para todos os elementos, com exceção do último sucessivamente. 
A figura a seguir ilustra os 3 passos:
Considerando vetores, podemos ter a implementação do método da Bolha em linguagem C: 
void bubbleSort(int v[], int tam)
{
 int i, j;
 for(i = tam - 1; i > 0; i--)
 for(j = 0; j < i; j++)
 if(v[j] > v[j+1]) /* compara elementos adjacentes */
 {
 int temp;
 temp = v[j]; /* troca elementos em v[j] e v[j+1] */
 v[j] = v[j+1];
 v[j+1] = temp;
 }
}
Exercícios Práticos:
1) Testar a função bubbleSort definida acima. Faça um programa que receba os dados do vetor 
e depois os ordena utilizando o método da Bolha (por flutuação)
2) Crie um vetor de milhares de elementos usando uma função de geração aleatória de 
elementos. Verifique o tempo gasto pela função de ordenação por Bolha para classificar os 
elementos.
 // exemplo de geração aleatória usando a função rand
 printf("Insira a quantidade de elementos a serem gerados\n");
 scanf("%d",&num);
 i = 0;
 while (i <= num -1){
 v[i] = rand();
 i++;
 }
3) Escrever um código em linguagem C para implementar o algoritmo bubbleSort para uma 
lista ligada de objetos do tipo Pessoa, ordenando crescentemente de acordo com a data de 
nascimento de cada pessoa representada. Grave a lista ordenada num arquivo texto (.txt)
QuickSort
O QuickSort é baseado em uma estratégia de dividir para conquistar e é um dos algoritmos de 
ordenação mais populares, realizando a ordenação através de trocas..
O algoritmo QuickSort pode ser dividido nos seguintes passos: 
· O vetor A[p..r] é subdividido em dois vetore A[p..q] e A[q+1..r] não vazios tal que 
cada elemento de A[p..q] é menor ou igual a cada elemento de A[q+1..r]. O índice q é 
calculado como parte deste particionamento. 
· Os dois subvetores A[p..q] e A[q+1..r] são ordenados por recursivas chamadas do 
QuickSort. 
Por exemplo, dado o vetor f e d h a c g b, e tomando o valor “d” para partição, o primeiro 
passo do quicksort rearranja os elementos da seguinte forma:
Início: f e d h a c g b
passo 1: b c a d h e g f 
Esse processo é então repetido para cada seção – isto é, “b c a” e “h e g f”.
O algoritmo Quicksort, inventado por C.A.R. Hoare [Computer Journal, 5, pp.10-15, 1962], é 
em geral bastante rápido. O algoritmo consome tempo proporcional a n log(n) em média e 
proporcional a n2 no pior caso. 
A função qsort inclusa na biblioteca <stdio.h> rearranja o vetor base[0..tam-1] em ordem 
crescente. (O endereço do primeiro elemento do vetor é base e o vetor tem tam 
elementos.) A natureza dos elementos do vetor não importa, mas qsort precisa saber que 
cada elemento ocupa size bytes. Eis o protótipo da função: 
void qsort (void *base, size_t nmemb, size_t size, 
 int (*compar)(const void *, const void *));
O código abaixo ilustra uma utilização da função Qsort (biblioteca <stdlib.h>)
void imprimeV(int v[], int tam){
int p;
 for(p=0; p<tam; p++){
 printf(" %d",v[p]);
 }
}
int cmp (const void *x, const void *y) {
 return (*(int *)x - *(int *)y); 
}
int main()
{
 int v[100];
 int num;
 int i=0;
 //l = inicia();
 printf("Insira a quantidade de elementos (até 1000)\n");
 scanf("%d",&num);
 while (i < num){
 v[i] = rand();
 i++;
 }
 printf("\nElementos do Vetor : \n");
 imprimeV(v, num);
 
 
 qsort (v, num+1, sizeof (int), cmp);
 printf("\nElementos Ordenados : \n");
 imprimeV(v,num);
 system("PAUSE>>null");
 return 0;
}
Exercícios Práticos:
1) Familiarizar-se com a função qsort. Testar e finalizar o programa exemplo.
2) Comentar e testar a função qs que seleciona o valor intermediário para particionar o vetor 
(elemento “pivot”). Para uma ordenação ótima, deveria ser selecionado o valor que estivesse 
precisamente no centro da faixa de valores. Porém, isso não é fácil para a maioria do conjunto 
de dados
void qs(int *A, int left, int right) 
{ 
 register int i, j; 
 int x,y; 
 i=left; 
 j=right; 
 x=A[(left+right)/2]; // Elemento intermediário como “pivot” // 
 do{ 
 while(A[i]<x && i<right) i++; 
 while(A[j]>x && j>left) j--; 
 if(i<=j){ 
 troca(A,i,j); 
 i++; 
 j--; 
 } 
 }while(i<=j); 
 if(left<j) qs(A,left,j); 
 if(i<right) qs(A,i,right); 
} 
//-------------------------------------------------
3) Crie um vetor de milhares de elementos usando uma função de geração aleatória de 
elementos. Verifique o tempo gasto pela função de ordenação Quicksort para classificar os 
elementos e compare o resultado com o método da Bolha.