Roteiro do Encontro
Ordenação Rápida - Quick Sort
A ordenação rápida (Quick Sort) se basei em um conceito simples de divisão e conquista. Possui inúmeras aplicações em diferentes estruturas que necessitam de ordenação, em nosso caso de estudo usaremos um arquivo binário gerado com um gerador de sequências. Ele irá gerar por padrão 1000 palavras de 8 caracteres para que seja ordenadas pelo algoritmo Quick Sort. O objetivo será paralelizar a ordenação, fazendo com que possamos reduzir esse tempo de ordenação consideravelmente.
O algoritmo inicial utilizado para esse problema é o seguinte:
int main(void) {
char *keys;
long int N, i;
FILE *file;
if ((file = fopen("quicksort.in", "r")) == NULL) {
perror("quicksort.in");
exit(1);
}
fscanf(file, "%ld", &N);
keys = (char*) malloc(N * 8);
if (keys == NULL) {
perror("Memory allocation");
exit(EXIT_FAILURE);
}
for (i = 0; i < N; i++)
fscanf(file, "%s", keys + (i * 8));
fclose(file);
qsort(keys, N, 8, (int(*)(const void *, const void *)) strcmp);
if ((file = fopen("quicksort.out", "w")) == NULL) {
perror("quicksort.out");
exit(1);
}
for (i = 0; i < N; i++)
fprintf(file, "%s\n", keys + (i * 8));
fclose(file);
free(keys);
return EXIT_SUCCESS;
}
Paralelização
Durante a reunião foram discutidas diferentes abordagem para a solução desse problema. Inicialmente foi sugerido a modificação de função de leitura e foram anotados resultados efetivos nessa modificação, porém ainda não atingindo o objetivo principal. A paralelização foi decidida e será implementada em uma reunião futura.
