Subj : Re: "Faking a linked list" using arrays and sorting that list using an insertion sort...
To   : comp.programming
From : Roger Willcocks
Date : Wed Oct 05 2005 12:41 am


"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

.