Sorting a linked list of structs on multiple parameters.

[jagu22]

Hi
I have a linked list of struct.
with fields last name, first name, age

I want to sort this linked list based on the parameter provided by the user.

If the user provides last name, i want that list be sorted by last name. If 2 or more people have same last name then it be sorted by their first name, and if first names are also same for any then by age.

Same for first name sorting. initial sort by first name, then last name and then age


I haven't been able to figure out how to do this.Since I have a large file of this data, i would have to find an efficient solution.


Thanks in Advance

Jagu

[donbock]

You only need to look at the next key if the previous one was identical for the two records.

"If the user provides last name, i want that list be sorted by last name."
So what do you want to do if one record has a last name but the other doesn't?

Do you want to do a case-insensitive comparison?
How do you want to handle punctuation (such as dash or apostrophe)?
That is, do you want O'Reilly to match oreilly?

[jagu22]

Each struct has a last name, first name and age.

Punctuation be different. O'Reilly and oreilly be different.
Comparisons be case-sensitive.

I m more concerned in making it efficient , I can do it my way. But I need to have an efficient data structure use.
I have all the records in a linked list. And it will contain around 1000's of nodes.

So how to sort them is a major concern to me. Do i sort the list everytime I have to call the function. Or do I create 3 lists and keep them sorted throughout the program execution.

[donbock]

Age changes over time; and it changes on different days for different people. Do you mind if the sort order changes from one day to the next?

If so, then you should sort by birthdate (year-month-day) rather than by age.

In which order do you wish to sort by age: youngest first or oldest first?

Do you compute the age from birthdate and current date on the fly or is age explicitly stored in the database? If it is explicitly stored in the database, then are you worried that the value might be out-of-date?

[donbock]

Now I understand. All records have first name, last name, and age. The user may ask for a list sorted by last name or the user may ask for a list sorted by first name.

You have two fundamental key strategies: either construct the sort-key on the fly each time you need to resort or construct the key once when each record is created and store it in the record. Either way, the key is constructed by concatenating the three fields together in the appropriate order. You want to separate the fields with a character that is "further to the right" than any character that could legitimately appear in the fields. If you choose the latter strategy then you will actually have to store both sort-keys. Storing the sort-key(s) in the records makes sense the more times you have to resort the list.

You have two fundamental sort strategies: either resort each time the user asks for a list or sort the list both ways at the very beginning and respond to user requests by merely traversing the list rather than resorting it. If you choose the latter strategy then you will need two sets of links, one for each sort-key.

Can the user add, delete, or change entries? If so (and if you choose the latter sort strategy), then you need to adjust the list order every time one of these activities occurs. Adjustments of this kind ought to be possible without resorting the entire list.

[jagu22]

Can you tell me more how to sort on the key.
my last name, first name can be 10 characters each. and age 3 digits.
I understand that i concatenate the 3.
lastname+firstname+age

and that would go to 23 characters. But how do i sort them. for the missing characters i put Space . like if last name is of 5 chars. I put 5 spaces before concatenating the first name.

But how do i sort them.

[donbock]

You need to pick a field-separator character. It should be a lower sort-value than any character that might legitimately appear in any your fields, but it can't be '\0' because you need to reserve that code for terminating the string. I suggest '\001' -- it is the smallest non-null character value. This wouldn't work if your compiler's character encoding had a printable character for that value.

Choosing such a small value for the field separator eliminates the need to pad the first or last names with spaces.

You need to pad the age field with zeroes to insure it sorts properly.

For example, for a record equal to

Thomas Hardy, age 39

then the last-first-age key is "Hardy" "\001" "Thomas" "\001" "039";
and the first-last-age key is "Thomas" "\001" "Hardy" "\001" "039";

You can compare keys with the strcmp function.

[weaknessforcats]

But how do i sort them.

Are you able to sort an array of int?

If so, then there is a place in your code where you compare two ints.

When you sort your structs, there will be a place in your code where you compare two structs. Just call your function that compares two of your sort keys.

It would be helpful to have functions that a) create sort keys, b) compare to struct objects (this function should have the same return values as strcmp since this is a we--understood behavior), c) swaps two struct variables.

If you have code that sorts an array of int you should be able to modify it by removing the int stuff and substituting your functions above.