lab 7

Prévia do material em texto

INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DE SÃO PAULO 
DEPARTAMENTO INFORMÁTICA 
CURSO BACHARELADO EM CIÊNCIA DA COMPUTAÇÃO 
 
DISCIPLINA: Laboratório de Estrutura de Dados 
 
 
 
 
 
 
 
 
 
 
 
LAB 7 – DIVISÃO E CONQUISTA 
 
 
 
 
 
 
 
 
 
Aluno: Victor Augusto Sampaio Precoma 
Prof. Fabio Modesto 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
SALTO, 2023. 
 
1. INTRODUÇÂO 
 
O Merge Sort e o Insertion Sort são dois algoritmos de classificação 
amplamente utilizados para ordenar listas de elementos. Ambos os algoritmos 
empregam abordagens diferentes para atingir o objetivo de ordenação, cada 
um com suas próprias vantagens e desvantagens. 
 
O Merge Sort é um algoritmo de classificação eficiente, baseado na abordagem 
"dividir para conquistar". Ele divide repetidamente a lista não ordenada em 
sublistas menores, até que cada sublista contenha apenas um elemento. Em 
seguida, combina essas sublistas, mesclando-as em uma única lista ordenada. 
A operação de combinação, conhecida como intercalação, é o cerne do Merge 
Sort. O algoritmo realiza a intercalação recursivamente até que toda a lista 
esteja ordenada. O Merge Sort possui uma complexidade de tempo de O(n log 
n), tornando-o uma escolha eficiente para a ordenação de grandes conjuntos 
de dados. Ele é particularmente adequado para aplicações em que a 
estabilidade da ordenação é importante. 
 
Por outro lado, o Insertion Sort é um algoritmo de classificação mais simples, 
mas ainda efetivo, especialmente para listas pequenas. O Insertion Sort 
percorre a lista do início ao fim, comparando cada elemento com os elementos 
anteriores e inserindo-o na posição correta entre os elementos já ordenados. À 
medida que percorre a lista, o algoritmo constrói uma porção ordenada no 
início da lista. O Insertion Sort possui uma complexidade de tempo de O(n^2), o 
que significa que seu desempenho piora significativamente à medida que o 
número de elementos aumenta. No entanto, para listas de tamanho pequeno 
ou quase ordenadas, o Insertion Sort pode ser mais eficiente em comparação 
com outros algoritmos mais complexos. 
 
Em resumo, o Merge Sort é altamente eficiente e ideal para a ordenação de 
grandes conjuntos de dados, enquanto o Insertion Sort é uma opção mais 
simples e adequada para listas pequenas ou quase ordenadas. A escolha entre 
esses algoritmos dependerá do tamanho da lista, da eficiência desejada e de 
outras considerações específicas do contexto de aplicação. 
 
2 CONTEÚDO 
 
Mergesort 
 
#include <chrono> 
#include <bits/stdc++.h> 
#include <string> 
#include <iostream> 
#include <fstream> 
using namespace std::chrono; 
using namespace std; 
 
const int SIZE= 50; 
int grades[SIZE]; 
void readData() 
{ 
 int i=0; 
 std::fstream myfile("NumerosAleatorios.txt", std::ios_base::in); 
 if(myfile) 
 { 
 while(!myfile.eof()) 
 { 
 myfile >> grades[i]; 
 i++; 
 } 
 myfile.close(); 
 } 
 else 
 cout << "Couldn't open the file\n";} 
} 
 
void merge(int array[], int const left, int const mid, 
 int const right) 
 
