APS-UNIP

Prévia do material em texto

Universidade Paulista 
Ciência da Computação 
 
 BRENO ASSUNÇÃO - F05EEF9 
 DENILSON ABDON – N459FH4 
 FERNANDO FILIPE –N433221 
 JEFFERSON MATHEUS – F09IEG4 
 RENATO RODRIGUES – F0369D0 
 
 
 
DESENVOLVIMENTO DE SISTEMA ANÁLISE DE PERFORMANCE DE 
ALGORITMO DE ORDENAÇÃO DE DADOS 
 
 
 
 
 
 
 
 
 
 
Manaus-Am 
2020 
BRENO ASSUNÇÃO DE ALMEIDA 
 DENILSON ABDON OLIVEIRA 
 FERNANDO FILIPE DA SILVA COSTA 
 JEFFERSON MATHEUS LIMA GONSALVES 
 RENATO RODRIGUES MENDES DA SILVA FILHO 
 
 
 
 
 
 
 
 
DESENVOLVIMENTO DE SISTEMAS PARA ANÁLISE DE PERFOMANCE 
DE ALGORITMOS DE ORDENAÇÃO DE DADOS. 
 
 
Atividade prática supervisionada e 
apresentada ao curso Ciência da 
Computação, para fins de conhecimento 
na área. Orientador: Prof: Waterloo Silva 
 
 
 
Manaus - Am 
2020 
SUMÁRIO 
1 Introdução..............................................................................................................4 
2 Objetivos................................................................................................................5 
2.1 Geral....................................................................................................................5 
2.2 Especificos...........................................................................................................5 
3 Algoritmo de ordenação......................................................................................5 
3.1 Definição...............................................................................................................5 
4 Natureza dos dados...............................................................................................6 
5 Tipos de Algoritmo de ordenação.........................................................................7 
5.1 Bubble sort ...........................................................................................................7 
5.1.2 Heap sort ...........................................................................................................8 
5.1.3 Insertion sort ...................................................................................................10 
5.1.4 Merge sort .......................................................................................................12 
5.1.5 Quicksort..........................................................................................................16 
6 Contribuição do trabalho na nossa formação....................................................24 
7 Relatório com as linhas de códigos do programa.............................................25 
8 Apresentação do programa em funcionamento em um computador..............30 
9 Referencias............................................................................................................31 
 
 
 
 
 
 
 
 
 
4 
1 Introdução 
Os computadores são máquinas que manipulam dados e informações. A 
computação envolve o estudo de como a informação é organizada, manipulada e 
usada em um computador. 
 
Um aspecto marcante da sociedade atual é a automação de tarefas, e na 
ciência da computação existe um processo de desenvolvimento simultâneo e 
interativo de máquinas e elementos lógicos que gerenciam a execução automática 
de uma tarefa. 
 
Ao criar um programa de processamento de dados, é necessário transcrever 
para que o computador entenda e execute o programa, e o programador também 
entenda o que escreveu. Linguagens de programação são códigos escritos em uma 
linguagem que um programador entende e que o computador pode interpretar e 
executar. 
 
A partir do tópico DESENVOLVIMENTO DE SISTEMAS PARA ANÁLISE DE 
PERFOMANCE DE ALGORITMOS DE ORDENAÇÃO DE DADOS, comecei a 
pesquisar os principais métodos de ordenação para descobrir qual deles é mais 
funcional. 
O conceito de ordenação nada mais é do que uma forma de organizar a 
informação e organizá-la em uma ordem pré-determinada, então existem vários 
métodos que temos hoje que são fundamentais no desenvolvimento de algoritmos 
feitos para diferentes funcionalidades usadas de diferentes maneiras. 
 
 
5 
2 Objetivos 
2.1 Geral 
Pesquisar e dissertar sobre DESENVOLVIMENTO DE SISTEMA ANÁLISE 
DE PERFORMANCE DE ALGORITMO DE ORDENAÇÃO DE DADOS. 
2.2 Específicos 
 Pesquisar e dissertar sobre os 
conceitos gerais de algoritmos de ordenação 
 Pesquisar e dissertar sobre natureza 
dos dados 
 Pesquisar e dissertar sobre Bubble 
sort 
 Pesquisar e dissertar sobre heap 
sort 
 Pesquisar e dissertar sobre insertion 
sort 
 Pesquisar e dissertar sobre merge 
sort 
 Pesquisar e dissertar sobre quicksort 
 
3 Algoritmo de ordenação 
3.1 definição 
Ordenação é o ato de se colocar os elementos de uma sequência de 
informações, ou dados, em uma relação de ordem predefinida. O termo técnico em 
inglês para ordenação é sorting, cuja tradução literal é "classificação". 
Dado uma sequência de n dados: 
6 
 
O problema de ordenação é uma permutação dessa seqüencia: 
 
 , 
 ,... 
 
 tal que: 
 
 
 
 
 
para alguma relação de ordem. 
 
