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:

  1. 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).
  2. Conquistar: Classificar as duas metades recursivamente aplicando o merge sort;
  3. Combinar: Juntar as duas metades em um único conjunto já classificado.
    4. 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?