Subj : Re: "Faking a linked list" using arrays and sorting that list using an insertion sort...
To   : comp.programming
From : Willem
Date : Tue Oct 04 2005 10:36 pm

Kosio wrote:
)    I have some records that I need to sort.  Each record contains a
) rather large amount of data.  I will not have to sort more than 100
) records at a time, so an insertion sort should do the trick for me.  I
) will only sort based on only one value in the record.
)
)    One way to do this is just do an insertion sort, but I would also
) have to move more data around that way than I would like to move
) around.  Instead of swapping all of the values in the record, I would
) like to keep track of these records in some way and swap only their
) indexes, such that I can travel through their indexes and print out the
) data based on the corresponding index.

Wouldn't it be easier to just keep a separate list of indexes
that you sort ?

)    Basically I would like to do this by keeping indexes in an array
) that point to the next index and the previous index and sort the index
) values based on some data in their data portion of the array...

<snip>

) To sum everything up... Is there a feasible way to keep track of these
) indexes and sort the indexes instead of sorting the actual data?

Your data structure, as described, is close enough to an actual linked list
that you can simply treat it as such.  You can use any standard sort that
works with linked lists, such as mergesort, insertion sort or whatnot.

Mergesort would actually be quite easy, as it's very suited to a
linked list structure.  A very simple recursive function would suffice.


SaSW, Willem
-- 
Disclaimer: I am in no way responsible for any of the statements
            made in the above text. For all I know I might be
            drugged or something..
            No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

.