Alguns pedidos são fáceis de definir. Por exemplo, ordem numérica ou ordem 
alfabética - aumento ou diminuição. No entanto, algumas ordens (especialmente 
dados compostos) são importantes para estabelecer. 
Um algoritmo para classificar uma coleção (geralmente representado por um 
vetor) é chamado de algoritmo de classificação. Um algoritmo de classificação em 
ciência da computação é um algoritmo que coloca os elementos de uma 
determinada sequência em uma ordem específica - em outras palavras, executa sua 
classificação no todo ou em parte. A ordem mais comumente usada é a ordem 
numérica e a ordem do dicionário,.Há vários motivos para fazer o pedido. Uma é 
acessar seus dados com mais eficiência. 
Mais importante, podemos mencionar bubble sort (ou ordenação por 
flutuação), heap sort (ou ordenação por heap), insertion sort (ou ordenação por 
inserção), merge sort (ou ordenação por mistura) e o quicksort. Selection Sort, 
Bubble Sort e Quicksort exitem diversos outros tipos de algoritmo de ordenação. 
4 Natureza dos dados 
Para escolher melhor o método de ordenação, é necessário entender a 
natureza dos dados a serem processados. Dentre eles, dois se destacam: o tempo 
de acesso ao elemento e a possibilidade de acesso direto ao elemento. 
7 
O tempo de acesso a um elemento é a complexidade necessária para 
acessar um elemento em uma estrutura; 
1 Ex: Uma estante de livros com seu títulos bem visíveis. 
A possibilidade de acesso direto é a capacidade ou impossibilidade de 
acessar um elemento diretamente na estrutura. 
1 Ex: Uma pilha de livros dentro de uma caixa, onde precisamos tirar 
um a um para saber qual a sua natureza. 
Para classificarmos estes dois ambientes de atuação, costumamos utilizar o 
meio em que está armazenado os dados. 
 Em termos computacionais utiliza-se a designação Ordenação Interna, 
quando queremos ordenar informações em memória. E Ordenação Externa, quando 
queremos ordenar informações em arquivo. 
5 Tipos de Algoritmo de ordenação 
5.1 Bubble sort 
O bubble sort, ou ordenação por flutuação (literalmente "por bolha"), é 
um algoritmo de ordenação dos mais simples. A ideia é percorrer o vector diversas 
vezes, e a cada passagem fazer flutuar para o topo o maior elemento da sequência. 
Essa movimentação lembra a forma como as bolhas em um tanque de água 
procuram seu próprio nível, e disso vem o nome do algoritmo. 
No melhor caso, o algoritmo executa operações relevantes, onde 
 representa o número de elementos do vector. No pior caso, são feitas 
operações. 
 A complexidade desse algoritmo é de ordem quadrática. Por isso, ele não é 
recomendado para programas que precisem develocidade e operem com 
quantidade elevada de dados. 
Em Pseudocódigo 
https://pt.wikipedia.org/wiki/Algoritmo_de_ordena%C3%A7%C3%A3o
https://pt.wikipedia.org/wiki/Vector
https://pt.wikipedia.org/wiki/Tanque_(reservat%C3%B3rio)
https://pt.wikipedia.org/wiki/Complexidade
https://pt.wikipedia.org/wiki/Algoritmo
https://pt.wikipedia.org/wiki/Ordem_quadr%C3%A1tica
8 
O algoritmo percorre a lista de itens solicitáveis do início ao fim, verifica a 
ordem dos elementos um a um e altera a posição, se necessário. Percorra a lista até 
que nenhum elemento tenha sido alterado no parágrafo anterior. 
 
procedure bubbleSort( A : lista de itens ordenaveis ) defined as: 
 do 
 trocado := false 
 for each i in 0 to length( A ) - 2 do: 
 // verificar se os elementos estão na ordem certa 
 if A[ i ] > A[ i + 1 ] then 
 // trocar elementos de lugar 
 trocar( A[ i ], A[ i + 1 ] ) 
 trocado := true 
 end if 
 end for 
 // enquanto houver elementos sendo reordenados. 
 while trocado 
end procedure 
5.1.2 heapsort 
O algoritmo heapsort é um algoritmo de ordenação generalista, e faz parte da 
família de algoritmos de ordenação por seleção. Foi desenvolvido em 1964 por 
Robert W. Floyd e J.W.J Williams. 
 
Ele tem um bom desempenho de tempo de execução em coleções 
classificadas aleatoriamente, tem um bom uso de memória e o desempenho do pior 
caso é realmente igual ao desempenho do meio. No pior caso, alguns algoritmos de 
classificação rápida têm um desempenho muito ruim em tempo de execução ou uso 
de memória. 
A classificação de heap está em vigor e o tempo de execução do pior caso 
para classificar n elementos é O (n log n). O logaritmo (ou logaritmo) do logaritmo (n) 
baseado em n é lido. Para o valor de n (bastante grande), o termo log n é quase 
 
 
https://pt.wikipedia.org/wiki/Algoritmo
https://pt.wikipedia.org/wiki/Algoritmo_de_ordena%C3%A7%C3%A3o
https://pt.wikipedia.org/wiki/Ordena%C3%A7%C3%A3o_por_sele%C3%A7%C3%A3o
9 
 constante, portanto, o tempo de ordenação é quase linear com o número de 
