Thread: To understand how to write a quick sort while using a struct

  1. #1
    Registered User arti's Avatar
    Join Date
    May 2010
    Posts
    108

    To understand how to write a quick sort while using a struct

    I have a program that requires to be written with a struct. I understand that this struct, now that a quick sort is being thrown in the mix, will need to have an array. What I don't understand is how I am supposed to combine these two pieces of code together so that they work in unison. I hope someone can explain to me how it works. Also I'm confused on how the array will affect the qsort. Thank you in advance for all your help! I've seen the tutorial on this website and others and still do not understand how to make this work.
    Code:
    typedef char STR15[15+1];
    typedef char STR10[10+1];
    
    typedef struct EmployeeRecord
    {
      STR15 lastname;
      STR10 firstname;
      float payrate,
            hrs,
            deferred,
            gross,
            ft,
            st,
            ssi,
            net,
    	hrs_wrk,
    	ovt_hrs;
    }EmployeeRecord;
    Code:
    #include <stdio.h>
    typedef int int10[10];
    
    void qsort(int10 table, int start, int finish);
    void showtable(int10 table, const char * message);
    
    int main(void)
    {
      int10 numbers0 = {67, 89, 23, 42, 13, 57, 23, 9, 2, 23};
      int10 numbers1 = {2, 9, 13, 42, 23, 57, 67, 89, 90, 99};
      int10 numbers2 = {99, 90, 89, 67, 57, 23, 42, 13, 9, 2};
    
      showtable(numbers1, "Before Sort");
      qsort(numbers1, 0, 9);
      showtable(numbers1, "After Sort ....");
      return 0;
    }
    
    void qsort(int10 table, int start, int finish)
    {
      int left=start,
          right=finish, 
          pivot=table[(start+finish)/2];
      while(left<right) {
        // find left candidate
        while (table[left] < pivot) left++;
        // find right candidate
        while (table[right] >pivot) right--;
        if(left <=right) {
          int temp = table[left];
          table[left]=table[right];
          table[right]=temp;
           left++;
           right--;
        }
      } //while left<right
      if (start<right) qsort(table, start, right);
      if (left<finish) qsort(table, left, finish);
    }
    
    void showtable(int10 table, const char * message)
    {
      printf("\t%s\n", message);
      { int i;
        for(i=0;i<10;i++) printf("%d\n", table[i]);
      }//local block
    }//show
    Last edited by arti; 05-08-2013 at 01:00 AM.

  2. #2
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    An array is the preferred data structure to have, when using Quicksort - it's not the only one, but it is the most common one, and the one where Quicksort really shines.

    There are two kinds of structs to be considered here -
    1) "flat" structs - all the record members sizes are the same, and fixed at compile time.
    2) "deep" structs - where one or more record members have their sizes allocated at run-time.

    Flat structs are easy to work with - you can swap them just like any other variable. Deep structs are more difficult, since each record member must be swapped using specific code - like strcpy(), etc. (there are some exceptions to this).

    Since your structs are the "flat" type, there should be no problem at all. Comparisons of struct member values is straight forward, so Quicksort will have no problems with this, at all.

    I need to see some work from you on this program. None of the above is your work, and frankly, you won't learn much by saying you're a visual learner - like who isn't - and waiting for someone to post the answer (or something you can readily adapt), for you.

    Um, umm, ummm.

    Come on and give it a try. If you get stuck, post your try at it, and tell us what has you stuck. We'll be glad to help, but help doesn't include starting the program for you. That part is up to you.

  3. #3
    Registered User arti's Avatar
    Join Date
    May 2010
    Posts
    108
    Quote Originally Posted by Adak View Post
    An array is the preferred data structure to have, when using Quicksort - it's not the only one, but it is the most common one, and the one where Quicksort really shines.

    There are two kinds of structs to be considered here -
    1) "flat" structs - all the record members sizes are the same, and fixed at compile time.
    2) "deep" structs - where one or more record members have their sizes allocated at run-time.

    Flat structs are easy to work with - you can swap them just like any other variable. Deep structs are more difficult, since each record member must be swapped using specific code - like strcpy(), etc. (there are some exceptions to this).

    Since your structs are the "flat" type, there should be no problem at all. Comparisons of struct member values is straight forward, so Quicksort will have no problems with this, at all.

    I need to see some work from you on this program. None of the above is your work, and frankly, you won't learn much by saying you're a visual learner - like who isn't - and waiting for someone to post the answer (or something you can readily adapt), for you.

    Um, umm, ummm.

    Come on and give it a try. If you get stuck, post your try at it, and tell us what has you stuck. We'll be glad to help, but help doesn't include starting the program for you. That part is up to you.
    No, the struct is my work. The quick sort is not; it is the code that the professor gave to the class. He told us he would be teaching less and less of the class, so he hasn't gone deep into how this is all supposed to come together. Anyways, I will take your advise and try it on my own. Thank you!

  4. #4
    Registered User arti's Avatar
    Join Date
    May 2010
    Posts
    108
    Quote Originally Posted by Adak View Post
    An array is the preferred data structure to have, when using Quicksort - it's not the only one, but it is the most common one, and the one where Quicksort really shines.

    There are two kinds of structs to be considered here -
    1) "flat" structs - all the record members sizes are the same, and fixed at compile time.
    2) "deep" structs - where one or more record members have their sizes allocated at run-time.

    Flat structs are easy to work with - you can swap them just like any other variable. Deep structs are more difficult, since each record member must be swapped using specific code - like strcpy(), etc. (there are some exceptions to this).

    Since your structs are the "flat" type, there should be no problem at all. Comparisons of struct member values is straight forward, so Quicksort will have no problems with this, at all.

    I need to see some work from you on this program. None of the above is your work, and frankly, you won't learn much by saying you're a visual learner - like who isn't - and waiting for someone to post the answer (or something you can readily adapt), for you.

    Um, umm, ummm.

    Come on and give it a try. If you get stuck, post your try at it, and tell us what has you stuck. We'll be glad to help, but help doesn't include starting the program for you. That part is up to you.
    One last thing. In the quicksort where it says "int table" is supposed to go
    "int record[i]"?

  5. #5
    Registered User
    Join Date
    Aug 2005
    Location
    Austria
    Posts
    1,990
    Quote Originally Posted by arti View Post
    One last thing. In the quicksort where it says "int table" is supposed to go
    "int record[i]"?
    Nowhere in quicksort it says "int table"

    Guess you mean the parameters for quicksort

    I'd use
    Code:
    void qsort( EmployeeRecord table[], int start, int finish);
    Kurt

  6. #6
    Registered User
    Join Date
    May 2012
    Posts
    1,066
    Quote Originally Posted by Adak View Post
    There are two kinds of structs to be considered here -
    1) "flat" structs - all the record members sizes are the same, and fixed at compile time.
    2) "deep" structs - where one or more record members have their sizes allocated at run-time.

    Flat structs are easy to work with - you can swap them just like any other variable. Deep structs are more difficult, since each record member must be swapped using specific code - like strcpy(), etc. (there are some exceptions to this).
    "Deep" structs are also easy to work with if you use an array of pointers to each struct instead of an array of the actual structs. Then you just need to swap the pointers.

    Bye, Andreas

  7. #7
    Registered User arti's Avatar
    Join Date
    May 2010
    Posts
    108
    Quote Originally Posted by ZuK View Post
    Nowhere in quicksort it says "int table"

    Guess you mean the parameters for quicksort

    I'd use
    Code:
    void qsort( EmployeeRecord table[], int start, int finish);
    Kurt
    Yes that's exactly what I meant. The variable of the struct is "record" so wouldn't I have use
    Code:
    void qsort(EmployeeRecord record[], int start, int finish);
    so I can access the struct?
    Thank you for your help! Much appreciated!

  8. #8
    Registered User arti's Avatar
    Join Date
    May 2010
    Posts
    108
    I have a struct that is called EmployeeRecord and it's variable is record. I have to implement my own version of the quick sort below, I understand that the struct needs an array so the quick sort can work.

    I have to sort by last name of the employee.
    What I need to understand is....is the parameter int10 table of the quick sort is supposed to be struct EmployeeRecord record[]? or since i'm sorting by last name does it have to be EmployeeRecord lastname[]??
    I'm so confused


    Code:
    #include <stdio.h>
    typedef int int10[10];
    
    void qsort(int10 table, int start, int finish);
    void showtable(int10 table, const char * message);
    
    int main(void)
    {
      int10 numbers0 = {67, 89, 23, 42, 13, 57, 23, 9, 2, 23};
      int10 numbers1 = {2, 9, 13, 42, 23, 57, 67, 89, 90, 99};
      int10 numbers2 = {99, 90, 89, 67, 57, 23, 42, 13, 9, 2};
    
      showtable(numbers1, "Before Sort");
      qsort(numbers1, 0, 9);
      showtable(numbers1, "After Sort ....");
      return 0;
    }
    
    void qsort(int10 table, int start, int finish)
    {
      int left=start,
          right=finish, 
          pivot=table[(start+finish)/2];
      while(left<right) {
        // find left candidate
        while (table[left] < pivot) left++;
        // find right candidate
        while (table[right] >pivot) right--;
        if(left <=right) {
          int temp = table[left];
          table[left]=table[right];
          table[right]=temp;
           left++;
           right--;
        }
      } //while left<right
      if (start<right) qsort(table, start, right);
      if (left<finish) qsort(table, left, finish);
    }
    
    void showtable(int10 table, const char * message)
    {
      printf("\t%s\n", message);
      { int i;
        for(i=0;i<10;i++) printf("%d\n", table[i]);
      }//local block
    }//show

  9. #9
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,615
    Yes that's exactly what I meant. The variable of the struct is "record" so wouldn't I have use
    void qsort(EmployeeRecord record[], int start, int finish);
    so I can access the struct?
    Yes. That is a good start. To get the quick sort working with Employees though, you also have to change the expressions used to compare employees in the array. Remember that quick sort was originally written to sort ints, so the pivot is an int (which needs to be changed, and you compare with < and >. When you compare two struct objects, you are actually comparing members of the different structs. So you have to decide what it means to sort Employees. I see two possibilities:

    1) You make the quick sort as robust as possible, offering comparison functions, and using function pointers in the sort to call any one of them.
    2) You can make a less ideal version that can only sort Employees 1 way, using a member or group of members.

    Depending on the assignment and what you learned, you will probably take the easy path (which is 2). This is fine. Option 1 is like writing the qsort() library function.

    To make the necessary changes you will need to understand how quick sort actually works. I can recommend reading wikipedia, or this because it has a quick sort section, or just searching the web. The changes for the new type will probably be easy once you understand the sort.

    HTH.

  10. #10
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    You have to change your int-centered code around a bit, so it will work with strings, instead.

    *pivot will be a char array, and be given the value of table[(start+finish)/2], and don't forget the ( )'s in there.

    *you can use strcmp(table[i].lastName, pivot) (include <string.h>) strcmp() returns an int based on the value of the first string it has in it's parameter (string1, string2). A value > 0 indicates that string1 is > string2. A value < 0 indicates that string1 is < string2. A zero return indicates that string1 equals string2.

    So:
    Code:
    while(strcmp(table[i].lastName, pivot) < 0) ++i;
    Is one way to use strcmp() in Quicksort's while loop.

    First thing I'd do is set this code aside for reference (it's a dandy Quicksort, however), and start making changes to a copy of it, so the number arrays are replaced by simple strings that are out of order: cat, ant, bat, etc.

    You need to start working with strings, not keep on working with the numbers.
    Last edited by Adak; 05-08-2013 at 10:55 PM.

  11. #11
    Registered User arti's Avatar
    Join Date
    May 2010
    Posts
    108
    Quote Originally Posted by Adak View Post
    An array is the preferred data structure to have, when using Quicksort - it's not the only one, but it is the most common one, and the one where Quicksort really shines.

    There are two kinds of structs to be considered here -
    1) "flat" structs - all the record members sizes are the same, and fixed at compile time.
    2) "deep" structs - where one or more record members have their sizes allocated at run-time.

    Flat structs are easy to work with - you can swap them just like any other variable. Deep structs are more difficult, since each record member must be swapped using specific code - like strcpy(), etc. (there are some exceptions to this).

    Since your structs are the "flat" type, there should be no problem at all. Comparisons of struct member values is straight forward, so Quicksort will have no problems with this, at all.

    I need to see some work from you on this program. None of the above is your work, and frankly, you won't learn much by saying you're a visual learner - like who isn't - and waiting for someone to post the answer (or something you can readily adapt), for you.

    Um, umm, ummm.

    Come on and give it a try. If you get stuck, post your try at it, and tell us what has you stuck. We'll be glad to help, but help doesn't include starting the program for you. That part is up to you.
    Hi Adak! I wrote the code by myself and a tutor at my school checked if it was correct. I am stuck though and it is a stupid question but how do you write the prototypes? I've seen that people write in the parameters like i did struct EmployeeRecord record[] but when I write the prototype...it is written like so Qsort(record[], int, int), right?

  12. #12
    Registered User arti's Avatar
    Join Date
    May 2010
    Posts
    108
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    void Qsort(struct EmployeeRecord record[], int start, int finish);//quicksort prototype
    void sTable(struct EmployeeRecord record, const char *message)//show table prototype
    
    typedef struct EmployeeRecord record;
    void Qsort(struct EmployeeRecord record[], int start, int finish)
    {
      int left,
          right;
      EmployeeRecord pivot;
      EmployeeRecord temp;
          left=start;
          right=finish;
          pivot=record[(start+finish)/2];
          while(left<right)
          {
            while(strcmp(record[left], pivot)< 0)++left;
            //find left candidate
            while(strcmp(record[right], pivot)> 0)--right;
            //find right candidate
            if(left<=right)
            {
             temp=record[left];
             record[left]=record[right];
             record[left]=temp;
             left++;
             right--;
            } while(left<right)
            if(start<right) qsort(table, start, right);
            if(left<finish) qsort(table, left, finish);
          }
    void sTable(struct EmployeeRecord record, const char *message)
    {
      printf("\t%s\n", message);
      { 
       int i;
       for(i=0;i<10;i++)
       printf("%d\n",record[i]);
      }
    }

  13. #13
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote Originally Posted by arti View Post
    Hi Adak! I wrote the code by myself and a tutor at my school checked if it was correct. I am stuck though and it is a stupid question but how do you write the prototypes? I've seen that people write in the parameters like i did struct EmployeeRecord record[] but when I write the prototype...it is written like so Qsort(record[], int, int), right?
    No.

    Prototypes are the more formal information on the function, so the data type (like "struct",int, char, etc.), needs to be included.

    NOTE: If the typedef was BEFORE (above), the prototype, and the name was not the same as the name of the array, then your prototype question you asked would be answered: Yes!

    In the actual CALL of the function, you would only need the name of the struct array, name of the first int variable, and the name of the second int variable.

    prototype:
    void Quicksort(struct EmployeeRecord record[], int, int);

    call:
    Quicksort(record, intVariable1, intVariable2);

    The prototype (by custom posted above main() ), can be exactly the same as the very first line of the function itself - but it can use just the data type, and not include the names of the variables.

    The call MUST include the names of the variables being passed to the function, but need not include the data types of those variables.



    In your code, the typedef is confusing - because you give it the same name as the array. Honestly, I've never seen such a thing, so I don't know if it's OK, or not, but I know it's confusing to me. Can you make it:
    Code:
    typedef struct Employeerecord Record; //with a capital R
    That would help me understand your code.

    Then in the sorting function, you need to refer to the actual record[left].lastName (I believe you named it), member name.

    record[left] is not going to work. You need to pinpoint the comparison to record[left].lastName, see?

    Also, in giving the pivot a value:

    1) The pivot must be a char array equal in size to that of the lastName record member.

    2) You can't just assign it:
    Code:
     pivot=record[(start+finish)/2];
    Because it's a string, not an int. (Also, this does not refer to any struct.member in particular). You have to refer to record[(start+finish)/2].lastName, and you need to use strcpy() (or some copy function), to copy the string over to the pivot.
    Code:
    strcpy(pivot, record[(start+finish)/2].lastName);
    Think strings for all your comparisons.
    Last edited by Adak; 05-09-2013 at 09:57 PM.

  14. #14
    Registered User arti's Avatar
    Join Date
    May 2010
    Posts
    108
    I'll send my entire code in a message

    Quote Originally Posted by Adak View Post
    No.

    Prototypes are the more formal information on the function, so the data type (like "struct",int, char, etc.), needs to be included.

    NOTE: If the typedef was BEFORE (above), the prototype, and the name was not the same as the name of the array, then your prototype question you asked would be answered: Yes!

    In the actual CALL of the function, you would only need the name of the struct array, name of the first int variable, and the name of the second int variable.

    prototype:
    void Quicksort(struct EmployeeRecord record[], int, int);

    call:
    Quicksort(record, intVariable1, intVariable2);

    The prototype (by custom posted above main() ), can be exactly the same as the very first line of the function itself - but it can use just the data type, and not include the names of the variables.

    The call MUST include the names of the variables being passed to the function, but need not include the data types of those variables.



    In your code, the typedef is confusing - because you give it the same name as the array. Honestly, I've never seen such a thing, so I don't know if it's OK, or not, but I know it's confusing to me. Can you make it:
    Code:
    typedef struct Employeerecord Record; //with a capital R
    That would help me understand your code.

    Then in the sorting function, you need to refer to the actual record[left].lastName (I believe you named it), member name.

    record[left] is not going to work. You need to pinpoint the comparison to record[left].lastName, see?

    Also, in giving the pivot a value:

    1) The pivot must be a char array equal in size to that of the lastName record member.

    2) You can't just assign it:
    Code:
     pivot=record[(start+finish)/2];
    Because it's a string, not an int. (Also, this does not refer to any struct.member in particular). You have to refer to record[(start+finish)/2].lastName, and you need to use strcpy() (or some copy function), to copy the string over to the pivot.
    Code:
    strcpy(pivot, record[(start+finish)/2].lastName);
    Think strings for all your comparisons.

  15. #15
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    You need to make the changes to your code, that I've posted above. Pivot is still being treated like an integer in your code - and it's always going to be a string, in your program.

    I don't understand why you're not making the changes I've noted for you. I thought they were detailed enough.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. I don't want to write a code I don't understand ..!!
    By bchaib in forum C Programming
    Replies: 28
    Last Post: 12-19-2007, 04:29 AM
  2. Quick Sort
    By e66n06 in forum C++ Programming
    Replies: 13
    Last Post: 08-21-2007, 08:02 AM
  3. Quick Sort or Merge Sort???
    By swanley007 in forum C++ Programming
    Replies: 6
    Last Post: 11-10-2005, 06:48 PM
  4. Quick sort VS Merge Sort
    By sachitha in forum Tech Board
    Replies: 7
    Last Post: 09-03-2004, 11:57 PM
  5. Shell Sort vs Heap Sort vs Quick Sort
    By mackol in forum C Programming
    Replies: 6
    Last Post: 11-22-2002, 08:05 PM