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

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.

Originally Posted by Adak

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!

Originally Posted by Adak

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]"?

Originally Posted by arti

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

Originally Posted by Adak

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

Originally Posted by ZuK

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!

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

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.

Originally Posted by Adak

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?

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

I'll send my entire code in a message

Originally Posted by Adak

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.

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.