itens a serem ordenados. 
A classificação de heap não é um algoritmo de ordenação estável. No 
entanto, a estrutura a ser solicitada pode ser ajustada para estabilizar o pedido. 
Cada elemento da estrutura adaptada deve ser pareado (elemento original, índice 
original). Portanto, se os dois elementos forem iguais, o desempate ocorrerá por 
meio do índice na estrutura original. 
O heapsort utiliza uma estrutura de dados chamada heap, para ordenar os 
elementos à medida que os insere na estrutura. Assim, ao final das inserções, os 
elementos podem ser sucessivamente removidos da raiz da heap, na ordem 
desejada, lembrando-se sempre de manter a propriedade de max-heap. 
A heap pode ser representada como uma árvore (uma árvore binária com 
propriedades especiais[1]) ou como um vetor. Para uma ordenação decrescente, 
deve ser construída uma heap mínima (o menor elemento fica na raiz). Para uma 
ordenação crescente, deve ser construído uma heap máxima (o maior elemento fica 
na raiz). 
Funcionamento do heap em C 
void heapsort(int a[], int n) { 
 int i = n / 2, pai, filho, t; 
 while(true) { 
 if (i > 0) { 
 i--; 
 t = a[i]; 
 } else { 
 n--; 
 if (n <= 0) return; 
 t = a[n]; 
https://pt.wikipedia.org/wiki/Heap
https://pt.wikipedia.org/wiki/Heapsort#cite_note-2
10 
 a[n] = a[0]; 
 } 
 pai = i; 
 filho = i * 2 + 1; 
 while (filho < n) { 
 if ((filho + 1 < n) && (a[filho + 1] > a[filho])) 
 filho++; 
 if (a[filho] > t) { 
 a[pai] = a[filho]; 
 pai = filho; 
 filho = pai * 2 + 1; 
 } else { 
 break; 
 } 
 } 
 a[pai] = t; 
 } 
} 
 
5.1.3 insertion sort 
Insertion Sort, ou ordenação por inserção, é um algoritmo de ordenação que, 
dado uma estrutura (array, lista) constrói uma matriz final com um elemento de cada 
vez, uma inserção por vez. Assim como algoritmos de ordenação quadrática, é 
bastante eficiente para problemas com pequenas entradas, sendo o mais eficiente 
entre os algoritmos desta ordem de classificação. 
 
11 
Podemos comparar a insertion sort com a maneira como algumas pessoas 
organizam seus baralhos em um jogo de cartas. Suponha que você esteja jogando 
cartas. Você tem cartas na mão, elas estão em ordem. 
Você receberá um novo cartão, que deve ser colocado na posição correta da 
mão do cartão para que o cartão obedeça ao pedido. 
Depois de adicionar cada nova carta à sua mão, a nova carta pode ser 
menor ou maior do que algumas cartas que você já tem em sua mão, então você 
pode comparar a nova carta com todas as cartas em sua mão até encontrar sua 
própria carta. O local certo. Você insere o novo cartão na posição correta e, em 
seguida, suas mãos são compostas de cartas. Você receberá outra carta e repetirá o 
mesmo processo. Em seguida, outra carta e assim por diante, até que nunca mais 
recebesse outra carta. 
Essa é a ideia por trás do pedido de veiculação. Percorra a posição da 
matriz a partir do índice 1 (um). Cada nova posição é como a nova letra que você 
recebeu e você precisa inseri-la na posição correta na submatriz do lado esquerdo 
da posição. 
Vantagens e desvantagem 
Vantagens 
 É o método a ser utilizado quando o arquivo está "quase" ordenado 
 É um bom método quando se desejar adicionar poucos elementos em 
um arquivo já ordenado, pois seu custo é linear. 
 O algoritmo de ordenação por inserção é estável. 
Desvantagem 
 Alto custo de movimentação de elementos no vetor 
Implementação em pseudocódigo 
12 
Esta é uma versão simples do pseudocódigo do algoritmo, o vetor começa do 
zero:. 
FUNÇÃO INSERTION_SORT (A[], tamanho) 
 VARIÁVEIS 
 i, j, eleito 
 PARA i <- 1 ATÉ (tamanho-1) FAÇA 
 eleito <- A[i]; 
 j <- i-1; 
 ENQUANTO ((j>=0) E (eleito < A[j])) FAÇA 
 A[j+1]:= A[j]; 
# Elemento de lista numerada 
 j:=j-1; 
 FIM_ENQUANTO 
 A[j+1] <- eleito; 
 FIM_PARA 
FIM 
 
