Skip to content

Instantly share code, notes, and snippets.

@roooodcastro
Created June 2, 2016 23:47
Show Gist options
  • Save roooodcastro/862f3c76f75b7c6c55e3e9804abe5b7e to your computer and use it in GitHub Desktop.
Save roooodcastro/862f3c76f75b7c6c55e3e9804abe5b7e to your computer and use it in GitHub Desktop.
Trabalho 2 APA - Rodrigo Castro Azevedo
#include "sort.h"
void insertionSort(int *vector, int vectorSize) {
int currentNumber, prevNumber, index, subIndex;
// Para cada índice, posicioná-lo corretamente
for (index = 1; index < vectorSize; index++) {
subIndex = index;
currentNumber = vector[subIndex];
prevNumber = vector[subIndex - 1];
// Enquanto o elemento estiver fore de ordem, posicioná-lo, um por um
while (currentNumber < prevNumber) {
vector[subIndex - 1] = currentNumber;
vector[subIndex--] = prevNumber;
currentNumber = vector[subIndex];
prevNumber = vector[subIndex - 1];
}
}
}
int main(void) {
// Lê o tamanho do vetor
int vectorSize;
scanf("%d", &vectorSize);
// printf("Reading %d numbers for sorting...\n", vectorSize);
// Lê o vetor
int vector[vectorSize];
readInput(vector);
// printf("Sorting %d numbers using Insertion Sort...\n", vectorSize);
// Faz o sort e calcula o tempo
double startTime = clock();
insertionSort(vector, vectorSize);
double endTime = clock();
// Imprime o resultado
// printSortResult(vector, vectorSize);
// Imprime o tempo de execução em ms em STDOUT
printTime(startTime, endTime);
return 0;
}
#include "sort.h"
void merge(int *vectorA, int *vectorB, int *outVector, int sizeA, int sizeB) {
// Algoritmo visto em aula
int indexA = 0, indexB = 0;
while (indexA < sizeA && indexB < sizeB) {
if (vectorA[indexA] <= vectorB[indexB]) {
outVector[indexA + indexB] = vectorA[indexA++];
} else {
outVector[indexA + indexB] = vectorB[indexB++];
}
}
while (indexA < sizeA) outVector[indexA + indexB] = vectorA[indexA++];
while (indexB < sizeB) outVector[indexA + indexB] = vectorB[indexB++];
}
void mergeSort(int *vector, int vectorSize) {
if (vectorSize == 1) return;
// Definindo o tamanho dos 2 vetores "filhos". O segundo terá 1 elemento a
// mais caso o vetor "pai" tenha tamanho ímpar
int sizeA = vectorSize / 2;
int sizeB = vectorSize / 2 + vectorSize % 2;
// Alocando e copiando o vetor em 2 vetores com metade do tamanho (divide)
int *vectorA = malloc(sizeA * sizeof(int));
int *vectorB = malloc(sizeB * sizeof(int));
memcpy(vectorA, vector, sizeA * sizeof(int));
memcpy(vectorB, vector + sizeA, sizeB * sizeof(int));
// Algoritmo visto em aula
mergeSort(vectorA, sizeA);
mergeSort(vectorB, sizeB);
// Fazendo merge dos 2 vetores ordenados (conquer)
merge(vectorA, vectorB, vector, sizeA, sizeB);
}
int main(void) {
// Lê o tamanho do vetor
int vectorSize;
scanf("%d", &vectorSize);
// printf("Reading %d numbers for sorting...\n", vectorSize);
// Lê o vetor
int vector[vectorSize];
readInput(vector);
printf("Sorting %d numbers using Merge Sort...\n", vectorSize);
// Faz o sort e calcula o tempo
double startTime = clock();
mergeSort(vector, vectorSize);
double endTime = clock();
// Imprime o resultado
// printSortResult(vector, vectorSize);
// Imprime o tempo de execução em ms em STDOUT
printTime(startTime, endTime);
return 0;
}
#include "sort.h"
int main(void) {
int i = 1;
// Executa todos os testes com o InsertionSort, 25 vezes cada teste
for (i; i <= 12; i++) {
char testCommand[30];
sprintf(testCommand, "./insertion_sort < Teste%d.txt", i);
profileTest(testCommand, 25);
}
return 0;
}
#include "sort.h"
int main(void) {
int i = 1;
// Executa todos os testes com o MergeSort, 25 vezes cada teste
for (i; i <= 12; i++) {
char testCommand[26];
sprintf(testCommand, "./merge_sort < Teste%d.txt", i);
profileTest(testCommand, 25);
}
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#include <float.h>
#include <time.h>
#define BUFSIZE 16
// Função helper para ler o vetor de STDIN
void readInput(int *vector) {
int index = 0, currentNumber;
while (scanf("%d", &currentNumber) != EOF) {
vector[index++] = currentNumber;
}
}
// Função helper para imprimir o vetor ordenado em STDOUT
void printSortResult(int *vector, int vectorSize) {
int index = 0;
for (index; index < vectorSize; index++) {
printf("%d\n", vector[index]);
}
}
// Função helper para imprimir o tempo de execu;cão em STDOUT
void printTime(double startTime, double endTime) {
double totalTime = (double)(endTime - startTime) / CLOCKS_PER_SEC;
// printf("Total time spent: %f ms\n", totalTime * 1000);
printf("%f", totalTime * 1000);
}
// Função helper para executar um comando shell e ler o output do programa.
// Fonte: http://stackoverflow.com/a/28971647/753012
double parseOutput(char *command) {
char buf[BUFSIZE];
FILE *fp;
fp = popen(command, "r");
// Lê uma única linha do "arquivo" (que na verdade é o output do comando), e
// retorna ela como double (converte char* para double, já sabemos que é o
// tempo de execução)
fgets(buf, BUFSIZE, fp);
pclose(fp);
return strtod(buf, NULL);
}
// Função helper para executar um comando n vezes e calcular o tempo mínimo,
// máximo e médio de execução. Para isso funcionar, o programa (de ordenação)
// deve imprimir apenas o tempo de execução em STDOUT. Por isso todos os prints
// nos programas estão comentados.
void profileTest(char *testCommand, int numExecutions) {
printf("Profiling test \"%s\":\n", testCommand);
int i = 0;
double executions[numExecutions];
double fastest = DBL_MAX, slowest = 0, average = 0;
// Executa n vezes o comando e calcula as execuções mais lentas e rápidas
for (i; i < numExecutions; i++) {
executions[i] = parseOutput(testCommand);
if (executions[i] < fastest) fastest = executions[i];
if (executions[i] > slowest) slowest = executions[i];
}
// Calcula a média de tempo de execução
for (i = 0; i < numExecutions; i++) {
average += executions[i];
}
average /= numExecutions;
printf("Average time is %f ms\n", average);
printf("Fastest time is %f ms\n", fastest);
printf("Slowest time is %f ms\n\n", slowest);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment