Trabalho 2 APA - Rodrigo Castro Azevedo

insertion_sort.c

#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;
}

merge_sort.c

#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;
}

profile_insertion_sort.c

#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;
}

profile_merge_sort.c

#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;
}

sort.h

#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);
}