{ 
 
 auto const subArrayOne = mid - left + 1; 
 auto const subArrayTwo = right - mid; 
 
 auto *leftArray = new int[subArrayOne], 
 
 *rightArray = new int[subArrayTwo]; 
 
 for (auto i = 0; i < subArrayOne; i++) 
 leftArray[i] = array[left + i]; 
 
 for (auto j = 0; j < subArrayTwo; j++) 
 rightArray[j] = array[mid + 1 + j]; 
 
 auto indexOfSubArrayOne 
 
 = 0, 
 
 indexOfSubArrayTwo 
 
 
 = 0; 
 
 int indexOfMergedArray 
 = left; 
 
 while (indexOfSubArrayOne < subArrayOne 
 && indexOfSubArrayTwo < subArrayTwo) { 
 if (leftArray[indexOfSubArrayOne] 
 <= rightArray[indexOfSubArrayTwo]) { 
 array[indexOfMergedArray] 
 = leftArray[indexOfSubArrayOne]; 
 indexOfSubArrayOne++; 
 } 
 else { 
 array[indexOfMergedArray] 
 = rightArray[indexOfSubArrayTwo]; 
 indexOfSubArrayTwo++; 
 } 
 indexOfMergedArray++; 
 } 
 
 while (indexOfSubArrayOne < subArrayOne) { 
 array[indexOfMergedArray] 
 = leftArray[indexOfSubArrayOne]; 
 indexOfSubArrayOne++; 
 indexOfMergedArray++; 
 } 
 
 while (indexOfSubArrayTwo < subArrayTwo) { 
 array[indexOfMergedArray] 
 = rightArray[indexOfSubArrayTwo]; 
 indexOfSubArrayTwo++; 
 indexOfMergedArray++; 
 } 
 delete[] leftArray; 
 delete[] rightArray; 
} 
 
void mergeSort(int array[], int const begin, int const end) 
{ 
 if (begin >= end) 
 return; 
 auto mid = begin + (end - begin) / 2; 
 mergeSort(array, begin, mid); 
 mergeSort(array, mid + 1, end); 
 merge(array, begin, mid, end); 
} 
 
 
 
void printArray(int A[], int size) 
 
{ 
 for (auto i = 0; i < size; i++) 
 cout << A[i] << " "; 
} 
 
int main() 
 
{ 
 readData(); 
 auto arr_size = sizeof(grades) / sizeof(grades[0]); 
 auto start = high_resolution_clock::now(); 
 mergeSort(grades, 0, arr_size - 1); 
 printArray(grades, arr_size); 
 
 auto stop = high_resolution_clock::now(); 
 auto duration = duration_cast<microseconds>(stop - start); 
 cout << endl; 
 cout << "Tempo de execucao: " << duration.count() << endl; 
 
 return 0; 
 
} 
 
 
O código fornecido implementa o algoritmo de ordenação Merge Sort para 
classificar um array de números inteiros armazenados no arquivo 
"NumerosAleatorios.txt". Vou explicar o código linha por linha: 
 
As bibliotecas necessárias são incluídas no início do código. 
 
É declarada uma constante SIZE com valor 50, que representa o tamanho 
máximo do array grades. 
 
Em seguida, é declarado um array grades do tamanho SIZE para armazenar os 
números a serem ordenados. 
 
A função readData() é definida para ler os números do arquivo 
"NumerosAleatorios.txt" e armazená-los no array grades. 
 
A função merge() é definida para mesclar duas sublistas do array durante o 
processo de ordenação Merge Sort. Recebe o array, os índices esquerdo (left), 
médio (mid) e direito (right) para determinar as sublistas a serem mescladas. 
 
Dentro da função merge(), as sublistas são inicializadas usando ponteiros para 
armazenar temporariamente os elementos das sublistas esquerda e direita. 
 
Os elementos das sublistas esquerda e direita são copiados para os arrays 
temporários. 
 
É feita a mescla das duas sublistas em um único array ordenado, comparando 
os elementos e colocando-os em ordem crescente. 
 
Depois que uma das sublistas é completamente inserida no array final, os 
elementos restantes da outra sublista são copiados para o array final. 
 
Os arrays temporários são liberados da memória usando o operador delete[]. 
 
A função mergeSort() é definida para realizar a ordenação Merge Sort. Ela 
recebe o array, o índice de início (begin) e o índice final (end) do subarray a ser 
 
ordenado. 
 
A função mergeSort() usa recursão para dividir o array em subarrays menores 
e, em seguida, chama a função merge() para mesclar esses subarrays. 
 
A função printArray() é definida para imprimir o array de números. 
 
A função main() é o ponto de entrada do programa. 
 
Primeiro, a função readData() é chamada para ler os números do arquivo e 
armazená-los no array grades. 
 
A variável arr_size é definida como o tamanho do array grades. 
 
É obtido o tempo de início da execução do algoritmo usando 
high_resolution_clock. 
 
O mergeSort() é chamado para classificar o array grades. 
 
Em seguida, a função printArray() é chamada para imprimir o array classificado. 
 
É obtido o tempo de término da execução do algoritmo. 
 
A duração total da execução é calculada usando duration_cast. 
 
Por fim, a duração é impressa na tela. 
 
