m01cu: FL CL CPP AD

NAG CL Interface
m01cuc (chain_sort)

Keyword Search:

NAG Library Manual, Mark 27.3

Interfaces: FL CL CPP AD

NAG CL Interface Introduction

M01 (Sort) Chapter Contents

M01 (Sort) Chapter Introduction

m01cu: FL CL CPP AD

▸▿ Contents

1 Purpose

2 Specification

3 Description

4 References

5 Arguments

6 Error Indicators and Warnings

7 Accuracy

8 Parallelism and Performance

9 Further Comments

▸▿ 10 Example

10.1 Program Text

10.2 Program Data

10.3 Program Results

Settings help

CL Name Style:
Short (a00aac)
Long (impl_details)
Full (nag_info_impl_details)

1 Purpose

m01cuc rearranges the links of a linked list into ascending or descending order of a specified data field of arbitrary type.

2 Specification

#include <nag.h>

void

m01cuc (Pointer *base, ptrdiff_t offset,

Integer

(*compare)(const Nag_Pointer a, const Nag_Pointer b),

Nag_SortOrder order, NagError *fail)

The function may be called by the names: m01cuc, nag_sort_chain_sort or nag_chain_sort.

3 Description

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.

4 References

Knuth D E (1973) The Art of Computer Programming (Volume 3) (2nd Edition) Addison–Wesley

5 Arguments

1: $base$ – Pointer * Input/Output

On entry: the pointer to the pointer to the first structure of the linked list.

On exit: the pointer to which base points is updated to point to the first element of the ordered list.

2: $offset$ – ptrdiff_t Input

On entry: 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.

3: $compare$ – function, supplied by the user External Function

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:

$−1$	if the first data field is less than the second,
$0$	if the first data field is equal to the second,
$1$	if the first data field is greater than the second.

The specification of compare is:

Integer

compare (const Nag_Pointer a, const Nag_Pointer b)

1: $a$ – const Nag_Pointer Input: On entry: the first data field.
2: $b$ – const Nag_Pointer Input: On entry: the second data field.

4: $order$ – Nag_SortOrder Input

On entry: specifies whether the array will be sorted into ascending or descending order.

Constraint:

order = Nag_Ascending

Nag_Descending

5: $fail$ – NagError * Input/Output

The NAG error argument (see Section 7 in the Introduction to the NAG Library CL Interface).

6 Error Indicators and Warnings

NE_BAD_PARAM: On entry, order had an illegal value.
NE_CH_LOOP: Too many elements in chain or chain in a loop. The linked list may have become corrupted.

7 Accuracy

Not applicable.

8 Parallelism and Performance

m01cuc is not threaded in any implementation.

9 Further Comments

The time taken by m01cuc is approximately proportional to

n \log (n)

10 Example

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.