CENTRO DE CIÊNCIAS EXATAS
DEPARTAMENTO DE COMPUTAÇÃO
TEORIA DA COMPUTAÇÃO
Algoritmos de Ordenação
Alunos:
André Ricardo Gonçalves
Luiz Gustavo Andrade dos Santos
Paulo Roberto Silla
Profa. Linnyer Beatrys Ruiz
LONDRINA - PR
2007
André Ricardo Gonçalves
Luiz Gustavo Andrade dos Santos
Paulo Roberto Silla
Algoritmos de Ordenação
Trabalho apresentado à Universidade Estadual de Londrina, como parte de requisito de avaliação do 3o Bimestre
da disciplina de Teoria da Computação, do curso de Ciência
da Computação sob orientação da Profa. Linnyer Beatrys
Ruiz.
LONDRINA - PR
2007
Sumário
1 Introdução
4
2 Algoritmos de Ordenação
5
2.1
Bubble Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
2.2
Insertion Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
2.3
Selection Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
2.4
Merge Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
2.5
Quick Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.6
Heap Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.7
Count Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.8
Bucket Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.9
Radix Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3 Conclusão
16
Apêndice
17
Referências Bibliográficas
23
3
Capı́tulo 1
Introdução
Métodos ordenação de elementos sempre foi uma área atrativa para os pesquisadores
da Ciência da Computação. Em busca de métodos eficientes para resolver tal problema,
pesquisadores analisavam algumas situações do dia-a-dia, como a maneira que os jogadores
de cartas ordenavam as cartas que continha, para facilitá-lo durante o jogo. Decorrente
disto vários algoritmos de ordenação foram apresentados, como o Bubble Sort, Selection
Sort, Quick Sort, dentre outros. Este trabalho tem por objetivo apresentar de forma
objetiva as principais caracterı́sticas de alguns métodos de ordenação, suas vantagens e
desvantagens, suas restrições e o tempo computacional de cada um deles.
4
Capı́tulo 2
Algoritmos de Ordenação
Os algoritmos de ordenação são algoritmos que colocam os elementos de uma lista em uma
determinada ordem, ou seja dada uma vetor de elementos de entrada n1 , n2 , n3 , ..., nk , o
algoritmo será aplicado a este vetor de forma que a saı́da seja da forma n1 6 n2 6 n3 , ..., 6
nk .
Existem vários algoritmos destinados a este fim, a maioria deles baseado na idéia de
Inserção, Seleção e Permutação.
A eficiência dos algoritmos de ordenação é analisada segundo alguns critérios, como
a complexidade computacional, quantidade de memória utilizada, quanto ao uso de recursão, estabilidade do algoritmo e outros. Esses critérios por sua vez são analisados
pelo número de movimentos e o número de comparação efetuadas durante a execução do
algoritmo [Wir86].
Quanto aos critérios apresentados, segue a definição de alguns deles abaixo:
Complexidade Computacional Está relacionado com o comportamento do algoritmo
no melhor, médio e pior caso, que é definido pelo número de comparações efetuadas
pelo algoritmo em relação ao tamanho do vetor de entrada. A complexidade é
comumente apresentada como uma função assintótica em relação a n, que é igual
ao número de elementos do vetor de entrada.
Estabilidade A estabilidade é definida pela não realização de trocas inúteis, como a
troca de elementos iguais. Um algoritmo é dito ser estável se o mesmo não efetua
trocas inúteis.
A seguir são apresentados alguns dos principais algoritmos de ordenação, como uma
breve explicação de seu funcionamento e algumas caracterı́sticas especı́ficas como a
análise computacional deste algoritmo.
5
2.1
Bubble Sort
É um dos mais simples dos algoritmos de ordenação, entretanto é o menos eficiente.
Considere um vetor disposto na vertical. Este método “bolha” faz com que um elemento
mais “leve” (menor) situado ao final do vetor (“fundo”) flutue até o inı́cio deste. Para
isso, são feitas comparações e trocas para cada par de elementos consecutivos. Ou seja,
é um método de permutação direta que consiste em comparar um elemento com todos
os elementos subseqüentes no vetor, verificando se o elemento é maior que o elemento
analisado, se for, faz a troca dos elementos. Este processo é realizado até o último elemento
do vetor.
Complexidade de tempo:
• Melhor caso:
n2
2
Vetor ordenado ou quase ordenado.
• Pior caso: 2n2
Vetor na ordem inversa.
• Médio caso:
5n2
2
Assintoticamente:
• Todos os casos com complexidade O(n2 )
Este método é um dos mais demorados que existe, por ser de ordem quadrática até
mesmo em seu melhor caso e também devido à grande quantidade de trocas realizadas,
mas ele pode sofrer algumas melhorias:
• Verificar se o vetor já está ordenado, antes de chegar ao último elemento a ser
analisado no vetor (se já estiver ordenado, não há necessidade de mais comparações).
Neste caso, o algoritmo pode ter uma melhor performance do que a quadrática, mas
sem garantia para a maioria dos casos;
• Armazenar a posição na qual o vetor não sofreu nenhuma troca, para que na próxima
verificação, o algoritmo reinicie o ciclo a partir dessa marcação, não necessitando
chegar até essa posição passando pelos antecessores;
• Alternar a direção dos sucessivos passos de ordenação: Shake Sort, um Bubble
Sort que age tanto da esquerda para a direita quanto da direita para a esquerda
alternadamente (bidirecional). O Shake Sort também pode utilizar armazenamento
de posições para os dois sentidos ou verificação de inalteração de posições.
Mesmo com tais melhorias o Bubble Sort é ainda pior do que os outros algoritmos de
permutação. O Shake Sort é utilizado quando já se sabe a priori se o vetor está quase em
ordem, porém este caso é muito raro na prática.
6
2.2
Insertion Sort
Consiste em um algoritmo simples, baseado na ordenação pela comparação durante a
inserção. Seu funcionamento obedece a definição a seguir:
Definição 2.1 Sejam V e V’ vetores. Inicialmente o número de elementos de V é n,
enquanto V’ está vazio. A cada iteração, um elemento de V (entrada) será retirado,
da esquerda para a direita e inserido em V’ (saı́da) na posição correta de acordo com a
ordenação desejada, resultando em V’ o vetor ordenado.
Exemplo 2.1 Estado inicial:
V = {3,7,4,8,1}
V’ = ∅
Estado após a retirada do elemento 3 de V e, inserção do mesmo em V’:
V = {7,4,8,1}
V’ = {3}
Estado após a retirada do elemento 7 de V e, inserção do mesmo em V’:
V = {4,8,1}
V’ = {3,7}
Estado após a retirada do elemento 4 de V e, inserção do mesmo em V’:
V = {8,1}
V’ = {3,4,7}
Estado após a retirada do elemento 8 de V e, inserção do mesmo em V’:
V = {1}
V’ = {3,4,7,8}
Estado após a retirada do elemento 1 de V e, inserção do mesmo em V’:
V=∅
V’ = {1,3,4,7,8}
Observe que a cada estado, V’ está sempre ordenado.
A seguir, descrevemos as caracterı́sticas do Insertion Sort
Implementação O algoritmo possui simplicidade de implementação;
Eficiência É eficiente para pequenos conjuntos de dados e também para conjuntos onde
os dados encontram-se parcialmente ordenados;
Melhor caso Um vetor já ordenado, onde é executado em tempo O(n), em que n é o
tamanho da entrada;
7
Pior caso Um vetor no qual seus elementos estão em ordem inversa, sendo executado
em tempo O(n2 ), em que n é o tamanho da entrada.
Tempo médio O Insertion Sort é, em média, executado em tempo O(n2 ), com n representando o tamanho da entrada.
2.3
Selection Sort
O Selection Sort é baseado no seguinte princı́pio:
1. Escolha o elemento de menor valor;
2. Troque os elementos do ponteiro corrente, ak , pelo elemento encontrado no passo
anterior;
3. Incremente o ponteiro atual, ak+1 e repita as operações anteriores agora com a apenas
os n − 1 elementos restantes, depois os n − 2, até restar somente um elemento, o
maior deles.
Neste algoritmo o número de comparação das chaves é independente da ordem inicial
do vetor, assim o número de comparações é definido por:
(n2 − n)
(2.1)
2
Já o número de movimentações é mı́nimo se o vetor já está ordenado como mostra a
C=
equação 2.2, e o número máximo de movimentações é realizado se o vetor está ordenado
na ordem inversa, como mostra a equação 2.3 [Wir86].
Mmin = 3 ∗ (n − 1)
(2.2)
n2
+ 3 ∗ (n − 1)
(2.3)
4
Com isso podemos concluir que os algoritmo Selection Sort é mais indicado do que o
Mmax =
algoritmo Insertion Sort, exceto nos seguintes casos:
• as chaves estão inicialmente ordenadas;
• as chaves estão inicialmente quase ordenadas.
8
2.4
Merge Sort
O Merge Sort aplica a técnica de divisão e conquista para a ordenação [Goo04]. Baseia-se
na junção de duas seqüências ordenadas resultando em uma única, também ordenada. A
técnica da divisão e conquista para ordenar uma seqüência S de n elementos é dividida
em três etapas, segundo [Goo04]:
1. Divisão: retornar S caso ela possua um ou zero elemento. Caso contrário, remover
todos os elementos de S, inserindo a primeira metade (dn/2e) em S1 e a segunda
metade (bn/2c) em S2 ;
2. Recursão: ordenar S1 e S2 de modo recursivo;
3. Conquista: devolver os elementos para S, realizando um merge entre S1 e S2 de
maneira a manter a seqüência S ordenada.
Abaixo notamos a figura 2.1 que mostra a execução do algoritmo Merge Sort:
Figura 2.1: Exemplo da execução do algotirmo Merge Sort.
Detalhando um pouco mais a divisão nota-se que enquanto o número de elementos
da seqüência for maior que um, devem ser criadas duas novas seqüências, cada uma com
metade dos elementos da seqüência anterior e o algoritmo de divisão deve ser chamado
recursivamente para essas duas novas seqüeências.
Já o processo de junção deve ser realizado da seguinte maneira: remover, iterativamente, o menor elemento entre S1 e S2 e inserı́-lo na posição final de S. Quando uma das
9
seqüências estiver vazia, todo o restante da outra deverá ser movido para o final de S.
[Goo04] propõe um algoritmo, para esta finalidade, que pode ser encontrado no apêndice,
com o nome de junção.
Podemos destacar algumas caracterı́sticas do Merge Sort:
Eficiência É uma boa escolha quando a entrada não cabe totalmente na memória principal, tendo de ser armazenada em dispositivos mais lentos, como um disco rı́gido,
pois aproveita melhor os dados trazidos em bloco do disco;
Tempo de execução Não depende do estado inicial da seqüência de entrada. Logo,
tanto no melhor quanto no pior e, conseqüentemente no caso médio, o Merge Sort
executa em O(log2 n), com n igual ao número de elementos da entrada.
2.5
Quick Sort
O Quick Sort é um método de ordenação por particionamento e é o mais eficiente que se
conhece considerando casos gerais, ou seja, não-especı́ficos, mas é não-estável. Ele tem
como base os algoritmos de ordenação por permutações, como o BubbleSort. Porém sua
estratégia baseia-se na solução de problemas conhecida como dividir para conquistar, na
qual consiste em escolher um pivô, um elemento qualquer do vetor para ser o elemento que
dividirá o vetor em dois segmentos (sub-vetores), sendo estes os problemas menores da
estratégia. Esta divisão é lógica, e não fı́sica, como acontece com o MergeSort. Após esta
divisão, efetua-se um processo de separação dos demais elementos, tendo como parâmetro
de separação o valor do elemento escolhido como pivô.
Primeiramente, o vetor é varrido da esquerda para a direita, até que se encontre um
elemento a > pivô; e também da direita para a esquerda a fim de encontrar um elemento
b < pivô. Assim, achado os dois elementos a e b, faz-se a troca deles. Este processo
será realizado mais vezes, a partir de b e a, caso haja necessidade, até que todos os
elementos à esquerda do pivô sejam menores ou iguais a ele; e da mesma forma, todos os
elementos à sua direita sejam maiores ou iguais. Após esta etapa, o elemento escolhido
como pivô estará na sua posição correta em relação à ordenação do vetor. No caso de não
se conseguir escolher algum elemento em um dos segmentos, a troca é feita com o próprio
pivô. Após esta partição do vetor, realiza-se o processo de recursão para os segmentos.
Estes segmentos serão considerados como sendo vetores originais, assim também serão
particionados, gerando seus segmentos, de tamanho cada vez menor. Assim, o processo
de particionamento se repete até que se obtenha vetores contendo apenas uma posição, e
com isso, todos os pivôs serão atingidos e como estes estão em suas devidas posições, se
10
obtém a ordenação global.
O Quick Sort apresenta diferentes tempos de ordenação para os casos médio, mı́nimo
e máximo, pois dependem da escolha do pivô. Se o pivô for o elemento médio e mediano
(separando a mesma quantidade de elementos maiores e menores do que ele em cada lado)
em toda chamada da recursão, o tempo é mı́nimo, ou seja, O(n ∗ log(n)). Caso o pivô
seja o elemento maior ou menor em cada recursão, o tempo é máximo, ou seja, O(n2 ).
O tempo médio se obtém quando pega o pivô aleatoriamente ou o elemento médio. Isto
é necessário pois, quando o vetor já estiver ordenado, ao tomar o pivô como sendo o
primeiro elemento, cairá no pior caso do algoritmo. Então é recomendado escolher o pivô
aleatoriamente ou o elemento médio.
Caraterı́sticas:
• Ordena vetores ordenados e inversamente ordenados com velocidade praticamente
igual.
• Caso médio (pivô aleatório) é inferior ao caso ótimo diferindo apenas por um fator
logarı́tmico de 2 ∗ ln(2). Assim, o caso médio possui complexidade de tempo de
ordenação assintoticamente igual ao seu melhor caso.
• Preferência por vetores maiores e bastante desordenados.
• Se escolhendo no vetor o pivô como o elemento central, o caso ótimo do Quick Sort
é o vetor inicialmente ordenado.
• Considerando caso médio, o Quick Sort é de 2 a 3 vezes mais rápido do que o Heap
Sort (não-assintótico).
2.6
Heap Sort
O Heap Sort também conhecido como método de ordenação por árvores é baseado no
método de seleção direta. Este algoritmo utiliza um estrutura de dados chamada de heap,
que consiste em uma árvore cuja raiz é o elemento de menor valor, caso seja um heap de
mı́nimo, ou o de maior valor, caso seja um heap de máximo.
O Heap é uma estrutura de dados em forma de uma árvore, cuja raiz é o elemento
mı́nimo ou máximo, dependendo do tipo do heap. Para efetuar a construção do heap a
partir do vetor de entrada, o tempo gasto é O(n ∗ logn), em uma análise mais complexa
este tempo pode ser dado como O(n) [Wir86].
A figura 2.2 apresenta um exemplo de um heap.
Com heap construı́do o HeapSort apenas cria o heap a partir do vetor de entrada, e o
algoritmo apenas vai removendo do heap e colocando no vetor de saı́da.
11
Figura 2.2: Exemplo de um Heap de Máximo
Segundo [Wir86] o Heap Sort tem uma complexidade computacional na ordem de
O(n ∗ logn), mesmo no pior caso, este valor é calculado da seguinte maneira: para a
construção do heap é necessário O(n), e mais O(logn) para extrair os elementos do heap
. E o número médio de movimentos é de aproximadamente n/2 ∗ log(n).
O Heap Sort tem vantagem sobre o Merge Sort, pois não necessita de memória auxiliar,
mas uma boa implementação do Quick Sort é em geral mais rápido [Miy99].
Algumas caracterı́sticas do Heap Sort são descritas abaixo:
• O Heap Sort não é recomendado para vetores de entrada com poucos elementos,
devido a complexidade do heap;
• Quanto maior o vetor de entrada, mais eficiente este algoritmo é;
• Mesmo no pior caso, o Heap Sort é O(n ∗ logn), este excelente desempenho no pior
caso é uma das principais vantagens do Heap Sort;
• O Heap Sort é mais eficiente com vetores de entrada, cujos elementos estão parcialmente ordenados na ordem inversa, dando uma caracterı́stica não-natural ao
algoritmo;
• Se o vetor de entrada estiver na ordem inversa, o processo de construção do heap
leva zero movimentos para ser realizado.
2.7
Count Sort
Também conhecido como Counting Sort, é um método de ordenação linear, isto é, tem
complexidade O(n). Ele não se baseia em comparações, e sim em indexação. Para isso,
12
os valores a serem ordenados devem ser inteiros, pois estes serão usados como chaves no
vetor auxiliar por ele requisitado (repare que ele precisa de memória extra para trabalho,
porém não é recursivo). Assim, este algoritmo não funciona com entradas em ponto
flutuante, pois se usasse uma lista encadeada, seu desempenho possivelmente não seria
satisfatório, devido ao percurso na lista para cada busca. Ele necessita ainda que se saiba
a priori o valor do maior elemento k da entrada para criar o vetor auxiliar de contagem
dos elementos da entrada, cujos valores devem variar desde 0 até k. Importante observar
que O(k) deve ser linear para que o algoritmo também o seja, o que acontece na prática.
O algoritmo é formado por quatro laços de repetição que varrem ou o vetor original ou
o de trabalho. Primeiramente ele cria o vetor de trabalho e atribui zero a todas posições,
consumindo O(k). Depois varre o vetor original e incrementa as quantidades dos elementos
da entrada no vetor de trabalho utilizando a indexação. Assim, o tempo gasto é de apenas
O(n) pois a indexação consome tempo O(1). Agora ele percorre o vetor de trabalho a fim
de obter a quantidade de elementos menores ou iguais ao valor de cada posição. Para isso,
ele faz a soma do valor de uma posição com a anterior, começando pela segunda e indo
até a última. Este laço leva O(k). Por último, cursa o vetor de entrada ao contrário, para
assim garantir estabilidade. Essa propriedade é importante quando se trabalha com outros
dados junto ao elemento que sofrerá ordenação, mas para isso será necessário outro vetor
auxiliar, o vetor de saı́da. Este vetor, logicamente terá o mesmo tamanho da entrada, e
será preenchido da seguinte forma: o elemento de entrada será colocado na posição de
saı́da indicada pelo seu próprio valor no vetor de trabalho. Logo em seguida, decrementase o valor da contagem do vetor de trabalho na posição utilizada, para que, quando ocorra
repetição de elementos na entrada, estes não ocupem o mesmo lugar no vetor de saı́da.
Esta etapa também é O(n), e no total temos O(k)+O(n)+O(k)+O(n) = O(n), adotando
que O(k) é linear.
Finalmente, não é recomendado usar este algoritmo quando se tem um valor muito
grande de k, pois precisaria de muita memória e em muitos casos sem necessidade. Por
outro lado, é bom utilizá-lo quando a comparação dos elementos representar um problema,
pois este método usa operações aritméticas e atribuições para fazer a ordenação ao invés
de comparações.
2.8
Bucket Sort
Algoritmo baseado na idéia do uso de chaves como ı́ndices em um arranjo B de Buckets.
Tal arranjo, possui entradas no intervalo de 0 a [N − 1], onde N representa a quantidade
de chaves. Cada posição de B é uma lista de itens. Por exemplo, o elemento f será
armazenado em B[f ].
13
O Bucket Sort funciona da seguinte maneira: seja S a seqüência que deseja-se ordenar.
Cada elemento de S é inserido em seu Bucket. Em seguida, ordena-se os Buckets e o
conteúdo é devolvido em S.
Para garantir a estabilidade desse algoritmo, deve-se, segundo [Goo04] remover sempre o
primeiro elemento da seqüência S e das seqüências B[i].
O Bucket Sort possui tempo de execução O(n + N ) onde n representa a quantidade de
elementos na sequüência S. Apresenta bom desempenho quando N é pequeno se comparado com n.
No melhor caso, espera-se que cada elemento de S seja armazenado em um Bucket diferente e, em contrapartida, em seu pior caso, todos os elementos da seqüência são armazenados no mesmo Bucket.
2.9
Radix Sort
O Radix Sort é um algoritmo baseado no conceito de ordenação por contagem, que consiste
em criar uma tabela de N entradas, onde N é o número de elementos diferentes que pode
ser inseridos no vetor de entrada. E nesta tabela são inseridos contadores, incrementadoos se os mesmos forem correspondentes a chave de valor i, após realizado este processo,
é conhecido a quantidade de posições necessárias para cada valor de chave, assim os
elementos são transferidos para as posições corretas no novo vetor ordenado[Ric03].
O Radix Sort utiliza o conceito de ordenação por contagem, porém ele realiza a contagem com apenas uma parte da representação do elemento, a qual é denominada raiz.
O processo de contagem é realizado com esta parte várias vezes até que a representação
total do elemento seja analisada.
Duas classificações podem ser realizadas com o radix sort, LSD (Least Significant
Bits) e MSD (Most Significant Bits), que define a ordem que serão analisados as partes
do elemento, se LSD o processo é iniciado com os bits menos significativos e se MSD com
os bits mais significativos.
Com esta especificação do radix sort apresentada acima é possı́vel perceber que este algoritmo pode ser aplicado a ordenação de strings como um vetor de entrada [bg, bd, a, f k, f j, e]
sendo ordenado como [a, bd, bg, e, f j, f k]. Este algoritmo é muito utilizado para ordenação
lexicográfica.
Para ordenação de números inteiros o radix sort pode trabalhar uma maneira simples,
como a parte do elemento sendo um dı́gito do elemento, assim a ordenação pode ser feita
ordenando os dı́gitos menos signficativos para os mais significativos. Como é mostrado
no exemplo 2.2:
Exemplo 2.2 Dado o vetor de entrada [36, 0, 9, 25, 1, 49, 64, 16, 81, 4], realizando a or14
denação pelo dı́gito menos significativo, temos algo como mostrado na figura 2.3
Figura 2.3: Vetor ordenado pelo dı́gito menos significativo
Após isto, realiza-se a ordenação dos próximos dı́gitos, como neste caso os valores
são no máximo de dois dı́gitos, então na ordenação do próximo dı́gito o vetor já estará
ordenado, como é mostrado na figura 2.4.
Figura 2.4: Vetor ordenado
Uma desvantagem do Radix Sort é a necessidade de um espaço de memória auxiliar
de tamanho N , que é o tamanho do alfabeto dos elementos de entrada. Se a quantidade
de memória for limitada este é uma desvantagem significante deste algoritmo.
A complexidade computacional é da ordem de (i ∗ N ), onde i é o tamanho do vetor
de entrada, sendo então de complexidade temporal linear O(n).
15
Capı́tulo 3
Conclusão
Apresentamos, neste trabalho, alguns dos principais algoritmos de ordenação. Mostramos
as caracterı́sticas de cada um, analisando o tempo computacional no melhor, pior e médio
casos.
Através deste estudo, pode-se concluir que não existe um algoritmo de ordenação
que seja eficiente para todos os casos, já que para cada situação existe um algoritmo
que melhor a solucione. Um exemplo mostrado foi o caso do Merge Sort que funciona
melhor em situações onde a entrada não cabe toda na memória princial necessitando ser
armazenada em um meio de acesso mais lento e, em contrapartida, o Quick Sort, se bem
implementado, é um dos algotimos mais rápidos quando a entrada está toda em memória.
Podem ser realizadas pequenas modificações nos algoritmos originais, a fim de garantir caracterı́sticas extras, como no caso do Bucket Sort, onde a estabilidade é garantida
através da remoção do primeiro elemento de cada seqüência.
16
Apêndice A
Pseudo-Código do Algoritmo de ordenação Bubble Sort
Algoritmo segundo [Wir86]:
BubbleSort(vetor A,n)
1.
2.
para i ← 0 ate n faca
para j ← n - 1 decrescendo ate j = i faca
3.
se A[j] < A[j - 1] entao
4.
Troque(A[j] , A[j - 1]);
5.
6.
7.
fim se
fim para
fim para
fim do algoritmo
Pseudo-Código do Algoritmo de ordenação Insertion
Sort
Algoritmo segundo [Miy99]:
InsertionSort(Vetor V , Inteiro n)
1.
j←2
2.
enquanto j ≤ n faça
3.
AU X ← V [j];
4.
i ← j − 1;
5.
enquanto i > 0 e V [i] > AU X faça
6.
V [i + 1] ← V [i];
7.
j ← j − 1;
8.
fim enquanto
9.
V [i + 1] ← AU X;
10.
j ← j + 1;
11.
fim enquanto
fim do algoritmo
17
Pseudo-Código do Algoritmo de ordenação Selection
Sort
Algoritmo segundo [Wir86]:
SelectionSort(A,tam)
1.
2.
para i ← 1 ate tam faca
min ← i;
para j ← i + 1 ate tam faca
3.
4.
se A[min] > A[j]
5.
min ← j;
6.
fim se
7.
fim para
8.
se i 6= min
A[min] ← A[i];
9.
10
11.
fim se
fim para
fim do algoritmo
Pseudo-Código do Algoritmo de ordenação Merge Sort
Algoritmo segundo [Miy99]:
MergeSort(Vetor V, inicio, f im)
1.
se inicio < f im então
2.
im
meio ← b inicio+f
c
2
3.
MergeSort(V , inicio, meio);
4.
MergeSort(V , meio + 1, f im);
5.
Juncao(V [inicio..meio], V [meio + 1..f im], V );
6.
fim se
fim do algoritmo
Método auxiliar do Merge Sort
Junção(S1 ,S2 , S):
% Entrada sequência S1 e S2 ordenadas de forma não-decrescente e uma sequência S vazia.
% Saida sequência S contendo os elementos de S1 e S2 ordenados de
forma não-decrescente com as sequências S1 e S2 tornando-se vazias
18
1.
2.
enquanto S1 ou S2 não forem vazias faca
se S1 .firstElement() ≤ S2 .firstElement() então
3.
{remova o primeiro elemento de S1 para o final de S}
4.
S.insertLast(S1 .removeFirst())
5.
senão
6.
{remova o primeiro elemento de S2 para o final de S}
7.
S.insertLast(S2 .removeFirst())
8.
{remova os elementos restantes de S1 para S}
9.
enquanto(nãoS1 .isEmpty()) faça
10.
S.insertLast(S1 .removeFirst())
11.
{remova os elementos restantes de S2 para S}
12.
enquanto(nãoS2 .isEmpty()) faça
13.
S.insertLast(S2 .removeFirst())
fim do algoritmo
Pseudo-Código do Algoritmo de ordenação Quick Sort
Algoritmo segundo [Miy99]:
QuickSort(vetor V, inicio, fim)
1.
se inicio < fim entao
2.
meio ← Particiona( V, inicio, fim )
3.
QuickSort( V, inicio, meio -1 );
4.
QuickSort( V, meio + 1, fim );
5.
fim se
fim algoritmo
Método auxiliar do Quick Sort
Particiona(vetor V, inicio, fim)
1.
Pivo ← V[inicio];
2.
ESQ ← inicio + 1;
3.
DIR ← fim;
4.
enquanto ESQ < DIR faca
5.
enquanto V[ESQ] ≤ Pivo e ESQ ≤ fim faca ESQ ← ESQ + 1;
6.
enquanto V[DIR] > Pivo e DIR ≥ inicio faca DIR ← DIR - 1;
7.
se ESQ < DIR entao Troque(V[ESQ], V[DIR]);
8.
fim enquanto
9.
MEIO ← DIR;
19
10.
Troque(V[inicio, V[MEIO]]);
11.
Retorne MEIO;
fim do algoritmo
Pseudo-Código do algoritmo de Ordenação Heap Sort
Algoritmo segundo [Miy99]:
HeapSort(A,i)
1.
ConstroiHeap(A,i);
2.
para i ← n decrescendo ate 1 faca
3.
A[i] ← ExtraiMax(A,i);
fim do algoritmo
Métodos auxiliares do Heap Sort
ConstroiHeap(A,n)
1.
2.
para i ← [ n2 ] decrescendo ate 1 faca
Rebaixa(A,n,i);
fim do algoritmo
Rebaixa(A,n,i)
1.
pai ← i;
2.
fesq ← FilhoEsq(i);
3.
fdir ← FilhoDir(i);
4.
maior ← pai;
5.
se fesq 6 n e A[fesq] > A[pai]
6.
entao maior ← fesq;
7.
se fdir 6 n e A[fdir] > A[maior]
8.
entao maior ← fdir;
9.
se maior 6= pai entao
10.
Troca(A[maior], A[pai]);
11.
Rebaixa(A,n,maior);
fim do algoritmo
ExtraiMax(A,n,i)
1.
se n < 1 erro;
2.
max ← A[1];
3.
A[1] ← A[n];
4.
n ← n - 1;
20
5.
Rebaixa(A,n,1);
6.
retorne max;
fim do algoritmo
Pseudo-Código do Algoritmo de ordenação Count Sort
Algoritmo segundo [Miy99]:
CountSort(A,B,n,k)
1.
2.
3.
4.
5.
6.
7.
para i ← 1 ate k faca
C[i] ← 1; % inicializa contadores com 0
para j ← 1 ate n faca
C[A[i]] ← C[A[i]] +1;
para i ← 2 ate k faca
C[i] ← C[i] + C[i - 1];
para j ← n decrescendo ate 1 faca
8.
B[C[A[j]]] ← A[j];
9.
C[A[j]] ← C[A[j]] - 1;
fim do algoritmo
Pseudo-Código do Algoritmo de ordenação Bucket Sort
Algoritmo segundo [Miy99]:
BucketSort(S)
1.
Entrada: seqüência S de itens com chaves inteiras no intervalo [0, N − 1]
2.
Saida: seqüência S ordenada pelas chaves, de forma não-decrescente
3.
seja B um arranjo de N seqüências, cada uma inicalmente vazia
4.
para cada item x em S faça
5.
seja k a chave de x
6.
remove x de S e o insere no fim da seqüência B[k]
7.
fim para
8.
para i ← 0 ate N − 1 faça
9.
para cada item x da seqüência B[i] faça
10.
11.
12.
remove x de B[i] e o insere no fim de S
fim para
fim para
fim do algoritmo
21
Pseudo-Código do Algoritmo de Ordenação Radix Sort
Algoritmo segundo [Miy99]:
RadixSort(A,n,d)
1.
2.
para i ← 1 ate d faca
Use um algoritmo estavel para ordenar o array A no digito i.
fim do algoritmo
22
Referências Bibliográficas
[Goo04] Michael T. Goodrich. Projeto de algoritmos: Fundamentos, análise e exemplos
da Internet. Editora Bookman, 2004.
[Miy99] F. K. Miyazawa. Notas de complexidade de algoritmos. Universidade Estadual
de Campinas, 1999.
[Ric03] Ivan L. M. Ricarte.
Ordenação por contagem.
Disponı́vel em:
http://www.dca.fee.unicamp.br/cursos/EA876/apostila/HTML/node24.html.
Acessado em: 09 Ago. 2007, 2003.
[Wir86] Niklaus. Wirth. Algoritmos e Estruturas de Dados. Editora Prentice Hall, 1986.
23