Skip to content

Instantly share code, notes, and snippets.

@jjfajardo
Created February 2, 2012 19:41
Show Gist options
  • Save jjfajardo/1725330 to your computer and use it in GitHub Desktop.
Save jjfajardo/1725330 to your computer and use it in GitHub Desktop.
Implementación del algoritmo de ordenación Mergesort en C.
/*Códigos correspondientes al trabajo realizado para el ISUM 2012.
* Test de rendimiento de los algoritmos de ordenamiento Quicksort,
* Mezcla y burbuja implementados en C++, Fortran y Python.
* Guanajuato, Guanajuato, México (14-16 de Marzo 2012)
*
* Programa: mergesort.c
* compilar: gcc -Wall -O mergesort.c -o mergesort
* Uso: $./mergesort 1000.dat
* El tamaño del array se toma del nombre del archivo (1000.dat)
* Salida:
* $ Tamaño_array Tiempo_de_ejecución_del_algoritmo
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
inline
void merge(int *left, int l_len, int *right, int r_len, int *out)
{
int i, j, k;
for (i = j = k = 0; i < l_len && j < r_len; )
out[k++] = left[i] < right[j] ? left[i++] : right[j++];
while (i < l_len) out[k++] = left[i++];
while (j < r_len) out[k++] = right[j++];
}
void recur(int *buf, int *tmp, int len)
{
int l = len / 2;
if (len <= 1) return;
recur(tmp, buf, l);
recur(tmp + l, buf + l, len - l);
merge(tmp, l, tmp + l, len - l, buf);
}
void merge_sort(int *buf, int len)
{
int *tmp = malloc(sizeof(int) * len);
memcpy(tmp, buf, sizeof(int) * len);
recur(buf, tmp, len);
free(tmp);
}
int main(int argc, char *argv[])
{
int n;
clock_t ini, final;
double total;
if(argc == 1)
{
return 0;
}
char numero[12];
char* p, *q;
for(p = argv[1], q = numero; *p != '\0'; ++p)
{
if(*p == '.')
{
break;
}
else
{
*q = *p;
++q;
}
}
*q = '\0';
n = atol(numero);
int *x = malloc(sizeof(int)* n);
FILE *inFile;
inFile = fopen(argv[1], "r" );
if (!inFile)
{
return 0;
}
int k;
for (k = 0; k < n; k++)
{
fscanf(inFile, "%i", &x[k]);
}
fclose(inFile);
ini = clock();
merge_sort(x, n);
final=clock();
total=((double)(final - ini)) / CLOCKS_PER_SEC;
printf ("%d \t",n);
printf ("%lf \n", total);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment