#Sorting linked list
22 messages in this thread
I have a linked list that has about 500 items in it so far. I am
trying to find a different way of sorting it than of searching
through the list to find the proper place to insert a new item. Each
sort takes about 40 to 50 seconds right now and this will get worse
as I continually add items. Does anyone have any ideas on a better
way to sort it?
We may need to go through an exercise of defining ground rules. You
have a linked list .. is there a reason for this other than keeping
the items in sorted order? Is the whole file brought in, or just a
record at a time? Is the "key field" on which you're sorting a small
part of the whole data record? Any objection to building a small
index file, containing: (1) the key for each record, in sorted
order, and (2) the position/location of the whole record? If you're
afraid that the small index file might not be THAT small, any
objection to building a smaller file containing, say, every 25th
record?
Could be when you've thought through the answers to these questions
you might have an approach to solving your problem.
–Jim
Jim, It is a linked list because each time the program is ran any
number of items may be added to it thus I don't know its final size.
The whole file is in memory at all times. The structure I am using
has 10 items, the program can sort on 4 of them. I have thought
about the index file but I am not sure on how to go about it. That
was why I asked the question. Hopes this clarify's my need a little
better.
The info is a good start, Jack. Now, about those ten fields for each record,
and your comment that the computer "can sort on 4 of them".
Could you give a little more detail, please? Does the computer
continuously have a (sorted) linked list for each index field? Or,
do you ask the computer to do a sort on a specific field when you
need it? Or, is it really just a multi-field key (thus, surname, and
if surname is the same, then city, and if both are the same, then
street name… you know the kind of thing).
One of the easier ways to do an index is just to write one more
sequential file, paralleling your data file. It's a bit like the
headings in your phone book .. or, if you like, the "keys" to each
volume of an encyclopaedia. Thus, you can say the logical equivalent
of: "AAA is record 1, DOE is record 11, HAMPTON is record 21, MURRAY
is record 31… ". In such a case, you would know that to find
FOGARTY you can start your search at record 11/12, and will find it
with 10 comparisons at most, if it's there.
It's often true that sequential key files are much shorter than
their data equivalents; for that reason, the key file sometimes
contains EVERY record. But it doesn't need to. Note also that my
above reference to records 11 or 21 do not need to be in numeric
sequence; in a linked list, the won't be. Rather, they are just the
point at which the list may be entered for searching.
And keep in mind that such an index file can be rebuilt very
quickly. Just roar through the linked list (no comparisons needed),
and make an entry into your index file every tenth (or twentieth, or
fiftieth) item.
–Jim
It is an inventory program I am working on and someof the fileds are
name, location, cost and the like. The program normally sorts on the
name filed but the user can request it to sort on location for
instance. Thanks for the suggestion on how to sort using the optional
list. It makes sense reading through it but since this is my first
try at something like this it will probably take a while to implement
it. I will try though. Thanks, Jack.
Jack, I see you're getting a lot of theory on sorting methods, which may or may
not be applicable to your data system. For example, insertion sorts are NOT so
bad if:
a) your program occasionally adds items to an already-sorted file;
b) insertion doesn't need massive movement/reorganization of records;
c) you can find the insertion point quickly. I think your application meets
criterion (a). For (b), you should have no problem with a linked list;
changing a couple of links should do the trick. The main difficulty lies with
(c); that's where a supplementary index might help.
It never hurts to learn about new tricks on the computer, even if you can't
use them right away. But keep your specific application firmly in mind, and
choose only that stuff that seems to apply. –Jim
40 to 50 seconds! What is this written in? Seems like a long time
to sort 500 items. Is this a text string comparison?
I would recommend you put your items into a hash table if the items
are fairly evenly spread out across a range.
With a hash table, you break the big list into, say, 10 smaller lists
which are indexed by some value. You can make a hash table with 26
lists based on the first letter of a string field. Then you copy
each item from the big list into it's correct smaller list in the
hash table. This way you can keep a fixed array of 10 or so linked
list pointers and you are sorting throuh shorter lists to put
something into place.
a -> apple, ardvark, author…
b -> balloon, beach, butter…
c -> china, class, correct…
With numerical fields, you would have to do something like take the 4
highest bits to get 16 smaller lists. Using the high byte would give you
256 sub lists which would be a little impractical to keep an array of 256
pointers for a list of 500 items. With hash tables you want data that is
evenly spread out across a range like a-z or 1-10.
(Lengthy description of Quicksort, Bubblesort, Shell and Shell-Metzger
sorts deleted because I remembered you are using a linked list. And it
was a really good explanation, too. Oh well.)
-Jerry
Thanks Jerry. I'll give it a try. But since I have not done this before would
you have any idea of where an example might be found? Jack
RE: Locating sample sort code.
Most programming algorithm textbooks will have a discussion of the Shell
sort and hash tables. I don't think the Shell-Metzger and heap sort are
very popular.
Kernighan and Ritchie's "The C Programming Language" has examples of the
Shell sort and hash tables, but it is skimpy on the explanation.
Below is a listing of some files here on CompuServe which contain example
code for implementing hash tables. I would take a look at these programs
first. If they aren't very clear (I haven't seen them myself), check out
a book on computer programming algorithms from your library.
I'm sorry I don't have a specific source to point you to. I learned a lot
about sorting in school. I think that at the time, the instructors were
just starting to teach more than number crunching but there wasnn't any
GUIs or Object Oriented stuff to teach. Seemed like every class did
nothing but sorting!
Let me know if you have any more questions on this. It sounds like
an interesting project.
Jerry, Forgot to answer your first question. Yes it is a string comparison.
Could this be one of the reasons why it takes so long? -Jack
Sorting strings will take longer. You have to do the comparison as a
routine instead of a simple instruction for integers.
An insertion sort is fine for small jobs, but it is not fast, as you
have found out. Any other sort should speed up your program. The
Shell sort would be a real trick to implement with singly linked
lists, however! If your doing an insert sort now, I think a hash
table is gonna make your computer boogie off the desktop.
Jack,
take a look at doing an insertion sort. It's a gem for linked lists
and I got over 1000 sorts per second with it when I used it for a complex
database. Just make sure that you pass the compare routine as a function
pointer so you can keep it generic and efficient.
Brian
bjbart@watserv.ucr.edu
I think I am doing an insertion sort now. I go through each item in
the list until I find where it belong and rearrange the pointers. But
if an items is at at the end of the list a lot of time is wasted on
the going through all the ones before it. Maybe I'm doing it
differently than you did. I'll have to look at it agin. Thanks, Jack
Jack,
if you are maintaining a pointer to the last list item, before you even
do a comparison to your first item in the list, do a comparison to your
last item. This will pay off very well if you accidently insert a sorted
list, btw.
"You do trust me, don't you? Of course you do."
— "To Play the King" (BBC)
Thanks Brian. I didn't think of that. I will give it a try. -Jack
Jack,
I don't usually discover things like that until I reach the profiler
stage.
"You do trust me, don't you? Of course you do."
— "To Play the King" (BBC)
I have written a sort routine which I call ZSort which will sort
linked listed data structures. I've used my own doubly-linked list
code (for portability), but you could eaisly modify it to use the
native system. ZSort sorts in near-linear time and will sort your
list of 500 items in way less than a second. It can use either
strings or integers as keys to sort on, and you specify them by
offset from the links. Intrested? If so, I'll upload it here.
-Fred.
Yes, I am very interested Fred. I have gotten a lot of good ideas from others
on the question but I don't know if I have enough experience to implement them.
A working example would be prefect and truly appreciated. Thanks again – Jack
Sorry I've been away so long — computer down time. I'll get the files
uploaded as soon as possible.