COS-121

Estrutura de Dados e Algoritmos

2º Semestre de 2014

 Professor Ricardo Farias

Aula 08

Tópicos desta aula.

Linguagem C

Ordenação dos Elementos de um Vetor


Quick Sort

Determina-se um elemento pivô. O pivô é posicionado dentro do vetor de tal forma que, todos à esquerda do pivô são menores que ele e, todos à direita do pivô são maiores. O pivô "divide" o vetor em dois subvetores. Recursivamente o quick sort é realizado na primeira metade do vetor e na segunda metade.

Algoritmo: Seja x o vetor a ser ordenado e n o número de elementos de x. Seja a um elemento de x escolhido ao acaso (por exemplo, a=x[0]). Suponha que os elementos de x estão divididos de tal forma que a é colocado na posição j e as seguintes condições são verdadeiras:

Então a está na posição correta no vetor. Se este processo for repetido para os sub-vetores x[0] a x[j-1] e x[j+1] a x[n-1], o resultado é o vetor ordenado.

Observe a figura: Vetor original com elemento desordenados.

0 1 2 3 4 5 6 7
25 57 86 48 37 24 92 12

O pivô (primeiro elemento do vetor) é escolhido.

0 1 2 3 4 5 6 7
25 57 86 48 37 24 92 12
pivô

A busca por elementos maiores que o pivô se inicia à esquerda do trecho do vetor que está sendo ordenado, e a busca por elementos menores que o pivô se inicia à direita.
0 1 2 3 4 5 6 7
25 57 86 48 37 24 92 12
esq dir

25 não é maior que o pivô (25). A busca por um elemento maior que o pivô continua à esquerda.
0 1 2 3 4 5 6 7
25 57 86 48 37 24 92 12
pivô esq dir

57 é encontrado. A busca por um elemento menor que o pivô à direita encontra o 12.
0 1 2 3 4 5 6 7
25 57 86 48 37 24 92 12
pivô esq dir

Troca o elemento da esquerda com o da direita.
0 1 2 3 4 5 6 7
25 12 86 48 37 24 92 57
pivô esq dir

Continua a busca por elementos maiores que o pivô (25) a partir da esquerda e por elementos menores a partir da direita.
0 1 2 3 4 5 6 7
25 12 86 48 37 24 92 57
esq dir

Troca.
0 1 2 3 4 5 6 7
25 12 24 48 37 86 92 57
pivô esq dir

O processo continua.
0 1 2 3 4 5 6 7
25 12 24 48 37 86 92 57
pivô dir esq

Ops! Ocorreu um cruzamento da posição esquerda com a posição direita. Troca o pivô com o elemento da posição direita.
0 1 2 3 4 5 6 7
24 12 25 48 37 86 92 57

O subvetor à esquerda do pivô contém os elementos menores que o pivô e o subvetor à direita do pivô contém os elementos maiores que o pivô. O processo se repete para o subvetor da esquerda do vetor e para o subvetor da direita.

O 24 é pivô no subvetor à esquerda.
0 1 2 3 4 5 6 7
24 12 25 48 37 86 92 57
esq dir
E o processa continua no subvetor à esquerda.
0 1 2 3 4 5 6 7
12 24 25 48 37 86 92 57
esq dir
E a direita, onde o pivô é o 48.
0 1 2 3 4 5 6 7
12 24 25 48 37 86 92 57
esq dir
0 1 2 3 4 5 6 7
12 24 25 48 37 86 92 57
dir esq
Ops! Cruzamanto da posiçães direita e esquerda. Troca o pivô com o elemento da posição direita.
0 1 2 3 4 5 6 7
12 24 25 37 48 86 92 57
0 1 2 3 4 5 6 7
12 24 25 37 48 86 92 57
esq dir
0 1 2 3 4 5 6 7
12 24 25 37 48 86 92 57
esq dir
0 1 2 3 4 5 6 7
12 24 25 37 48 86 57 92
esq dir
0 1 2 3 4 5 6 7
12 24 25 37 48 86 57 92
dir esq
0 1 2 3 4 5 6 7
12 24 25 37 48 57 86 92
0 1 2 3 4 5 6 7
12 24 25 37 48 57 86 92
O processo de ordenação termina!

Veja o algoritmo a seguir: 

#include 

void lerVet( int *p, int t ){

	int i;

	for ( i=0; i pivo )
			dir--; 

		if ( esq < dir )
			trocar(v,esq,dir);

	}

	v[inf] = v[dir];
	v[dir] = pivo ;
	return dir;
}

void quickSort( int *p, int inf, int sup ) {

	int posPivo; // posição do pivô

	if ( inf >= sup )
		return;

	posPivo= divide(p,inf,sup); 
	quickSort(p,inf,posPivo-1);
	quickSort(p,posPivo+1,sup); 

}


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");
	quickSort(p, 0, tam-1);

	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?