Esse código lê os números de um arquivo, classifica-os usando o algoritmo 
Merge Sort e imprime o resultado ordenado junto com o tempo de execução. 
 
 
INSERTION#include <chrono> 
using namespace std::chrono; 
#include <bits/stdc++.h> 
using namespace std; 
#include <string> 
#include <iostream> 
#include <fstream> 
 
const int SIZE = 50; 
int grades[SIZE]; 
 
void readData() { 
 
 
 int i=0; 
 std::fstream myfile("NumerosAleatorios.txt", std::ios_base::in); 
 if(myfile) 
 { 
 while(!myfile.eof()) 
 { 
 
 myfile >> grades[i]; 
 i++; 
 } 
 myfile.close(); 
 } 
 else 
 cout<<"Couldn't open the file\n"; 
} 
void insertionSort(int arr[], int n) 
{ 
 int i, key, j; 
 for (i = 1; i < n; i++) 
 { 
 key = arr[i]; 
 j = i - 1; 
 
 while (j >= 0 && arr[j] > key) 
 { 
 arr[j + 1] = arr[j]; 
 j = j - 1; 
 } 
 arr[j + 1] = key; 
 } 
} 
void printArray(int arr[], int n) 
{ 
 int i; 
 
 for (i = 0; i < n; i++) 
 cout << arr[i] << " "; 
 cout << endl; 
} 
int main() 
{ 
 readData(); 
 
 int N = sizeof(grades) / sizeof(grades[0]); 
 
 auto start = high_resolution_clock::now(); 
 insertionSort(grades, N); 
 printArray(grades, N); 
 auto stop = high_resolution_clock::now(); 
 auto duration = duration_cast<microseconds>(stop - start); 
 cout << duration.count() << endl; 
 
 return 0; 
} 
 
Este código implementa o algoritmo de ordenação Insertion Sort para 
classificar um array de números inteiros lidos de um arquivo chamado 
"NumerosAleatorios.txt". Aqui está uma explicação linha por linha: 
As bibliotecas necessárias são incluídas no início do código. 
É declarada uma constante SIZE com valor 50, que representa o tamanho 
máximo do array grades. 
Em seguida, é declarado um array grades do tamanho SIZE para armazenar os 
números a serem ordenados. 
A função readData() é definida para ler os números do arquivo 
"NumerosAleatorios.txt" e armazená-los no array grades. 
Dentro da função readData(), o arquivo é aberto e os números são lidos do 
arquivo e armazenados no array grades. 
A função insertionSort() é definida para realizar a ordenação Insertion Sort. Ela 
recebe o array e o tamanho do array como parâmetros. 
Dentro da função insertionSort(), um loop é usado para percorrer o array a 
partir do segundo elemento. 
 
 
Para cada elemento do array, ele é comparado com os elementos anteriores e 
inserido na posição correta no subarray já ordenado. 
A função printArray() é definida para imprimir o array de números. 
A função main() é o ponto de entrada do programa. 
Primeiro, a função readData() é chamada para ler os números do arquivo e 
armazená-los no array grades. 
A variável N é definida como o tamanho do array grades. 
É obtido o tempo de início da execução do algoritmo usando 
high_resolution_clock. 
O insertionSort() é chamado para classificar o array grades. 
Em seguida, a função printArray() é chamada para imprimir o array classificado. 
É obtido o tempo de término da execução do algoritmo. 
A duração total da execução é calculada usando duration_cast. 
Por fim, a duração é impressa na tela. 
 
Em resumo, este código lê os números de um arquivo, classifica-os usando o 
algoritmo Insertion Sort e imprime o resultado ordenado junto com o tempo de 
execução. 
 
3 METODOLOGIA EXPERIMENTAL 
 
 
3.2 Procedimento Experimental 
 
Foi utilizada a linguagem c++ e as bibliotecas chronos, bits/stdc++.h, iostream, 
string, fstream. Foi utilizado algumas funções para leitura de arquivo e contagem do 
tempo de execução. 
 
4 RESULTADOS E DISCUSSÂO 
 
4.1 Entrada de Dados 
 
 
 
 
4.2 Saída de Dados 
 
MERGE-SORT 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
INSERTION-SORT. 
 
 
 
4.3 Memória 
 
É usado apenas a memória Stack pois não é utilizado nenhuma função de 
alocação dinâmica, porém é utilizado a Stack dinâmica, pois trabalhamos com 
várias funções fora da main, então assim que a função acaba a pilha 
relacionada a ela será liberada.