Thread: Problem with arrays structures sorting.

  1. #16
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    I believe C.A.R. Hoare would be very upset if we had to use just one implementation of his beautiful sorting algorithm.

    Did you jump to a conclusion there Meldreth? You know what happens when you jump to conclusions like that.

    Echo my left foot.

  2. #17
    Registered User
    Join Date
    Feb 2009
    Posts
    138
    Quote Originally Posted by Adak
    I believe C.A.R. Hoare would be very upset if we had to use just one implementation of his beautiful sorting algorithm.
    without lots of proof, i trust the library more than i trust an ad hoc implementation by an egotist who thinks he can compete.
    Did you jump to a conclusion there Meldreth?
    i could say you jumped to the conclusion that when i wrote qsort it meant the quicksort algorithm and not c's qsort function. i think what really happened is you intentionally misread my words so you could make a petty jab at me. and you proved it with your next statement. weak.
    Quote Originally Posted by Adak
    Echo my left foot.
    bitter much?

  3. #18
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by Adak
    I believe C.A.R. Hoare would be very upset if we had to use just one implementation of his beautiful sorting algorithm.
    Hoare's sorting algorithm is named "quick sort", not "qsort".
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  4. #19
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote Originally Posted by Meldreth View Post
    without lots of proof, i trust the library more than i trust an ad hoc implementation by an egotist who thinks he can compete.

    i could say you jumped to the conclusion that when i wrote qsort it meant the quicksort algorithm and not c's qsort function. i think what really happened is you intentionally misread my words so you could make a petty jab at me. and you proved it with your next statement. weak.

    bitter much?
    No no, just having fun. I thought you were, as well.

    Qsort is quite good, but it's not the very best implementation of Quicksort. The newer C++ version is one such better version.

    To be honest, I was thinking of my Quicksort code, but of course, it's not *my* code. It's from a book. I used to tweak it a bit for special sorting jobs. Don't do that anymore, though. There's no need to tweak it, because the faster hardware has made all but the most extremely demanding sorting job, well within what I need.

    I'm just a hobby coder, so I'm guessing you're a better programmer than I am. I'm not competing with you, or the standard library version of Quicksort.

  5. #20
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by Adak
    Qsort is quite good, but it's not the very best implementation of Quicksort. The newer C++ version is one such better version.
    As far as I can tell, quicksort is not mandated for the implementation of qsort and std::sort, though typically a variant of quicksort is used.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  6. #21
    Registered User
    Join Date
    Feb 2009
    Posts
    138
    Quote Originally Posted by Adak
    No no, just having fun. I thought you were, as well.
    of course i'm havng fun. you're my new "Special Friend".
    Quote Originally Posted by Adak
    Qsort is quite good, but it's not the very best implementation of Quicksort.
    so you've checked the source code for every compiler in existence and determined that none of them uses the very best implementation of quicksort? who's measure of "very best" are you using? c++'s? c++ usually uses introsort, and introsort isn't really quicksort. it's a hybrid of quicksort, heapsort, and insertionsort designed to overcome quicksort's flaws. there's nothing stopping a compiler from using introsort for qsort too. or bubblesort. at least c++'s sort has a performance guarantee.
    Quote Originally Posted by Adak
    I'm just a hobby coder, so I'm guessing you're a better programmer than I am.
    damn skippy. who knows or cares who's better, but my ego dictates that i have to assume it's always me.

  7. #22
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    I read a book on sorting, and it showed how quicksort could be optimized, if you were careful.

    I don't have that ego driven dictate. It would make no sense to think I'm somehow "better", because I clung to some vaporous assumption. I like to be more objective than that.

    I recall an episode of the Animaniac's where they were being canceled, and they did this long and very hilarious song about their studio exec. I was in stitches. Never saw a funnier cartoon. Their 50 states and capitals song was quite clever, as well.

  8. #23
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Meldreth's "animaniacs" observation fits my theory that quicksort would really be better known as quacksort -- but I said that somewhere else already.

    "introsort" must really be the beginning of the end.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  9. #24
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by MK27
    Meldreth's "animaniacs" observation fits my theory that quicksort would really be better known as quacksort -- but I said that somewhere else already.
    I really don't see why any correct sorting algorithm should be known as "quacksort", except maybe bogosort, but even bogosort is correct.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  10. #25
    Registered User
    Join Date
    Feb 2009
    Posts
    7
    Could give me an example to use as i am strugglling to start off, i know this is asking an annoying question but i have dedicated a lot of time to this and it is getting very frustrating.
    thanks

  11. #26
    Registered User
    Join Date
    Feb 2009
    Posts
    138
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    struct element
    {
        char name[128];
        int freq;
    };
    
    int cmp_name(const void *a, const void *b);
    int cmp_freq(const void *a, const void *b);
    void list(struct element *a, int sz);
    
    int main()
    {
        FILE *fp = fopen("test.txt", "r");
        int (*cmp_pf)(const void*, const void*);
        struct element elm[200];
        int n, opt;
        for (n = 0; n < 200; n++) 
            if (fscanf(fp, "%s%d", elm[n].name, &elm[n].freq) != 2) 
                break;
        fclose(fp);
        printf(
            "how would you like the data sorted?\n"
            "1: by name\n"
            "2: by abundance\n> ");
        scanf("%d", &opt);
        cmp_pf = (opt == 1) ? &cmp_name : &cmp_freq;
        qsort(elm, n, sizeof(struct element), cmp_pf);
        list(elm, n);
        return EXIT_SUCCESS;
    }
    
    int cmp_name(const void *a, const void *b)
    {
        return strcmp(((struct element*)a)->name, ((struct element*)b)->name);
    }
    
    int cmp_freq(const void *a, const void *b)
    {
        return ((struct element*)a)->freq - ((struct element*)b)->freq;
    }
    
    void list(struct element *a, int sz)
    {
        int i;
        for (i = 0; i < sz; i++) printf("%s %d\n", a[i].name, a[i].freq);
    }

  12. #27
    Registered User
    Join Date
    Feb 2009
    Posts
    7
    Thank you so much, that has helped me get my head around how to work my program.

  13. #28
    Registered User
    Join Date
    Feb 2009
    Posts
    7
    I have made a draft of the program using your code as a basis, however i keep getting either an error when runnign from command promt saying " the instruction at 0x7c90100b referenced memory at 0x00000034. the memory could not be read" or if i run through my compiler i get a screen continually displaying pages of 1/4 over again. can;t seem to work out the problem, i'm probably overlooking somthing aren't i?
    here is the code:
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    struct element
    {
        char name[128];
        int abund;
    };
    
    int cmp_name(const void *a, const void *b);
    int cmp_abund(const void *a, const void *b);
    void list(struct element *a, int sz);
    
    int main()
    {
        
        char name[128];
        FILE *fp; 
        char s[1000];
        {
         printf("\nPlease input a file name including extension\n");
         gets(name);
         fp=fopen(name,"r");
         while (s!=NULL)
         printf("%s",s);
         while (fgets (s,1000,fp)!=NULL);
         fclose(fp);
        }
      
        fp=fopen(name,"r");
        int (*cmp_pf)(const void*, const void*);
        struct element elm[1000];
        int n, opt;
        for (n = 0; n < 1000; n++) 
            if (fscanf(fp, "%s%d", elm[n].name, &elm[n].abund) != 2) 
                break;
        printf(
            "how would you like the data sorted?\n"
            "1: by name\n"
            "2: by abundance\n> ");
        scanf("%d", &opt);
        cmp_pf = (opt == 1) ? &cmp_name : &cmp_abund;
        qsort(elm, n, sizeof(struct element), cmp_pf);
        list(elm, n);
        return EXIT_SUCCESS;
    }
    
    int cmp_name(const void *a, const void *b)
    {
        return strcmp(((struct element*)a)->name, ((struct element*)b)->name);
    }
    
    int cmp_abund(const void *a, const void *b)
    {
        return ((struct element*)a)->abund - ((struct element*)b)->abund;
    }
    
    void list(struct element *a, int sz)
    {
        int i;
        for (i = 0; i < sz; i++) 
        printf("%s %d\n", a[i].name, a[i].abund);
    }

  14. #29
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    An error with such a low memory address means you've accessed something relative to a NULL pointer.

    "%s%d" does not sound like what you want for your fscanf. Don't you have a seperator such as a comma or space between those fields? I haven't run the program but I'd guess the bug is on that line.
    Try printing n after the for loop.

    Probably a good idea to read this (Meldreth too):
    http://www.akalin.cx/2006/06/23/on-t...ison-function/
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  15. #30
    Registered User
    Join Date
    Feb 2009
    Posts
    7
    nope, same problem occurs

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 26
    Last Post: 06-11-2009, 11:27 AM
  2. Array Sorting problem
    By ___________ in forum C++ Programming
    Replies: 4
    Last Post: 07-22-2008, 12:17 AM
  3. Problem with structures
    By dereach in forum C Programming
    Replies: 2
    Last Post: 10-30-2007, 08:22 AM
  4. problem with arrays and structures
    By gell10 in forum C++ Programming
    Replies: 7
    Last Post: 11-03-2003, 12:02 AM
  5. Sorting an Array of Structures
    By bob2509 in forum C++ Programming
    Replies: 7
    Last Post: 05-12-2002, 08:26 AM