NAG Library Function Document
nag_chain_sort (m01cuc) rearranges the links of a linked list into ascending or descending order of a specified data field of arbitrary type.
||nag_chain_sort (Pointer *base,
(*compare)(const Nag_Pointer a,
const Nag_Pointer b),
nag_chain_sort (m01cuc) uses a variant of list merging, as described in Knuth (1973)
. It uses a local stack to avoid the need for a flag bit in each pointer.
Knuth D E (1973) The Art of Computer Programming (Volume 3) (2nd Edition) Addison–Wesley
– Pointer *Input/Output
On entry: the pointer to the pointer to the first structure of the linked list.
: the pointer to which base
points is updated to point to the first element of the ordered list.
: the offset within the structure of the pointer field which points to the next element of the linked list.
Note: this field in the last element of the linked list must have the value NULL.
– function, supplied by the userExternal Function
nag_chain_sort (m01cuc) compares the data fields of two elements of the list. Its arguments are pointers to the structure, therefore this function must allow for the offset of the data field in the structure (if it is not the first).
The function must return:
||if the first data field is less than the second,
||if the first data field is equal to the second,
||if the first data field is greater than the second.
The specification of compare
compare (const Nag_Pointer a,
const Nag_Pointer b)
– const Nag_Pointer Input
On entry: the first data field.
– const Nag_Pointer Input
On entry: the second data field.
On entry: specifies whether the array will be sorted into ascending or descending order.
– NagError *Input/Output
The NAG error argument (see Section 3.6
in the Essential Introduction).
6 Error Indicators and Warnings
On entry, order
had an illegal value.
Too many elements in chain or chain in a loop. The linked list may have become corrupted.
8 Parallelism and Performance
The time taken by nag_chain_sort (m01cuc) is approximately proportional to .
The example program declares a structure containing a data field, a pointer to the next record and an index field. It generates an array of such structures assigning random data to the data field. The index field is randomly assigned a unique value. The pointer to next record fields are assigned to create a linked list in the order of the index field. It sorts this linked list into ascending order according to the value of the data field.
10.1 Program Text
Program Text (m01cuce.c)
10.2 Program Data
10.3 Program Results
Program Results (m01cuce.r)