Nesta versão, verifique o acréscimo para ver se é necessário estar em sua 
nova posição, ou seja, se não houver troca, não há necessidade de reescrever o 
valor, pois ele já “inseriu” no “eleito” no lugar certo. 
FUNÇÃO INSERTION_SORT (A[], tamanho) 
 VARIÁVEIS 
 i, ,j 
 eleito 
 PARA i <- 1 ATÉ tamanho-1 FAÇA 
 eleito <- A[i]; 
 j <- i-1; 
 ENQUANTO ((j>=0) E (eleito < A[j])) FAÇA 
 A[j+1]:=v[j]; 
 j:=j-1; 
 FIM_ENQUANTO 
 SE ((j) <> (i-1) ENTÃO //se for diferente teve troca 
de posições anteriormente 
 A[j+1] <- eleito; //escreve na nova posição 
 FIM_PARA 
FIM 
 
5.1.4 merge sort 
 
13 
O merge sort, ou ordenação por mistura, é um exemplo de algoritmo de 
ordenação por comparação do tipo dividir-para-conquistar. 
Suas idéias básicas incluem divisão (problemas em vários subproblemas, e 
então resolver recursivamente esses subproblemas) e conquistar (depois que todos 
os subproblemas são resolvidos, ocorre a conquista, que é a união das soluções dos 
subproblemas). Como o algoritmo de classificação por mesclagem usa recursão, há 
uma grande quantidade de consumo de memória e tempo de execução, o que torna 
essa técnica não muito eficaz em alguns problemas. 
Como funciona o Merge Sort? 
A ideia de merge sort é dividir o vetor em dois sub-vetores, cada um dos 
quais com metade dos elementos do vetor original. Em seguida, o processo é 
aplicado recursivamente aos dois subvetores. 
 
Quando o sub-vetor tem apenas um elemento (o caso base), a recursãopara. Em seguida, mescle (ou mescle) os subvetores ordenados em um único vetor 
ordenado. 
 
Por exemplo, classificaremos o vetor [5, 2, 7, 6, 2, 1, 0, 3, 9, 4]. Inicialmente, 
dividimos o vetor em dois sub-vetores, cada um com metade dos elementos originais 
do vetor. 
 
 
 Reaplicamos o método aos dois subvetores 
 
https://pt.wikipedia.org/wiki/Ordena%C3%A7%C3%A3o_(computa%C3%A7%C3%A3o)
https://pt.wikipedia.org/wiki/Ordena%C3%A7%C3%A3o_por_compara%C3%A7%C3%A3o
https://pt.wikipedia.org/wiki/Ordena%C3%A7%C3%A3o_por_compara%C3%A7%C3%A3o
https://pt.wikipedia.org/wiki/Divis%C3%A3o_e_Conquista
14 
 
 De novo, 
 
Mais uma vez, pois ainda não alcançamos o caso base em alguns 
subvetores. 
 
Finalmente, fazemos a fusão dos subvetores. 
 
 
 
O diagrama a seguir ilustra todas as etapas 
 
 https://www.blogcyberini.com/2018/07/merge-sort.html 
 
Algumas observações 
 É possível implementar o merge sort utilizando somente um 
vetor auxiliar ao longo de toda a execução, tornando assim a complexidade 
de espaço adicional igual a . 
 É um algoritmo estável na maioria das implementações, em que 
elas podem ser iterativas ou recursivas. 
 É possível também implementar o algoritmo com espaço 
adicional . 
 Algoritmo Criado por Von Neumann em 1945. 
 
Desvantagens 
https://pt.wikipedia.org/wiki/Von_Neumann
https://pt.wikipedia.org/wiki/1945
15 
Utiliza funções recursivas; 
Gasto extra de memória. O algoritmo cria uma cópia do vetor para cada nível 
da chamada recursiva, totalizando um uso adicional de memória igual a . 
Implementação do merge sort em C. 
void merge(int vetor[], int comeco, int meio, int fim) { 
 2 int com1 = comeco, com2 = meio+1, comAux = 0, tam = fim-
comeco+1; 
 3 int *vetAux; 
 4 vetAux = (int*)malloc(tam * sizeof(int)); 
 5 
 6 while(com1 <= meio && com2 <= fim){ 
 7 if(vetor[com1] < vetor[com2]) { 
 8 vetAux[comAux] = vetor[com1]; 
 9 com1++; 
10 } else { 
11 vetAux[comAux] = vetor[com2]; 
12 com2++; 
13 } 
14 comAux++; 
15 } 
16 
17 while(com1 <= meio){ //Caso ainda haja elementos na primeira 
metade 
18 vetAux[comAux] = vetor[com1]; 
19 comAux++; 
20 com1++; 
21 } 
22 
23 while(com2 <= fim) { //Caso ainda haja elementos na segunda 
metade 
24 vetAux[comAux] = vetor[com2]; 
25 comAux++; 
26 com2++; 
27 } 
28 
29 for(comAux = comeco; comAux <= fim; comAux++){ //Move os 
elementos de volta para o vetor original 
30 vetor[comAux] = vetAux[comAux-comeco]; 
31 } 
32 
33 free(vetAux); 
34 } 
 
 
 
 
 
16 
 
 
36 void mergeSort(int vetor[], int comeco, int fim){ 
37 if (comeco < fim) { 
38 int meio = (fim+comeco)/2; 
39 
40 mergeSort(vetor, comeco, meio); 
41 mergeSort(vetor, meio+1, fim); 
42 merge(vetor, comeco, meio, fim); 
43 } 
44 } 
 
5.1.5 Quicksort 
O algoritmo quicksort é um método de ordenação muito rápido e eficiente, 
inventado por C.A.R. Hoare [1] em 1960, ele visitou a Universidade de Moscou como 
estudante. Naquela época, Hoare trabalhava em projetos de tradução automática 
para o Laboratório Nacional de Física. Ao tentar traduzir um dicionário de inglês para 
o russo, ele criou o quicksort para ordenar as palavras, com o objetivo de reduzir o 
problema inicial a subproblemas que podem ser resolvidos de forma mais rápida e 
fácil. Após uma série de melhorias, o livro foi publicado em 1962. Quicksort é um 
algoritmo de ordenação por comparação instável. 
 
Algoritmo computacional 
Quicksort adota uma estratégia de dividir para conquistar. A estratégia é 
reorganizar as chaves de forma que a chave "menor" venha antes da chave "maior". 
Em seguida, o quicksort classifica as duas sublistas das chaves menores e maiores 
recursivamente até que a lista inteira seja classificada. Essas etapas são: 
A seleção de um elemento da lista é chamada de pivô; 
Patrocinia: reorganize a lista para que todos os elementos antes do pivô 
sejam menores do que a lista e todos os elementos após o pivô sejam maiores do 
 
17 
que a lista. No final do processo, o pivô estará em sua posição final, e 
haverá duas sublistas não ordenadas. Essa operação é chamada de participação; 
Recursivamente ordene a sub lista dos elementos menores e a sub lista dos 
elementos maiores; 
O caso básico de recursão é zero ou uma lista de tamanho, que é sempre 
ordenada. Este processo é limitado, pois cada iteração colocará pelo menos um 
elemento em sua posição final, e não será mais manipulado na próxima iteração. 
A escolha do pivô e os passos do Particiona podem ser feitos de diferentes 
formas e a escolha de uma implementação específica afeta fortemente a 
performance do algoritmo. 
Método de participação de lomuto 
Atribuído ao método de Nico Lomuto e promovido por Bentley em seu 
"Pérolas de programação" e Cormen et al. No livro Introdução aos Algoritmos. Este 
método geralmente seleciona o pivô no início ou no final da matriz. Como 
parâmetros, a Partiona recebe os dois índices lo e hi da matriz, que farão parte da 
matriz a ser particionada, e então seleciona um índice, ou seja, percorre a matriz 
com outro índice e muda se necessário para que todos sejam menores ou iguais ao 
pivô Os elementos do eixo estão antes do índice, ou seja, os elementos i + 1 a hi ou 
j-1 são maiores que o pivô. 
Esta é a maneira mais simples e fácil de entender, geralmente utilizada 
como uma introdução ao quicksort, entretanto é menos eficiente que o método 
Hoare. Este Método decai para O(n2) quando o array já está orden ado ou quando 
só possui elementos iguais. Existem várias formas para melhorar a eficiência do 
algoritmo através da escolha do pivô, lidar com elementos iguais, usar outros 
algoritmos para pequenos arrays como o Insertion sort e assim por diante. 
Complexidade 
Complexidade de tempo: 
https://pt.wikipedia.org/wiki/Recursividade_(ci%C3%AAncia_da_computa%C3%A7%C3%A3o)
https://pt.wikipedia.org/wiki/Insertion_sort
18 
Quando o elemento pivô divide a lista desbalanceada, ocorre o pior caso de 
particionamento, ou seja, a lista é dividida em duas sublistas: uma sublista tem 
tamanho 0 e a outra tem tamanho n-1 (onde n significa O tamanho da lista original)). 
Isso pode acontecer quando o elemento pivô é o maior ou o menor elemento da 
lista, ou seja, quando a lista já está ordenada ou invertida. 
 
Se isso acontecer em todas as chamadas de método de partição, cada 
etapa recursiva chamará uma lista-1 do mesmo tamanho da lista anterior. Portanto, 
teremos a seguinte relação recursiva: 
 
 
Se somarmos os custos em cada nível de recursão, teremos uma série 
aritmética que tem valor , assim, o algoritmo terá tempo de execução igual à 
 . 
Comportamento no melhor caso 
O melhor caso de particionamento acontece quando ele produz duas listas 
de tamanho não maior que n/2, uma vez que uma lista terá tamanho [n/2] e outra 
tamanho [n/2] - 1. Nesse caso, o quicksort é executado com maior rapidez. A relação 
de recorrência é a seguinte: 
 
 
 
 
que, a partir do teorema mestre, terá solução 
Complexidade de espaço: no melhor caso e no caso médio e : 
no pior caso. R. Sedgewick desenvolveu uma versão do quicksort com partição 
recursão de cauda que tem complexidade : ( ) no pior caso. 
Implementação 
19 
Em pseudocódigo, o quicksort ordena elementos do índice até de um 
array A pode ser escrito da seguinte forma: 
procedimento QuickSort(X[], IniVet, FimVet) 
var 
 i, j, pivo, aux 
início 
 i <- IniVet 
 j <- FimVet 
 pivo <- X[(IniVet + FimVet) div 2] 
 enquanto(i <= j) 
 | enquanto (X[i] < pivo) faça 
 | | i <- i + 1 
 | fimEnquanto| enquanto (X[j] > pivo) faça 
 | | j <- j - 1 
 | fimEnquanto 
 | se (i <= j) então 
 | | aux <- X[i] 
 | | X[i] <- X[j] 
 | | X[j] <- aux 
 | | i <- i + 1 
 | | j <- j - 1 
 | fimSe 
 fimEnquanto 
 se (IniVet < j) então 
 | QuickSort(X, IniVet, j) 
 fimSe 
 se (i < FimVet) então 
 | QuickSort(X, i, FimVet) 
 fimSe 
fimProcedimento 
ou de outra maneira, como: 
algorithm quicksort(A, lo, hi) is 
 if lo < hi then 
 p := particiona(A, lo, hi) 
 quicksort(A, lo, p – 1) 
 quicksort(A, p + 1, hi) 
 
algorithm particiona(A, lo, hi) is 
 pivot := A[hi] 
 i := lo - 1 
 for j := lo to hi - 1 do 
 if A[j] < pivot then 
 
 
 
 
20 
 i := i + 1 
 swap A[i] with A[j] 
 if pivot < A[i + 1] then 
 swap A[i + 1] with A[hi] 
 return i + 1 
 
Uma versão em C++ do primeiro pseudocódigo é expressa da seguinte 
maneira: 
#include <iostream> 
 
