Algoritmos de Ordenação

Links relacionados: DAS5102 Fundamentos da Estrutura da Informação, DAS5334 Introdução a Informática para Automação, Linguagens de Programação.

Introdução

Os algoritmos de ordenação são processos para arranjar um conjunto de informações semelhantes numa ordem crescente ou decrescente. Eles são utilizados em quase todos os programas de banco de dados, compiladores, interpretadores e sistemas operacionais. Destes métodos, existem três gerais: por troca (bolha), por seleção, por inserção.

Ordenação Bolha (O Demônio das Trocas)

O Método de ordenação bolha é um método de ordenação por trocas e é o método mais conhecido e mais difamado por ser uma das piores formas ordenações.

Resumo: Troca-se os elementos fora de ordem, até que o vetor esteja ordenado.

 1Bolha (vet : vetor, tamanho : inteiro)
 2
 3Variaveis
 4	a, b, no: inteiro
 5
 6Inicio
 7	Para a = tamanho-1 ate 1 Faca
 8		Para b = 1 ate a Faca
 9			Se vet[b] > vet[b+1] Entao Faca
10				no <- vet[b]
11				vet[b] <- vet[b+1]
12				vet[b+1] <- no
13			Fim Se
14		Fim Para
15	Fim Para
16Fim

Ordenação por Seleção

Este método encontra o elemento de menor valor e troca-o com o primeiro elemento, depois, no restante do vetor, encontra o menor valor e troca-o pelo segundo e sucessivamente.

 1Selecao (item : vetor, i: inteiro)
 2
 3Variaveis
 4	a, b, c, aux : Inteiro
 5	mudou : Booleano
 6
 7Inicio
 8	Para a = 0 ate i-2 faca
 9		Mudou <- falso
10		c <- a
11		Para b = a+1 ate i-1 faca
12			Se item[b] < item[c] entao faca
13				c <- b
14				mudou <- verdadeiro
15			Fim se
16		Fim para
17		Se mudou entao faca
18			aux <- item[c]
19			item[c] <- item[a]
20			item[a] <- aux
21		Fim se
22	Fim para
23Fim

Ordenação por Inserção

Este método ordena os dois primeiros membros do vetor. Em seguida, insere o terceiro membro na sua posição ordenada em relação aos outros dois membros, depois insere o quarto, e assim por diante, até que todo o vetor tenha sido ordenado.

 1Insercao (item : vetor, i : inteiro)
 2
 3Variaveis
 4	a, b : inteiro
 5	t : vetor
 6
 7Inicio
 8	Para a = 1 ate i-1 faca
 9		t <- item[a]
10		b <- a-1
11		Enquanto b >= 0 e t < item[b] faca
12			Item[b+1] <- item[b]
13			b <- b-1
14		Fim enquanto
15		Item[b+1] <- t
16	Fim para
17Fim

Exercícios / Roteiro

Parte 1: Crie uma TAD chamada sort (sort.h e sort.c) com o gerenciamento de uma estrutura com um vetor de tamanho dinâmico e uma informação do tamanho desse vetor, que deve ser passado na sua criação. Essa TAD possui as operações de ordenação para cada tipo visto em aula e uma operação para imprimir todos os elementos do vetor dinâmico.

Parte 2: Escreva um programa que seja capaz de receber como entrada o tipo do algoritmo de ordenação a ser utilizado, a opção de ordenação (crescente ou decrescente) e uma lista de números. Imprima-os após a ordenação (utilize argc argv para a tarefa).