ALGORITMOS DE ORDENAÇÃO BUBBLESORT, QUICKSORT, INSERTIONSORT, SELECTIONSORT

Prévia do material em texto

CENTRO UNIVERSITÁRIO ESTÁCIO - UNISEB 
COMPLEXIDADE E TÉCNICAS AVANÇADAS DE ALGORITMOS 
BACHARELADO EM ENGENHARIA DA COMPUTAÇÃO 
 
 
 
 
 
 
 
 
ALGORITMOS DE ORDENAÇÃO BUBBLESORT, QUICKSORT, INSERTIONSORT, 
SELECTIONSORT 
 
 
Gabriel Alberto Mini 
Yuri Alves Ferreira 
 
Prof. Ms. Reginaldo Gotardo 
 
 
 
 
 
 
RIBEIRÃO PRETO 
2016 
 
Sumário 
Introdução ............................................................................................................................................................... 3 
1) Códigos dos algoritmos utilizados ...................................................................................................................... 3 
Geração de números randômicos (python) ......................................................................................................... 3 
Parser do arquivo Json com lista de números. (C++) .......................................................................................... 4 
Classe Principal manipulação de algoritmos (C++) ............................................................................................ 5 
Algoritmos de Ordenação em C++ ..................................................................................................................... 6 
Bubble Sort ..................................................................................................................................................... 6 
Quick Sort ....................................................................................................................................................... 7 
Insertion Sort ................................................................................................................................................... 7 
Selection Sort .................................................................................................................................................. 8 
Algoritmo Auxiliar de manipulação e contagem de tempos ............................................................................... 8 
2) Simulação da execução dos algoritmos ............................................................................................................ 10 
Bubble Sort ....................................................................................................................................................... 10 
Quick Sort ......................................................................................................................................................... 10 
Insertion Sort ..................................................................................................................................................... 10 
Selection Sort .................................................................................................................................................... 10 
3) Gráficos ............................................................................................................................................................ 11 
Bubble Sort ....................................................................................................................................................... 11 
Quick Sort ......................................................................................................................................................... 11 
Insertion Sort ..................................................................................................................................................... 12 
Selection Sort .................................................................................................................................................... 12 
4) Comparações dos gráficos ................................................................................................................................ 13 
5) Comparação de comportamento e desempenho ............................................................................................... 13 
6) Detalhes do hardware ....................................................................................................................................... 13 
 
 
 
Introdução 
Para se construir o trabalho foi pesquisado os algoritmos definidos em sala para cada dupla. 
Ficou definido a utilização de duas linguagens de programação, o Python e C++ analisando o fato de 
que o python não tem boa performance nos quesitos de benchmark e operações matemáticas grandes, 
diferentemente do c++ que é uma das linguagens mais rápidas quando se trata de performance. 
Analisando esses fatos iniciais, os códigos em python foram utilizados para que seja feita a 
geração de números randômicos e a formatação dos dados em planilhas de forma estruturada, ou seja, 
auxiliar o desenvolvimento do projeto eliminando a programação custosa a partir do C++. Outro aspecto 
importante foi compilar o executável em C++ para que fosse chamado pelo python utilizando 
argumentos definidos, assim como o tipo do algoritmo a ser executado. 
1) Códigos dos algoritmos utilizados 
Geração de números randômicos (python) 
Para que se fossem gerados os números randômicos foi utilizado a função random.randint com 
o intervalo de zero a dez milhões, sendo que dentro deste intervalo foi gerado uma lista de inteiros de 
cinco milhões de números. Após essa geração foi utilizado a biblioteca módulo json para que fosse salvo 
os arquivos. 
Na geração de cada arquivo json, foi salvo um arquivo “random.json”, que contém o vetor de 
cinco milhões de números aleatórios não sequenciais. Após a geração do arquivo anterior foi criado um 
arquivo “sorted.json” onde é salvo este mesmo vetor de forma ordenada crescente, e também outro 
arquivo foi gerado com o nome “reversed.json” onde foi salvo o mesmo vetor de ordem decrescente. 
 
 
 
 
import random 
import json 
 