void quicksort(int values[], int began, int end) 
{ 
 int i, j, pivo, aux; 
 i = began; 
 j = end-1; 
 pivo = values[(began + end) / 2]; 
 while(i <= j) 
 { 
 while(values[i] < pivo && i < end) 
 { 
 i++; 
 } 
 while(values[j] > pivo && j > began) 
 { 
 j--; 
 } 
 if(i <= j) 
 { 
 aux = values[i]; 
 values[i] = values[j]; 
 values[j] = aux; 
 i++; 
 j--; 
 } 
 } 
 if(j > began) 
 quicksort(values, began, j+1); 
 if(i < end) 
 quicksort(values, i, end); 
} 
 
int main(int argc, char *argv[]) 
{ 
 int array[10] = {5, 8, 1, 2, 7, 3, 6, 9, 4, 10}; 
 for(int i = 0; i < 10; i++) 
 { 
 std::cout << array[i] << ' '; 
 } 
 
 
 
21 
 std::cout << std::endl; 
 quicksort(array, 0, 10); 
 for(int i = 0; i < 10; i++) 
 { 
 std::cout << array[i] << ' '; 
 } 
 return 0; 
} 
Tendo os valores como saída respectivamente, desorganizados e 
organizados através da função quicksort; 
5 8 1 2 7 3 6 9 4 10 
1 2 3 4 5 6 7 8 9 10 
 
Quicksort utilizando dois ou mais pivôs 
Dentre as muitas tentativas de melhorar a eficiência do Quicksort clássico, 
Yaroslavskiy (2009) propôs o Quicksort Dual-Pivot [6] em 2009, que usa 2 pivôs para 
dividir a matriz de entrada em 3 partes. Yaroslavskiy provou que é mais eficaz usar 
dois pivôs, especialmente quando o volume de dados de entrada é grande, o que 
prova sua vantagem sobre o algoritmo de ordenação quicksort clássico. 
O algoritmo Dual-Pivot Quicksort, particiona um array de entrada de dados de 
diferentes dados primitivos (tais como, int, char, double float e long) em três partes, 
utilizando dois pivôs P1 e P2. Desse modo, estabelecem os seguintes ponteiros, L, 
K, G e left e right(índices para o primeiro e último elementos). 
Segue abaixo a descrição do algoritmo. 
1. Para pequenos vetores (tamanho < 17) utilizar o 
algoritmo Insertion Sort. 
2. Escolha dois pivôs (P1 e P2), podemos escolher por exemplo, o 
primeiro (a[left]) elemento como P1 e o último como P2. 
 
22 
https://pt.wikipedia.org/wiki/Insertion_sort
3. P1 deve ser menor do que o P2, caso contrário, eles são 
trocados. Então, existem as seguintes partes: 
1. Parte I: com índices elemento mais a esquerda, de left até 
L-1 contendo os elementos que são menores que o P1. 
2. Parte II: com índices de L até K-1 contendo os elementos 
maiores ou iguais a P1 e menores ou iguais a P2. 
3. Parte III: Com índices de G + 1 até o último elemento a 
direita, contendo os elementos superiores P2. 
4. Parte IV: contendo os elementos a ser examinados com 
índices de K até G 
4. O próximo elemento na posição K pertencente a parte IV é 
comparado com os pivôs P1 e P2, e alocado na parte correspondente, I, II ou 
III. 
5. Os ponteiros L, K e G são alterados nas direções 
correspondentes. 
6. Os passos 4 e 5 são repetidos enquanto G se aproxima de K. 
7. O pivô P1 é trocado com o último elemento da parte I, o pivô P2 
é trocado com o primeiro elemento da parte III. 
8. As etapas 1 e 7 são repetidas de forma recursiva para cada 
parte I, II e III. 
Também foi demonstrado por Yaroslavskiy que para ordenação de dados 
primitivos é mais eficiente a utilização do quicksort de 3 partições, sendo o número 
médio de comparações do Dual-Pivot Quicksort é , é o numero médio de 
trocas é enquanto a versão clássica do algoritmo Quicksort possui 
 respectivamente. 
Uma experimento realizado pelo Budiman, Zamzami e Rachmawati (2017), foi 
proposto, implementado e realizado experimentos com os 
 algoritmos quicksort clássico e quicksort com dois, três, quatro e cinco pivôs. 
Analisando os resultados experimentais notou-se que o quicksort com um único pivô 
23 
 é o mais lento entre as cinco. Em segundo lugar, analisando o uso de até 5 
pivôs foi comprovado que quanto mais pivôs são utilizados em um algoritmo 
quicksort, mais rápido seu desempenho se torna. Em terceiro lugar, o aumento de 
velocidade resultante da adição de mais pivôs tende a diminuir gradualmente. 
Comparação com outro algoritmo de ordenação 
Quicksort é uma versão otimizada de uma árvore binária ordenada. 
Atualmente, o Quicksort não introduz a ordem dos itens em uma árvore explícita, 
mas os organiza em uma árvore implícita e os organiza por meio de chamadas 
recursivas. O algoritmo executa exatamente a mesma comparação, mas em uma 
ordem diferente. 
O algoritmo mais familiarizado com Quicksort é o Heapsort. Para o pior caso 
neste algoritmo, temos . No entanto, Heapsort causou muita controvérsia 
no identificador médio, mas é mais lento do que o algoritmo quicksort. Na 
classificação rápida, o pior caso ainda existe, a menos que envolva o uso da 
variante de classificação Intro, quando o pior caso for detectado, a variante se 
tornará Heapsort. Se você sabe que é necessário usar a classificação de heap no 
início, é recomendado usá-lo diretamente em vez de usar introsort e, em seguida, 
chamar a classificação de heap, o que tornará o algoritmo mais rápido. 
O quicksort também compete com o Mergesort, outro algoritmo de ordenação 
recursiva, tendo este o benefício de ter como pior caso Mergesort, ao 
contrário do quicksort e do Heapsort, é estável e pode facilmente ser adaptado para 
operar em listas encadeadas e em listas bastante grandes alojadas num tipo de 
acesso lento a média como um Network-Attached Storage ou num disco. Embora o 
quicksort possa ser operado em listas encadeadas, por vezes escolhendo um mau 
pivô sem acesso aleatório. A maior desvantagem do Mergesort é que quando opera 
em arrays, requer de espaço para o melhor caso, considerando que o quicksort 
com um particionamento espacial e com recursão utiliza apenas ) de espaço. 
 
