Code:
#include <stdlib.h>
#include <math.h>
#include <stdio.h>
#include <unistd.h>
#include <string.h>
#define MAXSIZE 5000
#define ARRAY_LEN 5000
#define LESS(a, b) a < b
#define MIN(a, b) (a < b) ? a : b
struct element
{
int value;
char *str;
} elements[5000];
int *array;
int *tempArray;
int cmpint(struct element *a1, struct element *a2);
int cmpstr(struct element *a1, struct element *a2);
int comps=0;
int count;
void usage(char *argv);
void mysort1(void *base, int nel, int width, int (*compar)(void *, void*));
void BUmergesort(void *array, int l, int r, int width, int (*compar)(void *, void*) );
void merge(void *pa, int l, int m, int r, int width, int (*compar)(void *, void*) );
int main(int argc, char *argv[])
{
array = (int*)calloc(sizeof(int ),count);
tempArray = (int *)calloc(sizeof(int), count);
memcpy(tempArray, array, count*sizeof(int));
extern char *optarg;
extern int optind, opterr, optopt;
FILE *ifp = stdin;
FILE *ofp = stdout;
char *infile = NULL;
char *outfile = NULL;
int field = 1;
int natural = 1;
int c;
char buf[200];
char *type;
int nl=0;
while ((c = getopt(argc, argv, "i:o:f:s:")) != -1) {
switch (c) {
case 'i':
if (infile) {
usage(argv[0]); /* argv[0] == program name */
exit(1);
}
infile = optarg;
if (!(ifp = fopen(infile, "r")))
fprintf(stderr,"Error,can not open file \n" );
else {
while (fgets(buf, sizeof(buf), stdin) && count < 5000) {
sscanf(buf, "%d%s", &elements[count].value, elements[count].str);
++count;
}
if (count >= 5000) {
fprintf(stderr,"too many items \n" );}
break;
}
case 'o':
if (outfile) {
fprintf(stderr,"Error,can not open file \n");
exit (1);
}
outfile = optarg;
if (!(ofp = fopen(outfile, "w"))) {
fprintf(stderr,"Error,can not open file '\n");
}
break;
case 'f':
field = atoi(optarg);
if (field ==-1 || field !=2)
field=1;
else
field=2;
break;
case 's':
type = optarg;
if (!strcmp(type,"b")) natural=2;
else if (!strcmp(type,"n")) natural=1;
else natural=1;
break;
case ':': /* option without arguments */
fprintf(stderr, "Option -%c requires an argument\n",optopt);
/* call error routine and exit */
break;
case '?':
fprintf(stderr, "Unrecognized option: - %c\n",optopt);
/* call error routine and exit */
}
if( field == 1 )
{
mysort1( elements, count, sizeof( struct element ), cmpint );
}
else
{
mysort1( elements, count, sizeof( struct element ), cmpstr );
}
}
fclose(ifp);
fclose(ofp);
printf("%d comparsions\n",comps);
return 0;
}
void mysort1(struct element *base, int nel, int width, int (*compar)(void *, void*))
{
BUmergesort(base,0,nel-1,width,compar);
}
void BUmergesort(void *array, int l, int r, int width, int (*compar)(void *, void*) )
{
int i, m;
for (m=1; m <= r-l; m = m+m)
for (i=l; i<=r-m; i +=m+m)
merge(array, i, i+m-1, MIN(i+m+m-1, r), width, compar );
}
void merge(void *pa, int l, int m, int r, int width, int (*compar)(void *, void*) )
{
int i, j, k;
char *aux = malloc( width * ARRAY_LEN ); // ARRAY_LEN should be m-l+1 ???
char *a = pa; // use a char pointer, so we can do address arithmetic
for (i= m+1; i>l; i--)
memcpy( &aux[(i-1)*width], &a[(i-1)*width], width ); // aux[i-1] = a[i-1];
for (j = m; j < r; j++)
memcpy( &aux[(r+m-j)*width], &a[(j+1)*width], width ); // aux[r+m-j] = a[j+1];
for (k=l; k <= r; k++)
if ( compar( &aux[j*width], &aux[i*width]) < 0 )
memcpy( &a[k*width], &aux[j--*width], width ); // a[k] = aux[j--];
else
memcpy( &a[k*width], &aux[i++*width], width ); // a[k] = aux[i++];
free( aux );
}
void usage(char *argv0)
{
fprintf(stderr, "usage: %s [-i infile] [-o outfile] [-s {n|b}] [-f {1|2}]\n", argv0);
exit(1);
}
int cmpint(struct element *a1, struct element *a2)
{
comps++;
return a1-> value - a2-> value;
}
int cmpstr(struct element *a1, struct element *a2)
{
comps++;
return strcmp(a1-> str, a2-> str);
}