MIN, MAX = 0, 10000000 
 
print "\tCriando numeros randomicos" 
randomNumbers = list() 
for i in range(5000000): 
randomNumbers.append(random.randint(MIN, MAX)) 
 
print "\tCriando arquivo randomico" 
json.dump(randomNumbers, open("random.json", "w")) 
 
print "\tCriando arquivo ordenado" 
randomNumbers.sort() 
json.dump(randomNumbers, open("sorted.json", "w")) 
 
print "\tCriando arquivo reversamente ordenado" randomNumbers.reverse() 
json.dump(randomNumbers, open("reversed.json", "w")) 
 
print "\tAquivos Gerados com sucesso !!" 
 
Parser do arquivo Json com lista de números. (C++) 
 Para que não fosse necessário a utilização de alguma biblioteca json em C++, foi criado um parser 
específico para que pudesse abrir o arquivo json com a lista de números para que seja feita a análise do 
algoritmo. Nesse algoritmo é passado o nome do arquivo e a quantidade de números. Foi necessário a 
utilização do buffer do arquivo ao invés do getline, pois o get line faz a leitura do arquivo inteiro e o 
transforma em uma string grande, o que consome cerca de aproximadamente 5 minutos para ler um 
arquivo de 5 bilhões de números, com o tamanho aproximado de 45 MB. No algoritmo de getline é 
manipulado a partir de índices da string, e é utilizado o método stoi, para transformar o valor entre 
vírgulas em um número. 
 Para o algoritmo de buffer, o arquivo é transformado em um ponteiro de char. Com um loop 
infinito é iterado cada char utilizando o método sbumpc, que passa para o próximo caractere do ponteiro 
quando o método é chamado novamente. Para cada ciclo desse algoritmo, o caractere é comparado e se 
ele for colchetes, é ignorado pois esses são os limites de uma lista em json, e se for um número, é 
adicionado a uma string temporária de números, e se for uma vírgula, a string temporária é transformadaem um inteiro e adicionado a um vetor de inteiros (push_back), e posteriormente a string é apagada para 
um próximo número até que se encontre o caractere de final de arquivo, EOF. 
 A vantagem desse algoritmo é de que não é necessário transformar o arquivo inteiro em uma 
string, ou seja, é possível conseguir a quantidade necessária de números sem precisar transformar todos 
e dividir o vetor, o que seria ruim pelo tempo de execução, exceto o caso que se precise de todos os 
números do arquivo. O problema de tempo de leitura se observava mesmo quando se era preciso de 
quantidades pequenas de números, pois era necessário transformar o arquivo inteiro em uma string, 
mesmo se não fosse utilizar todos os números. Outro aspecto observado foi de que a leitura de todos os 
números do arquivo ainda foram 1/5 do tempo comparando-se com o getline, se aproximando dos valores 
perto de 57 segundos a 1 min. 
 
#include <iostream> 
#include <fstream> 
#include <vector> 
#include <string> 
using namespace std; 
 
//Função para transformação de um arquivo em um vetor de inteiros 
vector<int> parseFile(string fileName, int length) { 
 ifstream myfile(fileName); 
 filebuf* fbuf = myfile.rdbuf(); 
 vector<int> numbers; 
 string tempString; 
 while(true){ 
 char actual = fbuf->sbumpc(); 
 if ((actual == EOF) || (numbers.size() == length)) 
 break; 
 
 if (actual == '[' || actual == ']') 
 continue; 
 
 if (actual == ',') { 
 numbers.push_back(stoi(tempString)); 
 tempString.erase(); 
 } 
 else { 
 tempString+=actual; 
 } 
 } 
 myfile.close(); 
 return numbers; 
} 
Classe Principal manipulação de algoritmos (C++)
 
#include "stdafx.h" 
#include <iostream> 
#include <string> 
#include <vector> 
#include <ctime> 
#include "parsing.h"" 
#include "functions.h" 
using namespace std; 
#define MAX 5000000 // Número máximo de números aleatórios 
 
int main(int argc, char* argv[]) 
{ 
 // Argumentos arquivo random/ordenado ; qdte de numeros, opcao de algoritmo 
if (argc == 4) { 
 string fileName = argv[1]; 
 int qtdNumbers = atoi(argv[2]); 
 int option = atoi(argv[3]); 
 if (qtdNumbers > MAX) 
 qtdNumbers = MAX; 
 
 std::vector<int> randomVector; 
 cout << "\n\t Abrindo Arquivo: "; 
 randomVector = parseFile(fileName, qtdNumbers); 
 if (randomVector.size() == 0) { 
 cout << "Arquivo Invalido !!" << endl; 
 return -1; 
 } 
 cout << "OK" << endl; 
 if ((option >= 0) && (option <= 4)) { 
 cout << "\t Nome do Arquivo: " << fileName << endl; 
 cout << "\t Qtde de Numeros: " << qtdNumbers << endl; 
 clock_t start = clock(); 
 switch (option) { 
 case 1: // BubbleSort 
 cout << "\t Opcao: BubbleSort" << endl; 
 BubbleSort(randomVector); 
 break; 
 case 2: 
 cout << "\t Opcao: QuickSort" << endl; 
 QuickSort(randomVector); 
 break; 
 case 3: 
 cout << "\t Opcao: InsertionSort" << endl; 
 InsertionSort(randomVector); 
 break; 
 case 4: 
 cout << "\t Opcao: SelectionSort" << endl; 
 SelectionSort(randomVector); 
 break; 
 } 
 clock_t end = clock(); 
 double timeElapsed = double(end - start) / CLOCKS_PER_SEC; 
 cout << "\t * Tempo Decorrido: " << timeElapsed << " segundos" << endl; 
 
 return int(timeElapsed*1000); 
 } 
 else { 
 cout << "Opcao Invalida: " << option; 
 return -1; 
 } 
 } 
 else { 
 cout << "Argumentos Invalidos"<<endl; 
 return -1; 
 } 
 return -1; 
} 
 
No executável desse algoritmo é passado 3 argumentos (Ex: “complexidade.exe random.json 5000 
4”), dos quais são: 
1. Caminho do arquivo de vetores (ordenados ou não); 
2. Quantidades de números para ordenar (MAX=5.000.000); 
3. Tipo do algoritmo a se executar: 
 BubbleSort (1); 
 QuickSort (2); 
 Insertion Sort (3); 
 Selection Sort (4). 
É retornado o número inteiro em milissegundos do tempo de operação quando estiver 
ordenando, ou -1 se houver algum tipo de falha. 
 
Algoritmos de Ordenação em C++ 
Bubble Sort 
 
 
//Algoritmo de BubbleSort, OPÇÃO 1 
 
void BubbleSort(vector<int> &numbers) { 
 bool swapped = true; 
 int j = 0; 
 int tmp; 
 while (swapped) { 
 swapped = false; 
 j++; 
 for (int i = 0; i < numbers.size() - j; i++) { 
 if (numbers[i] > numbers[i + 1]) { 
 tmp = numbers[i]; 
 numbers[i] = numbers[i + 1]; 
 numbers[i + 1] = tmp; 
 swapped = true; 
 } 
 } 
 } 
 return; 
} 
Quick Sort 
 
 
Insertion Sort 
 
 
//Algoritmo QuickSort - OPÇÃO 2 
 
void QuickSort(vector<int> &numbers) { 
 __quickSortRecursive(numbers, 0, numbers.size()); 
 return; 
} 
 
