#C/Sorting strings
13 messages in this thread
My question is about sorting strings. I am working on a routine that accepts
any number of names and then sorts them by the last name. I am curious about
the best way to go about this. If the name is entered in as one string (the
way I would prefer) then strcmp won't sort it properly since it starts the
compare at the beginning of the string. Should I set up the input routine to
accept the first and last names separately or search each string for the
beginning of the last name and sort from there or is there an easier or more
preferred approach.
Hi Jack,
I would write a compare routine that did a simple scan along the line for the
surname. The compare routine could then be passed to qsort() to do the actual
sorting. Check out the qsort() family of functions in your compiler reference
manual. They are quite useful for this sort of thing, although they recurse, so
watch that stack!
Steve the G. [BEDFORDSHIRE, UK]
Jack,
Since you are reading the names in one at a time, I would suggest an
"insertion sort". As for comparing them last name, first name – try this:
Using strchr, find the space between the first name and last name.
Convert that space into a '\0'. Now, the original string will
return the first name, while a pointer to the character after
the space will return the last name.
As for how you do an insertion sort, what you do is create an array of pointers
to pointers to char. The array should be as large as the largest list you need
to sort. (Ideally, you can replace the array with a linked list, but bear with
me.)
Now, the first name you read into the array becomes the first element. the next
name is compared with it and is added either before or after the first one.
This continues, with each new name being compared with all the previous ones
and being inserted at the correct point.
You can do the compares by starting with the first element each time, or by
doing a binary table search, or whatever. If the lists are short (say, less
than 1000 names) starting with the first element each time should be fast
enough on even a stock amiga.
Obviously, there are faster sorting techniques, but this one is very easy to
implement and fairly efficient.
Michael,
actually, if you're going to use an insertion sort, your data structure
should be a linked list rather than an array. Far more economical,
especially when inserting new elements.
Brian
Agreed, Brian. I just did't know where the guy's programming experience was.
Didn't want to confuse him with too many issues at once.
Michael,
ah, didn't think of that.
Brian
You could also read in the first and last names separately into
different components of a structure (e.g.
struct data {
char * fname;
char * lname;
.. other data ..
};
and the sorting function which you then pass to qsort can be aware
of the structure and do the compare any way you want.
This is a very general way of getting *any* multi-key sort to work
with qsort.
in my opinion, the data structure you have presented is a given.
I differ with you as to the sort algorithm. QuickSort, although it
is a favorite among many programmers, is problematic at best. If a
linked list is used for the overall data structure, it is far easier
to use an insertion sort as each data element is entered rather than
creating the list and passing it to QuickSort as a list. Any list
will perform better under an insetion sort at execution time than a
whole list passed for QuickSort at insertion of each data element,
especially if stability of data is a consideration. (QuickSort is
notoriously unstable, i.e., things that were previously in order may
be out of order on the secondary key with QuickSort.)
Or to put it another way, QuickSort uses 2NlnN comparisons, on
average, whereas the insertion sort on a doubly-linked list uses
N**2/4 comparisons and N**2/8 exchanges, in the worst case. However,
the insertion sort is almost linear, unlike QuickSort, when dealing
with an almost sorted data set, which a name array that is insertion
sorted as it is built will demonstrate.
If I haven't thoroughly confused you (and I hope I haven't!),
QuickSort pays off when you are going to pass a whole list for
sorting, insertion sort pays off if you are going to be building the
sorted list on the fly. I've only become aware of these issues as I
write my database program.
/*
You could also read in the first and last names separately into
different components of a structure (e.g.
struct data {
char * fname;
char * lname;
.. other data ..
};
*/
Yes, then you could use something like
scanf("%s %s",data.fname,data.lname)
to read in the string and the names will be parsed for you.
-Jerry
scanf is generally useless except for rare circumstances.
Going to route of struct data { char *fname;….. }; is a
sound one though. Of course space need to be allocated for
fname to point to before doing anything with it.
I must agree. scanf is one of those routines which IMHO is too complex
for the beginning user (when you have to consider the odd cases) and not
complex enough for the advanced user. I'm not sure how I might make it
easier to use, but I recommend avoiding it in general and writing your own
hand parsers for input.
I recommend using fgets to read the line, then use sscanf to
process/parse the line. This seems to me to give you better
control. You always know where the file is positioned to –
unlike scanf which leaves the position be if it does not
match the format string.
-Jay Pedersen
>I recommend using fgets to read the line, then use sscanf to
>process/parse the line. This seems to me to give you better
>control.
It is better off, however, it still leaves a number of things
uncontrollable. As in all programming, it becomes a judegement call
depending upon the context.