-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

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

"Kosio" <aarongeier@gmail.com> wrote in message 
news:1128459997.492096.234950@g44g2000cwa.googlegroups.com...
> -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.
.... [C code skipped]
>
> 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?

Yes, use an array of pointers to your records, and use the library qsort 
routine to sort the array.

record* array[RECORDS];

int sortfunc(const void* p, const void* q)
{
   return (*(record **)p)->field50 - (*(record **)q)->field50;
}

qsort(array, RECORDS, sizeof(record *), sortfunc);

--
Roger


 

Using indices instead of pointers is not "faking" at all.  Lots of new
students of data structures are surprised to learn that all the linked
list algorithms they are learning can be implemented just as easily by
allocating records from an array and using indices in place of
pointers.  In fact, when early FORTRAN was king, that's how _all_
linked structure algorithms (lists, trees, graphs, ...) were
implemented.

In fact, when memory was more expensive, using 2-byte indices in place
of 4-byte pointers was a popular way to save space.  GCC once used this
trick.  Of course it fails if you have more than 64K records to
address.

The algorithm you are proposing is just sorting a linked list.  You are
using indices instead of pointers, but any algorithm that works for one
will work for the other.  Mergesort is often used for this purpose.
It's a natural!  It's less well known that Quicksort translates nicely
to a linked list version.  Double links are not required for either
algorithm.  In fact it's easiest to sort using only "next" links and
then fix up the "prev" links at the end if they're needed for some
other purpose.  And of course insertion sort works fine with a linked
list, although the code looks a tad different than the array version.
Write a routine that inserts a single element in the correct position
of a list that's already sorted.  Now just pop elements one-by-one off
the original list and insert them into an (initially empty) sorted one.

Finally, the other writers are absolutely correct.  You are killing a
fly with a sledgehammer.  If all you are trying to do is avoid copying,
forget the linked list approach. Just make an array of pointers or
indices and sort those while using them to refer to the record keys for
comparisons.

Thanks for the response and information, it's appreciated!