24 
https://pt.wikipedia.org/wiki/Mergesort
Os tipos de algoritmo de ordenação existente 
Métodos simples 
 Insertion sort 
 Selection sort 
 Bubble sort 
 Comb sort 
 Bogo sort 
Métodos sofisticados 
 Merge sort 
 Heapsort 
 Shell sort 
 Radix sort 
 Gnome sort 
 Counting sort 
 Bucket sort 
 Cocktail sort 
 Timsort 
 Quick sort 
Métodos de pesquisa 
 Pesquisa binaria 
 Buscar linear 
 
6. CONTRIBUIÇÃO DO TRABALHO NA NOSSA FORMAÇÃO 
 Este trabalho permitiu colocar em prática o conteúdo aprendido durante o 
curso de Ciência da Computação. Desde a fase ainda teórica, onde são buscados 
os requisitos do programa, o que ele deve ou não deve fazer, os erros que devem 
ser tratados e qual será a lógica utilizada no programa. 
25 
https://pt.wikipedia.org/wiki/Insertion_sort
https://pt.wikipedia.org/wiki/Selection_sort
https://pt.wikipedia.org/wiki/Bubble_sort
https://pt.wikipedia.org/wiki/Comb_sort
https://pt.wikipedia.org/wiki/BogoBusca
https://pt.wikipedia.org/wiki/Merge_sort
https://pt.wikipedia.org/wiki/Heapsort
https://pt.wikipedia.org/wiki/Shell_sort
https://pt.wikipedia.org/wiki/Radix_sorthttps://pt.wikipedia.org/wiki/Gnome_sort
https://pt.wikipedia.org/wiki/Count_sort
https://pt.wikipedia.org/wiki/Bucket_sort
https://pt.wikipedia.org/wiki/Cocktail_sort
https://pt.wikipedia.org/wiki/Timsort
https://pt.wikipedia.org/wiki/Quick_sort
7. RELATÓRIO COM AS LINHAS DE CÓDIGO DO PROGRAMA 
 
#include<windows.h> 
#include<stdio.h> 
#include<conio.h> 
#include<iostream> 
#include <stdlib.h> 
#include <time.h> 
 
 
//Código feito com base em tutoriais na internet. 
 
void mgotoxy(int x, int y) 
{ 
 
SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE),(COORD){x,
y}); 
} 
 
main() 
{ 
 int x,d=2,cx[300]={1,2},cy[300]={7,7},t=1,mx,my,velo=100,velo2=5; 
 char niv; 
 
26 
 char tecla='a'; 
 int opcao; 
 int pontos=0; 
 int nivel = 1; 
 
 
 
 for(x=0;x<18;x++) 
 { mgotoxy(0,x); //vertical esquerda.// 
 
 printf("%c",219); 
 } 
 for(x=0;x<50;x++) 
 { mgotoxy(x,0); //horizontal ssuperior// 
 printf("%c",219); 
 } 
 for(x=0;x<18;x++) 
 { mgotoxy(50,x); //vertical direita// 
 printf("%c",219); 
 } 
 for(x=0;x<51;x++) 
 { mgotoxy(x,18); //horizontal inferior.// 
 printf("%c",219); 
27 
 } 
 
 
 
 srand(time(NULL)); 
 mx=(rand()%49)+1; 
 my=(rand()%17)+1; 
 
 velo = 200; 
 
 while(tecla!='s') 
 { while(tecla!='s'&&!(tecla=kbhit())) 
 
 { for(x=t;x>0;x--) 
 { cx[x]=cx[x-1]; 
 cy[x]=cy[x-1]; 
 } 
 
 if(d==0)cx[0]--; 
 if(d==1)cy[0]--; 
 if(d==2)cx[0]++; 
 if(d==3)cy[0]++; 
 mgotoxy(cx[t],cy[t]); 
28 
 printf(" "); 
 if(mx==cx[0]&&my==cy[0]) 
 { t++; 
 pontos++; 
 mx=(rand()%25)+1; 
 my=(rand()%17)+1; 
 velo-=5; 
 velo2+=5; 
 
 } 
 mgotoxy(cx[0],cy[0]); 
 
 printf("%c",219); 
 
 mgotoxy(mx,my); 
 printf("%c",1); 
 mgotoxy(55,10); 
 
 printf ("Pontos: %d",pontos); 
 mgotoxy(55,5); 
 printf ("Nivel: %d",nivel); 
 mgotoxy(55,3); 
 printf ("Velocidade: %d",velo2); 
29 
 mgotoxy(3,22); 
 
 printf ("Progrma criado pelo grupo da ciencia da computacao"); 
 
 Sleep(velo); 
 for(x=1;x<t;x++) 
 { if(cx[0]==cx[x]&&cy[0]==cy[x])tecla='s'; 
 } 
 if(cy[0]==0||cy[0]==18||cx[0]==0||cx[0]==50)tecla='s'; 
 
 
 
 
 } 
 if(tecla!='s')tecla=getch(); 
 if(tecla=='K')d=0; 
 if(tecla=='H')d=1; 
 if(tecla=='M')d=2; 
 if(tecla=='P')d=3; 
 if(cy[0]==0||cy[0]==18||cx[0]==0||cx[0]==26)tecla='s'; 
 
 } 
 system("cls"); 
30 
 system("pause"); 
 
 printf ("\n\n\tVOCE PERDEU\n\n"); 
 
 printf ("\n\n\tVOCE FEZ %d PONTOS",pontos); 
 
 
 
 
 
 
 
 getch(); 
} 
O programa utilizado para a criação do jogo foi o DEC C++. 
 
8 APRESENTAÇÃO DO PROGRAMA EM FUNCIONAMENTO EM UM 
COMPUTADOR 
 
 
 
 
 
 
31 
 
 
 
 
 
9 Referencias 
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford 
Stein. Introduction to Algorithms, 2ed. MIT Press e McGraw-Hill, 2001. ISBN 0-
262-03293-7. Problem 2-2, pg.40. 
https://pt.wikipedia.org/w/index.php?title=Thomas_H._Cormen&action=edit&redlink=1
https://pt.wikipedia.org/w/index.php?title=Charles_E._Leiserson&action=edit&redlink=1
https://pt.wikipedia.org/w/index.php?title=Ronald_L._Rivest&action=edit&redlink=1
https://pt.wikipedia.org/w/index.php?title=Clifford_Stein&action=edit&redlink=1
https://pt.wikipedia.org/w/index.php?title=Clifford_Stein&action=edit&redlink=1
https://pt.wikipedia.org/w/index.php?title=Introduction_to_Algorithms&action=edit&redlink=1
https://pt.wikipedia.org/wiki/McGraw-Hill
https://pt.wikipedia.org/wiki/Especial:Fontes_de_livros/0262032937
https://pt.wikipedia.org/wiki/Especial:Fontes_de_livros/0262032937
32 
Sorting in the Presence of Branch Prediction and Caches 
Fundamentals of Data Structures by Ellis Horowitz, Sartaj Sahni and 
Susan Anderson-Freed ISBN 81-7371-605-6 
 
Computer Algorithms. Introduction to Design and Analysis (em inglês) 2ª ed. 
Reading, Massachusetts: Addison-Wesley. 71 páginas 
https://medium.com/@henriquebraga_18075/algoritmos-de-
ordena%C3%A7%C3%A3o-iii-insertion-sort-bfade66c6bf1 
https://pt.wikipedia.org/wiki/Insertion_sort 
https://www.blogcyberini.com/2018/07/merge-sort.html 
https://pt.wikipedia.org/wiki/Quicksort 
AZEREDO, Paulo A. (1996). Métodos de Classificação de Dados e Análise de 
suas Complexidades. Rio de Janeiro: Campus. ISBN 85-352-0004-5 
 «An Interview with C.A.R. Hoare». Communications of the ACM, March 2009 
("premium content") 
BAASE, Sara (1988). Computer Algorithms. Introduction to Design and 
Analysis (em inglês) 2ª ed. Reading, Massachusetts: Addison-Wesley. 
53 páginas. ISBN 0-201-06035-3 
Jon Bentley (1999). Programming Pearls. Addison-Wesley Professional. 
«Recursão - Aprender Haskell será um grande bem para 
você!». haskell.tailorfontela.com.br. Consultado em 12 de agosto de 2020 
YAROSLAVSKIY, V. Dual-pivot quicksort. Research Disclosure, 
2009. BUDIMAN, M.; ZAMZAMI, E.; RACHMAWATI, D. Multi-pivot quicksort: an 
experiment with single, dual, triple, quad, and penta-pivot quicksort algorithms in 
https://www.cs.tcd.ie/publications/tech-reports/reports.05/TCD-CS-2005-57.pdf
https://pt.wikipedia.org/w/index.php?title=Sartaj_Sahni&action=edit&redlink=1
https://pt.wikipedia.org/wiki/Especial:Fontes_de_livros/8173716056
https://medium.com/@henriquebraga_18075/algoritmos-de-ordena%C3%A7%C3%A3o-iii-insertion-sort-bfade66c6bf1
https://medium.com/@henriquebraga_18075/algoritmos-de-ordena%C3%A7%C3%A3o-iii-insertion-sort-bfade66c6bf1
https://pt.wikipedia.org/wiki/Insertion_sort
https://www.blogcyberini.com/2018/07/merge-sort.html
https://pt.wikipedia.org/wiki/Quicksort
https://pt.wikipedia.org/wiki/Especial:Fontes_de_livros/8535200045
http://cacm.acm.org/magazines/2009/3/21782-an-interview-with-car-hoare/fulltext
https://pt.wikipedia.org/wiki/Especial:Fontes_de_livros/0201060353
http://haskell.tailorfontela.com.br/recursion#hello-recursion
http://haskell.tailorfontela.com.br/recursion#hello-recursion
33 
 python. In: IOP PUBLISHING.IOP Conference Series: Materials Science and 
Engineering. [S.l.], 2017. v. 180, n. 1, p.012051