Module ppm_module_util_qsort

This module provides the utility quicksort routines.

Defined Types

name description

no types

Defined Module Interfaces

name description

ppm_util_qsort

Defined Module Subroutines

name description

no subroutines

Interface ppm_util_qsort

Subroutines contained in this interface:

name description

ppm_util_qsort_s

From a list of values generates a sort permutation list

ppm_util_qsort_d

From a list of values generates a sort permutation list

ppm_util_qsort_i

From a list of values generates a sort permutation list

Subroutine ppm_util_qsort_d

From a list of values generates a sort permutation list

[Note]Note

From Leonard J. Moss of SLAC: Here is a hybrid QuickSort I wrote a number of i years ago. It is based on suggestions in Knuth, Volume 3, and performs much better than a pure QuickSort on short or partially ordered input arrays. SORTRX uses a hybrid QuickSort algorithm, based on several suggestions in Knuth, Volume 3, Section 5.2.2. In particular, the pivot key [my term] for dividing each subsequence is chosen to be the median of the i first, last, and middle values of the subsequence; and the QuickSort is cut off when a subsequence has 9 or fewer elements, and a straight insertion sort of the entire array is done at the end. The result is comparable to a pure insertion sort for very short arrays, and very fast for very large arrays (of order 12 micro-sec/element on the 3081K for arrays of 10K elements). It is also not subject to the poor performance of the pure QuickSort on partially ordered data.

Arguments

name type dimension intent optional description

inlist

real array

(:)

List to be sorted

outlist

integer array

(:)

Permutation list

info

integer

(OUT)

Return status, 0 on success

inlist

real array, (:), no intent declared

List to be sorted

outlist

integer array, (:), no intent declared

Permutation list

info

integer, , (OUT)

Return status, 0 on success

Used Modules

ppm_module_data, ppm_module_alloc, ppm_module_error, ppm_module_substop, ppm_module_substart

Subroutine ppm_util_qsort_i

From a list of values generates a sort permutation list

[Note]Note

From Leonard J. Moss of SLAC: Here is a hybrid QuickSort I wrote a number of i years ago. It is based on suggestions in Knuth, Volume 3, and performs much better than a pure QuickSort on short or partially ordered input arrays. SORTRX uses a hybrid QuickSort algorithm, based on several suggestions in Knuth, Volume 3, Section 5.2.2. In particular, the pivot key [my term] for dividing each subsequence is chosen to be the median of the i first, last, and middle values of the subsequence; and the QuickSort is cut off when a subsequence has 9 or fewer elements, and a straight insertion sort of the entire array is done at the end. The result is comparable to a pure insertion sort for very short arrays, and very fast for very large arrays (of order 12 micro-sec/element on the 3081K for arrays of 10K elements). It is also not subject to the poor performance of the pure QuickSort on partially ordered data.

Arguments

name type dimension intent optional description

inlist

integer array

(:)

List to be sorted

outlist

integer array

(:)

Permutation list

info

integer

(OUT)

Return status, 0 on success

inlist

integer array, (:), no intent declared

List to be sorted

outlist

integer array, (:), no intent declared

Permutation list

info

integer, , (OUT)

Return status, 0 on success

Used Modules

ppm_module_data, ppm_module_alloc, ppm_module_error, ppm_module_substop, ppm_module_substart

Subroutine ppm_util_qsort_s

From a list of values generates a sort permutation list

[Note]Note

From Leonard J. Moss of SLAC: Here is a hybrid QuickSort I wrote a number of i years ago. It is based on suggestions in Knuth, Volume 3, and performs much better than a pure QuickSort on short or partially ordered input arrays. SORTRX uses a hybrid QuickSort algorithm, based on several suggestions in Knuth, Volume 3, Section 5.2.2. In particular, the pivot key [my term] for dividing each subsequence is chosen to be the median of the i first, last, and middle values of the subsequence; and the QuickSort is cut off when a subsequence has 9 or fewer elements, and a straight insertion sort of the entire array is done at the end. The result is comparable to a pure insertion sort for very short arrays, and very fast for very large arrays (of order 12 micro-sec/element on the 3081K for arrays of 10K elements). It is also not subject to the poor performance of the pure QuickSort on partially ordered data.

Arguments

name type dimension intent optional description

inlist

real array

(:)

List to be sorted

outlist

integer array

(:)

Permutation list

info

integer

(OUT)

Return status, 0 on success

inlist

real array, (:), no intent declared

List to be sorted

outlist

integer array, (:), no intent declared

Permutation list

info

integer, , (OUT)

Return status, 0 on success

Used Modules

ppm_module_data, ppm_module_alloc, ppm_module_error, ppm_module_substop, ppm_module_substart

Defined Module Variables

name type dimension description

no variables

Used Modules

has no uses