COS-121

Estrutura de Dados e Algoritmos

2 Semestre de 2014

 Professor Ricardo Farias

Aula 06

Tópicos desta aula.

Linguagem C

Ordenação dos Elementos de um Vetor


Algoritmo Insertion Sort

Algoritmo:
Considera que o primeiro elemento está ordenado (ou seja, na posição correta).
A partir do segundo elemento, insere os demais elementos na posição apropriada entre aqueles já ordenados.
O elemento é inserido na posição adequada movendo-se todos os elementos maiores para posição seguinte do vetor.

Mais interessante que o Bubble Sort para popular um vetor.

Observe a figura:

O elemento da posição 0 (valor 50) é comparado com o elemento da posição 1 (valor 30).

0 1 2 3 4
50 30 40 20 10

Como o objetivo é ordenar crescentemente, os conteúdos dos elemetos da posições 0 e 1 devem ser trocados entre si.
0 1 2 3 4
30 50 40 20 10

Em seguida serão comparados os conteúdos dos elementos das posições 1 e 2:
0 1 2 3 4
30 50 40 20 10

Troca:
0 1 2 3 4
30 40 50 20 10

Elementos das posições 2 e 3:
0 1 2 3 4
30 40 50 20 10

Troca:
0 1 2 3 4
30 40 20 50 10

Elementos das posições 3 e 4:
0 1 2 3 4
30 40 20 50 10

Troca:
0 1 2 3 4
30 40 20 10 50

Apesar do vetor não estar ordenado ainda, observe que o maior elemento ficou na última posição:
0 1 2 3 4
30 40 20 10 50

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.:
0 1 2 3 4
30 40 20 10 50

Não troca:
0 1 2 3 4
30 40 20 10 50
Elementos das posições 1 e 2.:
0 1 2 3 4
30 40 20 10 50

Troca:
0 1 2 3 4
30 20 40 10 50
Elementos das posições 2 e 3.:
0 1 2 3 4
30 20 40 10 50

Troca:
0 1 2 3 4
30 20 10 40 50

E o processo recomeça:
0 1 2 3 4
30 20 10 40 50

Troca:
0 1 2 3 4
20 30 10 40 50

Elementos das posições 1 e 2:
0 1 2 3 4
20 30 10 40 50

Troca:
0 1 2 3 4
20 10 30 40 50


Recomeça... Elementos das posições 0 e 1:
0 1 2 3 4
20 10 30 40 50

Troca:
0 1 2 3 4
10 20 30 40 50

Vetor Ordenado!
0 1 2 3 4
10 20 30 40 50

O processo de ordenação termina! Veja o algoritmo a seguir: 

	#include 

	#define t 5

	void lerVet( int *p ){

		int i;

		for ( i=0; i0 && p[j-1] > aux) {
				p[j] = p[j-1];
				j--;
			}
			p[j] = aux;
		}
	}


	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");
		insertionSort(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?