COS-121
Estrutura de Dados e Algoritmos
2º Semestre de 2014
Professor Ricardo Farias
Aula 07
Tópicos desta aula.
Linguagem C
Ordenação dos Elementos de um Vetor
Algoritmo Merge Sort
A idéia básica do Merge Sort é criar uma sequência ordenada a partir de duas outras também ordenadas. Para isso, o algoritmo Merge Sort divide a sequência original em pares de dados, agrupa estes pares na ordem desejada; depois as agrupa as sequências de pares já ordenados, formando uma nova sequência ordenada de quatro elementos, e assim por diante, até ter toda a sequência ordenada.
Algoritmo:
Os três passos úteis dos algoritmos dividir-para-conquistar, que se aplicam ao Merge Sort são:
- Dividir: Dividir os dados em subsequências pequenas;
Este passo é realizado recursivamente, iniciando com a divisão do vetor de n elementos em duas metades, cada uma das metades é novamente dividida em duas novas metades e assim por diante, até que não seja mais possível a divisão (ou seja, sobrem n vetores com um elemento cada).
- Conquistar: Classificar as duas metades recursivamente aplicando o merge sort;
- Combinar: Juntar as duas metades em um único conjunto já classificado.
Para completar a ordenação do vetor original de n elementos, faz-se o merge ou a fusão dos sub-vetores já ordenados.
A desvantagem do Merge Sort é que requer o dobro de memória, ou seja, precisa de um vetor com as mesmas dimensões do vetor que está sendo classificado.
Observe a figura: Vetor original com elemento desordenados.
| 0
| 1
| 2
| 3
| 4
| 5
| 6
| 7
| 8
|
| 53
| 25
| 46
| 32
| 23
| 37
| 41
| 17
| 10
|
O vetor original é subdividido em dois vetores.
| 0
| 1
| 2
| 3
| 4
| 5
| 6
| 7
| 8
|
| 53
| 25
| 46
| 32
| 23
| 37
| 41
| 17
| 10
|
Cada um dos subvetores é novamente dividido.
| 0
| 1
| 2
| 3
| 4
| 5
| 6
| 7
| 8
|
| 53
| 25
| 46
| 32
| 23
| 37
| 41
| 17
| 10
|
E assim por diante.
| 0
| 1
| 2
| 3
| 4
| 5
| 6
| 7
| 8
|
| 53
| 25
| 46
| 32
| 23
| 37
| 41
| 17
| 10
|
| 53
| 25
| 46
| 32
| 23
| 37
| 41
| 17
| 10
|
Após todo o processo de divisão, ocorre o processo da fusão ordenada dos subvetores. O subvetor (53) com o subvetor (25). Ordenando os dois.
| 0
| 1
| 2
| 3
| 4
| 5
| 6
| 7
| 8
|
| 25
| 53
| 46
| 32
| 23
| 37
| 41
| 17
| 10
|
O subvetor (25, 53) com o subvetor (46). Ordenando os dois.
| 0
| 1
| 2
| 3
| 4
| 5
| 6
| 7
| 8
|
| 25
| 46
| 53
| 32
| 23
| 37
| 41
| 17
| 10
|
O subvetor (32) com o subvetor (23).
| 0
| 1
| 2
| 3
| 4
| 5
| 6
| 7
| 8
|
| 25
| 46
| 53
| 23
| 32
| 37
| 41
| 17
| 10
|
O subvetor (25,46,53) com o subvetor (23,32). Ordenando os dois.
| 0
| 1
| 2
| 3
| 4
| 5
| 6
| 7
| 8
|
| 23
| 25
| 32
| 46
| 53
| 37
| 41
| 17
| 10
|
O mesmo processo se repete no subvetor (37, 41, 17, 10).
| 0
| 1
| 2
| 3
| 4
| 5
| 6
| 7
| 8
|
| 23
| 25
| 32
| 46
| 53
| 37
| 41
| 17
| 10
|
| 23
| 25
| 32
| 46
| 53
| 37
| 41
| 10
| 17
|
| 23
| 25
| 32
| 46
| 53
| 10
| 17
| 37
| 41
|
Os subvetores resultantes (23,25, 32, 36,53) e (10, 17, 37, 41) são fundidos ordenandos durante a fusão.
| 0
| 1
| 2
| 3
| 4
| 5
| 6
| 7
| 8
|
| 10
| 17
| 23
| 25
| 32
| 37
| 41
| 46
| 53
|
O processo de ordenação termina!
Veja o algoritmo a seguir:
#include
void lerVet( int *p, int t ){
int i;
for ( i=0; i 1 ) {
meio = t / 2;
mergeSort(p, meio);
mergeSort(p + meio, t - meio);
merge(p, t);
}
}
void main(){
int *p, tam;
printf("Quantidade de elementos do vetor?");
scanf("%d",&tam);
p = (int*) malloc(tam * sizeof(int));
printf("\nDigite o conteudo do vetor:\n");
lerVet(p, tam);
printf("\nConteudo digitado para o vetor:\n");
mostrarVet(p, tam);
printf("\nOrdenando o vetor...\n");
mergeSort(p, tam);
printf("\nConteudo do vetor ja ordenado:\n");
mostrarVet(p, tam);
free(p);
}
Que alterações devem ser realizadas no algoritmo para que o vetor seja ordenado decrescentemente?