Subj : "Faking a linked list" using arrays and sorting that list using an insertion sort...
To   : comp.programming
From : Kosio
Date : Tue Oct 04 2005 03:06 pm

-Hello,

   This would probably be classified as a data structures question...

   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.

   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...

I hope I'm being clear, it's kind of hard to describe my problem.  To
clarify, perhaps I could produce an example:

I have 100 items in my record.  I will sort based on the 50th item in
the record.

For simplicity sake, say I'm sorting 5 records (I plan on sorting
more), my array would look something like this.

string records[5][102]

Element 0 of the second index represents the previous spot in the list
(if there is a -1, then it means it's the beginning of the list.
Element 1 of the second index represents the next spot in the list (if
there is a -1, then it means it's the end of the list).  Assume I will
convert the first two elements of the second index to integers, and all
of the rest of the data (elements 2 through 101) will be strings on
which I will sort my data.

#define PREV 0
#define NEXT 1

records[0][PREV] = -1
records[0][NEXT] = 1
records[1][PREV] = 0
records[1][NEXT] = 2
records[2][PREV] = 1
records[2][NEXT] = 3
records[3][PREV] = 2
records[3][NEXT] = 4
records[4][PREV] = 3
records[4][NEXT] = -1

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?

Thanks,
Aaron

.