Thread: Help here with qsort!

  1. #1
    Registered User xxxrugby's Avatar
    Join Date
    Jan 2005
    Posts
    178

    Help here with qsort!

    Just dont get it!
    When I wanna sort int, works fine.
    But this. Need Help in sorthing this qsort!

    Code:
    #include <stdio.h>
    #include <string.h>
    
    struct DATA {
           char name[10];
           char last_name[10];
    }data[1024];
    
    int main()
    {
        int i = 0, n; char temp[30];
        printf("How many elements you wanna insert : ");
        scanf("%d", &n);
        for(i = 0; i < n; i++)
        {
              printf("\nInsert name : ");
              scanf("%s", &temp);
              strcpy(data[i].name, temp);
              printf("Insert lastname : "); 
              scanf("%s", &temp);
              strcpy(data[i].last_name, temp);
        }
        
        for(i = 0; i < n; i++)
        {
              printf ("\n%s %s", data[i].name, data[i].last_name);
        }
        
        return 0;
    }
    Sorry for spelling errors, not English!
    xxxrugby: "All Human Race Will Die From My Hand!"
    xxxrugby: "We are all philosophers, when question is about politics!"

  2. #2
    Obsessed with C chrismiceli's Avatar
    Join Date
    Jan 2003
    Posts
    501
    printf("\nInsert name : ");
    scanf("%s", &temp);
    strcpy(data[i].name, temp);
    printf("Insert lastname : ");
    scanf("%s", &temp);
    strcpy(data[i].last_name, temp);
    you don't need the & when you are scanning into arrays, you might want to start looking into fgets http://faq.cprogramming.com/cgi-bin/...&id=1043284385
    Then you might want to look into linked list .
    BTW, what does this have to do with qsor?
    Help populate a c/c++ help irc channel
    server: irc://irc.efnet.net
    channel: #c

  3. #3
    Registered User xxxrugby's Avatar
    Join Date
    Jan 2005
    Posts
    178
    I wanna insert lets say 5 names. And sort them by alphabet!
    Sorry for spelling errors, not English!
    xxxrugby: "All Human Race Will Die From My Hand!"
    xxxrugby: "We are all philosophers, when question is about politics!"

  4. #4
    Handy Andy andyhunter's Avatar
    Join Date
    Dec 2004
    Posts
    540
    Ok so far you haven't even shown any code with respect to any sorting.

    qsort is a function which performs a quicksort using a user supplied function for comparison. That's right, you are still responsible for handling the comparison between two elements. The qsort function however handles all the iterating through the elements and storing the final sorted value. Let's have a look at the function definition:
    Code:
    void qsort (
               void* base,
               size_t num,
               size_t width,
               int(__cdecl*compare )(const void *, const void*);
    Now it is not as complicated as it looks to begin with. Lets start with
    the first parameter, void* base. All this is a pointer to the array that you are sorting. Now the array can contain pointers, or anything you want. That is why there is the userdefined compare function. This way you aren't restricted on what qsort can handle. This is also why you must typecast your pointer here to type void.

    The second parameter, size_t num, is pretty easy to understand. It is simply the number of elements in your array to be sorted. So if you had an array of 5 names, each name 10 characters in length(aka)
    Code:
                       char names[5][10];
    the number of elements that you wish to sort is 5.

    The third parameter, size_t width, is simply the size of the element in bytes. So using the above example the size of each element would be sizeof(char)*10.

    Now the fourth parameter is usually where some confusion sets in although it really is as easy as the other three parameters. This parameter is a pointer to the user defined comparison function. There are just some requirements for this function:

    1. The function must return an integer value in the following form:

    < 0 element1 is less than element2
    = 0 element1 is equal to element2
    > 0 element1 is greater than element2

    2. The parameters passed to the function are in the form of const void*. So thus a function declaration for a compare function used by qsort would look something like:
    Code:
    int myCompareFunction(const void*, const void*);
    3. Since the parameters are passed to your compare function as type void* you must typecast them to their appropriate type in order to perform the comparison. So if we wanted to compare integers our comparison portion might look like:
    Code:
               if(*(int*)element1 <  *(int*)element2) 
                                     return -1;
    Now enough with all this talking. Time to wrap this up by looking at a fully functional program that sorts 3 names.
    Code:
    #include <stdlib.h>
    #include <stdio.h>
    #include <string.h>
    
    int cmpFunction(const void*, const void*);
    
    int main(void) {
    
        char nameArray[3][10];
    
        strcpy(nameArray[0],"Chris");
        strcpy(nameArray[1],"Zambo");
        strcpy(nameArray[2], "Abba");
    
        printf("Current array is: \n");
        for(int i = 0; i < 3; i++){
            printf("%d. %s\n", i, nameArray[i]);
        }
        
        qsort((void*)nameArray, // target - pointer to data to be sorted
              3, // Array size in elements
              sizeof(char)*10, // Element size in bytes
              cmpFunction); //Pointer to comparison function
    
        printf("\nSorted array is: \n");
        for(int i = 0; i < 3; i++){
            printf("%d. %s\n", i, nameArray[i]);
        }
    
        return 0;
    }
    int cmpFunction(const void* name1, const void* name2) {
    
        return strcmp((char*)name1, (char*)name2);
    }
    I hope this helps you and any else looking at this thread for that matter.

    Happy Coding!!
    Last edited by andyhunter; 02-07-2005 at 08:06 PM.
    i don't think most standard compilers support programmers with more than 4 red boxes - Misplaced

    It is my sacred duity to stand in the path of the flood of ignorance and blatant stupidity... - quzah

    Such pointless tricks ceased to be interesting or useful when we came down from the trees and started using higher level languages. - Salem

  5. #5
    Registered User xxxrugby's Avatar
    Join Date
    Jan 2005
    Posts
    178
    Thanks andyhunter.
    Now finally I understand qsort algorithm.
    This code below is just for you to see that I maded with your help!
    Code:
    #include <stdio.h>
    #include <string.h>
    
    struct DATA {
           char name[10];
           char last_name[10];
    }data[1024];
    
    int cmpFunction(const void*, const void*);
    
    int main()
    {
        int i = 0, n = 0; char temp[30];
        printf("How many elements you wanna insert : ");
        scanf("%d", &n);
        for(i = 0; i < n; i++)
        {
              printf("\nInsert name : ");
              scanf("%s", &temp);
              strcpy(data[i].name, temp);
              printf("Insert lastname : "); 
              scanf("%s", &temp);
              strcpy(data[i].last_name, temp);
        }
         printf("\nQSORT by name :\n");
            qsort((void*)data, // target - pointer to data to be sorted
              n, // Array size in elements
              sizeof(char)*20, // Element size in bytes
              cmpFunction); //Pointer to comparison function
        for(i = 0; i < n; i++)
        {
              printf ("\n%s %s", data[i].name, data[i].last_name);
        }
        
        system("PAUSE");
        return 0;
    }
    
    int cmpFunction(const void* name1, const void* name2)
    {
        return strcmp((char*)name1, (char*)name2);
    }
    Sorry for spelling errors, not English!
    xxxrugby: "All Human Race Will Die From My Hand!"
    xxxrugby: "We are all philosophers, when question is about politics!"

  6. #6
    Registered User
    Join Date
    Jan 2005
    Posts
    204
    Hey andyhunter...
    Could you write something just like that about linked lists?
    You're pretty good at explaining things. Write a book dude!

  7. #7
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by caduardo21
    Hey andyhunter...
    Could you write something just like that about linked lists?
    You're pretty good at explaining things. Write a book dude!
    You could always just read the FAQ on linked lists.

    Quzah.
    Hope is the first step on the road to disappointment.

  8. #8
    Handy Andy andyhunter's Avatar
    Join Date
    Dec 2004
    Posts
    540
    Could you write something just like that about linked lists?
    The better way to have asked that would've been, hey I read the tut on linked list and I am still confused. Could you explain that?

    The answer to that is of course yes:

    Understanding Linked Lists

    A linked list is simply a group of structures (containers to be exact, you can have a series of class objects) that have at least one member that is a pointer to the next object in the list. Now this isn’t as complicated as it may sound, lets take a look at it piece by piece.

    1. A linked list is a group of structures; thus one element in the linked list(often referred to as a node) would be a structure. So an example of this node would be similar to:
    Code:
    struct myNode {
        char name[10];
    };
    2. These nodes must contain at least one member that is a pointer to the next structure. Now we say at least one member because often it is more convenient to have 2 pointers; one pointing to the next node and one pointing to the previous node. So we know we need a pointer that is of type of our structure, thus something like this:
    Code:
    struct myNode* nextNode;
    So putting this together we get the definition of our node:
    Code:
    struct myNode {
        char name[10];
        struct myNode* nextNode;
    };
    Now that we understand the concept of what a node is lets move onto the implementation of the linked list. As stated previously a linked list is a group or chain of nodes. As with all chains we need to define an anchor or starting point. This starting point is simply a pointer that is of type of our structure. So our implementation of this anchor would be like:
    Code:
    struct myNode* firstNode;
    You define the end of a linked list by having the last node’s next pointer set to NULL. Now in the beginning of our program to signify an initially empty list we will set firstNode to NULL. Thus you will usually see something along the lines of:
    Code:
    firstNode = NULL;
    Alright the remaining concept to grasp the fundamentals of linked lists lies in successfully adding and removing nodes from our list. These topics revolve around dynamic memory allocation, using malloc() and free().This topic is as easy to understand as the previous topics however it seems to be the hardest for new programmers to grasp so we’ll spend some time here. The prototype for malloc() is:
    Code:
    void* malloc(size_t size);
    All malloc() does is allocate size bytes and returns a pointer of type void to that memory, or NULL if an error occured. So you are probably asking, well that’s great but how do I use it? Well the standard convention for using malloc is:
    Code:
    pointer = malloc(n * sizeof(*pointer));
    where n is the number of elements you need and *pointer (the dereferenced pointer) is used to determine the size of the individual element. So if I wanted to create 1 new node (our node we have been using) I would do it like so:
    Code:
    //allocate space for our node
    newNode = malloc(1 * sizeof(*newNode));
    //check for error
    if(newNode == NULL){
         printf("Error allocating memory");
         return;
    }
    *Note, the ISO standard dictates there is no need to cast the return from malloc(), however some compilers may complain about being unable to convert the types. If this happens you can still use malloc, simply cast the return*

    Now that we understand how to allocate the memory, lets take a look at how we add the node to our list. Remember that we signify the end of our list by having the last node’s next node pointer be NULL. Thus to add a new node we simply “walk through” our linked list until we find the last node. Once we are there we set the last node’s next node pointer to our newly created node. Thus the implementation would look like:
    Code:
    //first check if the linked list is empty
    //if it is make the new node the first node
    if(firstNode == NULL) {
         firstNode = newNode;
         return;
    }
    //if not find the last node
    walker = firstNode;
    while(walker->nextNode != NULL){
         walker = walker->nextNode;
    }
    //set last node's next node to our new node
    walker->nextNode = newNode;
    To delete a node is just as easy as adding a node but before we dive into that lets take a look at how we free the memory we allocated with malloc(). The function is conveniently called free() and its prototype is:
    Code:
    void free(void* mem);
    where mem is a pointer to the block of memory allocated dynamically. Note that there is no return value and free does not ask for nor want a size to free. It simply releases the amount of memory pointed to by mem. Pretty easy, right?

    So now you are probably asking, well that’s great but how do I delete my node from the list? Remember that these lists are chained together simply by the pointers that each element has. So to remove an element from the list all you need to do is:
    1. Find the node to delete and the previous node
    2. Make the previous node’s next node pointer point to the node following the node to delete (aka set the previous node’s next node member equal to the node to delete’s next node member).
    3. free the memory allocated for the node to delete.

    So lets look at this 1 step at a time:
    1. Find the node to delete and the previous node
    Code:
    //if deleting the first node
    if(nodeNumber == 1){
         nodeToDelete = firstNode;
         firstNode = firstNode->nextNode;
    }else{
         //start at the begginning
         nodeToDelete = firstNode;
         prevNode = NULL;
         //find the previous node and node to delete
         for(int i = 0; i < nodeNumber - 1; i++){
              prevNode = nodeToDelete;
              nodeToDelete = nodeToDelete->nextNode;
         }
    2. Make the previous node’s next node pointer point to the node
    Code:
    prevNode->nextNode = nodeToDelete->nextNode;
    3. free the memory allocated for the node to delete.
    Code:
    free(nodeToDelete);
    And that is all there is to removing a node from a linked list and about all the basics for a linked list. Normally you would sort your linked list but that is a matter for another lesson, or the interested individual to figure out. Hopefully this will help you hit the ground running. Attached below is a full sample program that displays the principles explained above.
    Last edited by andyhunter; 02-08-2005 at 08:48 PM.
    i don't think most standard compilers support programmers with more than 4 red boxes - Misplaced

    It is my sacred duity to stand in the path of the flood of ignorance and blatant stupidity... - quzah

    Such pointless tricks ceased to be interesting or useful when we came down from the trees and started using higher level languages. - Salem

  9. #9
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,656
    qsort - linked lists, what happened to staying on topic?

    OIC, it was hijacked by caduardo21
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  10. #10
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Because linked list questions don't get enough of their own threads.

    Quzah.
    Hope is the first step on the road to disappointment.

  11. #11
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,656
    Perhaps it's a linked list of topics
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  12. #12
    Handy Andy andyhunter's Avatar
    Join Date
    Dec 2004
    Posts
    540
    Hey, I think the qsort() question was was answered sufficiently.
    i don't think most standard compilers support programmers with more than 4 red boxes - Misplaced

    It is my sacred duity to stand in the path of the flood of ignorance and blatant stupidity... - quzah

    Such pointless tricks ceased to be interesting or useful when we came down from the trees and started using higher level languages. - Salem

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. An interesting problem of qsort()
    By meili100 in forum C++ Programming
    Replies: 6
    Last Post: 03-05-2008, 12:09 PM
  2. qsort() in Array of Pointer to String
    By vb.bajpai in forum C Programming
    Replies: 8
    Last Post: 06-16-2007, 04:18 PM
  3. trouble with qsort
    By qubit67 in forum C Programming
    Replies: 5
    Last Post: 04-29-2007, 10:23 PM
  4. Question About Using qsort
    By Zildjian in forum C Programming
    Replies: 3
    Last Post: 11-04-2003, 03:17 PM
  5. C++ link error with qsort
    By bvnorth in forum C++ Programming
    Replies: 7
    Last Post: 10-24-2003, 02:22 AM