//Função auxiliar para QuickSort Recursivo 
void __quickSortRecursive(vector<int> &numbers, int left, int right) { 
 int i = left, j = right; 
 int tmp; 
 int pivot = numbers[(left + right) / 2]; 
 while (i <= j) { 
 while (numbers[i] < pivot) 
 i++; 
 while (numbers[j] > pivot) 
 j--; 
 if (i <= j) { 
 tmp = numbers[i]; 
 numbers[i] = numbers[j]; 
 numbers[j] = tmp; 
 i++; 
 j--; 
 } 
 }; 
 if (left < j) 
 __quickSortRecursive(numbers, left, j); 
 if (i < right) 
 __quickSortRecursive(numbers, i, right); 
 return; 
} 
 
//Algoritmo InsertionSort - OPÇÃO 3 
 
void InsertionSort(vector<int> &numbers) { 
 int j, temp; 
 for (int i = 0; i < numbers.size(); i++) { 
 j = i; 
 
 while (j > 0 && numbers[j] < numbers[j - 1]) { 
 temp = numbers[j]; 
 numbers[j] = numbers[j - 1]; 
 numbers[j - 1] = temp; 
 j--; 
 } 
 } 
 return; 
} 
Selection Sort 
 
 
Algoritmo Auxiliar de manipulação e contagem de tempos 
 
//Algoritmo SelectionSort - OPÇÃO 4 
 
void SelectionSort(vector<int> &numbers) { 
 int pos_min, temp; 
 int n = numbers.size(); 
 
 for (int i = 0; i < n - 1; i++) 
 { 
 pos_min = i; 
 for (int j = i + 1; j < n; j++) 
 if (numbers[j] < numbers[pos_min]) 
 pos_min = j; 
 
 if (pos_min != i){ 
 temp = numbers[i]; 
 numbers[i] = numbers[pos_min]; 
 numbers[pos_min] = temp; 
 } 
 } 
 return; 
} 
#coding=utf-8 
import os 
import time 
import os.path as path 
import openpyxl 
from openpyxl 
import Workbook 
from openpyxl.styles 
import Color, Font, Style, Alignment, PatternFill 
 
os.chdir(path.dirname(__file__)) 
 
def main(): 
 start = time.time() 
 if not os.path.isfile("complexidade.exe") or not os.path.isfile("random.json"): 
 print "Arquivos invalidos" 
 
 arrayQtds = [10000, 50000, 100000, 200000, 400000, 600000, 1000000, 5000000] 
 
 SORT_TYPES = { 
 1: "Bubble Sort", 
 2: "Quick Sort", 
 3: "Insertion Sort", 
 4: "Selection Sort" 
 } 
 wk = Workbook() 
 
 for sortNumber, sortType in SORT_TYPES.iteritems(): 
 lines = list() 
 for qtd in arrayQtds: 
 sortedMilli = os.system(" ".join(["complexidade.exe sorted.json", str(qtd), 
str(sortNumber)])) 
 randomMilli = os.system(" ".join(["complexidade.exe random.json", str(qtd), 
str(sortNumber)])) 
 reversedMilli = os.system(" ".join(["complexidade.exe reversed.json", str(qtd), 
str(sortNumber)])) 
 
 
 
 
 
 
 
 
 
 lines.append([qtd, sortedMilli, randomMilli, reversedMilli,]) 
 
 worksh = wk.create_sheet() 
 worksh.title = sortType 
 worksh.merge_cells("A1:D1") 
 c = worksh["A1"] 
 c.value = "Resultados do Algoritmo de " + sortType 
 c.font = Font(name='Calibri', bold=True, size 14) 
 c.alignment = Alignment(horizontal="center", vertical "center", wrap_text = False) 
 worksh.row_dimensions[1].height = 20 
 
 
 worksh.append(["Quantidades(ms)", "Ordenado(ms)", "Randomico(seg)", "Reverso(ms)"]) 
 for item in ["A2", "B2", "C2", "D2"]: 
 cell= worksh[item] 
 cell.style = Style(fill = PatternFill(patternType='solid', fgColor=Color('00777777'))) 
 cell.font = Font(bold = True, italic = True) 
 cell.alignment = Alignment(horizontal="center", wrap_text=False) 
 
 worksh.column_dimensions["A"].width = 17 
 worksh.column_dimensions["B"].width = 16 
 worksh.column_dimensions["C"].width = 16 
 worksh.column_dimensions["D"].width = 16 
 
 for line in lines: 
 worksh.append(line) 
 
 wk.remove_sheet(wk.get_sheet_by_name('Sheet')) 
 wk.save("results.xlsx") 
 end = time.time() 
 print "TOTAL TIME:", end - start 
 
