sorting

This is a discussion on sorting within the C Programming forums, part of the General Programming Boards category; how can i if my sorting function must have the following interface what should those XX be ? and if ...

  1. #1
    Registered User
    Join Date
    Apr 2003
    Posts
    5

    sorting

    how can i if my sorting function must have the following interface
    what should those XX be ? and if that's incorrect, how to fix it,
    where the interface of mysort1 is the same as quick sort.....

    struct element {
    int value;
    char *str;
    } elements[5000];
    .....
    ...
    ..
    void mysort1(struct element *base, int nel,int width, int (*compar)(struct element *, struct element*))
    {
    BUmergesort(XX,XX,XX);
    }

    void BUmergesort(int *array, int l, int r) {

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


    void merge(int *a, int l, int m, int r) {
    int i, j, k, aux[ARRAY_LEN];

    for (i= m+1; i>l; i--)
    aux[i-1] = a[i-1];
    for (j = m; j < r; j++)
    aux[r+m-j] = a[j+1];
    for (k=l; k <= r; k++)
    if (LESS(aux[j], aux[i]))
    a[k] = aux[j--];
    else a[k] = aux[i++];
    }

  2. #2
    Registered User
    Join Date
    Apr 2003
    Posts
    5
    thanks very much
    , why is that void, not somthing like
    int cmpint(struct element *a1, struct element *a2)
    {

    return a1-> value - a2-> value;
    }

  3. #3
    Registered User
    Join Date
    Apr 2003
    Posts
    5
    thanks so can i still write something like;what's the problem, what's your suggestion, and how to fix it.thanks for your kindness

    #include <stdlib.h>
    #include <math.h>
    #include <stdio.h>
    #include <unistd.h>
    #include <string.h>

    #define MIN(a, b) (a < b) ? a : b
    #define MAXLINELEN 200
    #define ARRAY_LEN 5000
    typedef struct element Element;
    struct element {
    int value;
    char *str;
    } elements[5000];

    void swap(int *px,int *py);

    int cmpint(struct element *a1, struct element *a2);
    int cmpstr(struct element *a1, struct element *a2);
    int comps=0;
    int field;
    int count;
    void mysort1(struct element *base, int nel, int width, int (*cmpint)(struct element *, struct element*));
    void BUmergesort(struct element *array, int l, int r, int width, int (*cmpint)(struct element*, struct element*) );
    void merge(struct element *pa, int l, int m, int r, int width, int (*cmpint)(struct element*, struct element*) );
    void usage(char *argv);
    int main(int argc, char *argv[])
    {
    struct element Element;
    extern char *optarg;
    extern int optind, opterr, optopt;
    FILE *ifp = stdin;
    FILE *ofp = stdout;
    char *infile = NULL;
    char *outfile = NULL;
    int field,c;
    int natural;
    char buf[MAXLINELEN];
    char *type;
    int nl=0;

    while ((c = getopt(argc, argv, "i: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;
    if (field == 1)
    {
    mysort1(elements, 0, count - 1, cmpint);
    } else {
    mysort1(elements, 0, count - 1, cmpstr);
    }

    ofp=fopen(outfile,"w");
    if (!(ofp = fopen(outfile, "w"))) {
    fprintf(stderr,"Error,can not open file '\n");
    }

    else {
    mysort1(elements, 0, count - 1, cmpint);
    ofp=fopen(outfile,"w");
    if (!(ofp = fopen(outfile, "w"))) {
    fprintf(stderr,"Error,can not open file '\n");}
    }
    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 */
    }
    }
    fclose(ifp);
    fclose(ofp);
    printf("%d comparsions\n",comps);
    return 0;
    }

    void usage(char *argv0)
    {
    fprintf(stderr, "usage: %s [-i infile] [-o outfile] [-f {1|2}][-s {n|b}]\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);
    }

    void mysort1(struct element *base, int nel, int width, int (*cmpint)(struct element *, struct element*))
    {
    BUmergesort(base,0,nel-1,width,cmpint);
    }

    void BUmergesort(struct element *array, int l, int r, int width, int (*compar)(struct element*, struct element*) ) {
    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, cmpint );
    }


    void merge(struct element *pa, int l, int m, int r, int width, int (*cmpint)(struct element *, struct element*) ) {
    int i, j, k;
    struct element *aux = malloc( width * ARRAY_LEN ); // ARRAY_LEN should be m-l+1 ???
    struct element *a = pa;

    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 ( cmpint( &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 );
    }

  4. #4
    Registered User
    Join Date
    Apr 2003
    Posts
    5
    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);
        }
    Last edited by penny_731729; 04-28-2003 at 12:50 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need help with linked list sorting function
    By Jaggid1x in forum C Programming
    Replies: 6
    Last Post: 06-02-2009, 03:14 AM
  2. sorting structure members using pointers
    By robstr12 in forum C Programming
    Replies: 5
    Last Post: 07-25-2005, 06:50 PM
  3. Sorting words with a fast, effincient sorting method
    By Unregistered in forum C++ Programming
    Replies: 19
    Last Post: 07-12-2002, 05:21 PM
  4. Still Needing Help : selection sorting
    By Unregistered in forum C Programming
    Replies: 6
    Last Post: 10-14-2001, 09:41 PM
  5. selection sorting
    By Unregistered in forum C Programming
    Replies: 5
    Last Post: 10-13-2001, 09:05 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21