if __name__ == '__main__': 
 main() 
 
2) Simulação da execução dos algoritmos 
Bubble Sort 
Entrada 
 
Vetor ordenado Vetor aleatório Vetor decrescente 
Troca
s 
Compar
ações 
Tempo 
(ms) 
Trocas Compar
ações 
Tempo 
(ms) 
Trocas Compar
ações 
Tempo 
(ms) 
10.000 0 19998 0 7.4e+07 9.9e+07 176 1.5e+08 9.9e+07 107 
50.000 0 99998 0 1.8e+09 2.5e+09 5065 3.7e+09 2.5e+09 2646 
100.000 0 199998 0 7.4e+09 9.9e+09 20072 1.5e+10 1.0e+10 10540 
200.000 0 399998 0 3.0e+10 3.9e+10 79585 6.0e+10 4.0e+10 41784 
400.000 0 799998 1 1.2e+11 1.5e+11 319368 2.4e+11 1.6e+11 166105 
600.000 0 1.2e+06 1 2.7e+11 3.6e+11 719460 5.4e+11 3.6e+11 375802 
1.000.000 0 2e+06 1 7.5e+11 9.9e+11 2036187 1.5e+12 1.0e+12 1215767 
5.000.000 0 1e+07 7 51319165 27328869 
Quick Sort 
Entrada 
 
Vetor ordenado Vetor aleatório Vetor decrescente 
Troca
s 
Compar
ações 
Tempo 
(ms) 
Trocas Compar
ações 
Tempo 
(ms) 
Trocas Compa
rações 
Tempo 
(ms) 
10.000 30897 143621 0 99426 192274 1 36336 135239 1 
50.000 154308 830583 1 581319 1.1e+06 4 182289 791899 1 
100.000 253335 1.7e+06 2 1.2e+06 2.3e+06 9 394650 1.7e+06 1 
200.000 617508 3.7e+06 4 2.6e+06 5.0e+06 20 729834 3.6e+06 4 
400.000 1.2e+06 7.8e+06 8 5.5e+06 1.0e+07 40 1.5e+06 7.5e+06 9 
600.000 1.8e+06 1.2e+07 11 8.5e+06 1.6e+07 61 2.2e+06 1.2e+07 10 
1.000.000 3.1e+06 2.1e+07 23 1.5e+07 2.9e+07 106 3.5+06 2.0e+07 18 
5.000.000 1.5e+07 1.2e+08 105 8.2e+07 1.5e+08 576 1.8e+07 1.1e+08 97 
Insertion Sort 
Entrada 
 
Vetor ordenado Vetor aleatório Vetor decrescente 
Troca
s 
Compar
ações 
Tempo 
(ms) 
Trocas Compar
ações 
Tempo 
(ms) 
Trocas Compa
rações 
Tempo 
(ms) 
10.000 0 10000 0 5.0e+07 7.5e+07 53 9.9e+07 1.5e+08 100 
50.000 0 50000 0 1.2e+09 1.9e+09 1220 2.5e+09 3.7e+09 2405 
100.000 0 100000 0 5.0e+09 7.5e+09 4838 1.0e+09 1.5e+10 9506 
200.000 0 200000 0 8.0e+10 1.2e+11 18981 4.0e+10 6.0e+10 44916 
400.000 0 400000 0 2.0e+10 3.0e+10 77773 1.6e+11 2.4e+11 159030 
600.000 0 600000 2 1.8e+11 2.7e+11 185260 3.6e+11 5.4e+11 367883 
1.000.000 0 1e+06 1 5.0e+11 7.5+11 501215 1.0e+12 1.5e+12 1048484 
5.000.000 0 5e+06 7 12527210 24885411 
Selection Sort 
Entrada 
 
Vetor ordenado Vetor aleatório Vetor decrescente 
Troca
s 
Compar
ações 
Tempo 
(ms) 
Trocas Compar
ações 
Tempo 
(ms) 
Trocas Compa
rações 
Tempo 
(ms) 
10.000 0 5.0e+07 38 29955 5.0e+07 41 17316 6.9e+07 111 
50.000 0 1.2e+09 966 149967 1.3e+09. 1018 86877 1.7e+09 2664 
100.000 0 5.0e+09 3751 299964 5.0e+09 4106 173718 7.0e+09 10661 
200.000 0 2.0e+10 15003 599961 2.0e+10 16406 346830 2.8e+10 42582 
400.000 0 1.8e+11 61512 1.2e+06 8.0e+10 71245 693120 1.1e+11 175152 
600.000 0 8.0e+10 143516 1.8+06 1.8e+11 156093 1.0e+06 2.5e+11 394453 
1.000.000 0 5.0e+11 406264 3.0e+06 5.0e+11 417788 1.7e+06 6.9e+11 1126723 
5.000.000 0 1.3e+13 10848335 10878576 27582691 
 
3) Gráficos 
 
 
 
Bubble Sort 
 
 
 
 
 
 
Quick Sort 
 
 
 
 
0
10000000
20000000
30000000
40000000
50000000
60000000
10000 50000 100000 200000 400000 600000 1000000 5000000
Te
m
p
o
 (
m
s)
Bubble sort
Ordenado(ms) Randomico(ms) Reverso(ms)
0
100
200
300
400
500
600
700
10000 50000 100000 200000 400000 600000 1000000 5000000
Te
m
p
o
 (
m
s)
Quick Sort
Ordenado(ms) Randomico(ms) Reverso(ms)
Insertion Sort 
 
 
 
 
 
Selection Sort 
 
 
 
 
 
 
 
0
5000000
10000000
15000000
20000000
25000000
30000000
10000 50000 100000 200000 400000 600000 1000000 5000000
Te
m
p
o
 (
m
s)
Insertion Sort
Ordenado(ms) Randomico(ms) Reverso(ms)
0
5000000
10000000
15000000
20000000
25000000
30000000
10000 50000 100000 200000 400000 600000 1000000 5000000
Te
m
p
o
 (
m
s)
Selection sort
Ordenado(ms) Randomico(ms) Reverso(ms)
4) Comparações dos gráficos 
 
 
 
5) Comparação de comportamento e desempenho 
6) Detalhes do hardware 
Os testes foram realizados em um Notebook com processador Core i5, 6GB de memória RAM. 
Baseado no que foi observado nos teste, mesmo usando um processador de 2 núcleos, trabalhando em 
múltiplas threads, os algoritmos usavam apenas um dos núcleos, o que nos leva a concluir que mesmo 
se usar um processador com oito núcleos, o tempo de execução dos algoritmos seria o mesmo. 
Portanto para ter uma melhor performance na execução, deve-se trabalhar na otimização do algoritmo 
de ordenação 
0
10000000
20000000
30000000
40000000
50000000
60000000
Te
m
p
o
 (
m
s)
Bubble sort
Ordenado(ms) Randomico(ms)
Reverso(ms)
0
200
400
600
800
Te
m
p
o
 (
m
s)
Quick Sort
Ordenado(ms) Randomico(ms)
Reverso(ms)
0
5000000
10000000
15000000
20000000
25000000
30000000
Te
m
p
o
 (
m
s)
Insertion Sort
Ordenado(ms) Randomico(ms) Reverso(ms)
0
5000000
10000000
15000000
20000000
25000000
30000000
Te
m
p
o
 (
m
s)
Selection sort
Ordenado(ms) Randomico(ms)
Reverso(ms)