HPSORT(3)

SYNOPSIS
SUBROUTINE HPSORT (HX, N, STRBEG, STREND, IPERM, KFLAG, WORK, IER)

NAME
hpsort - Return the permutation vector generated by sorting a substring within a character array and, optionally, rearrange the elements of the array. The array may be sorted in forward or reverse lexicographical order. A slightly modified quicksort algorithm is used.

LIBRARY
SLATEC

CATEGORY
N6A1C, N6A2C

TYPE
CHARACTER (SPSORT-S, DPSORT-D, IPSORT-I, HPSORT-H)

KEYWORDS
PASSIVE SORTING, SINGLETON QUICKSORT, SORT, STRING SORTING

AUTHOR
Jones, R. E., (SNLA) Rhoads, G. S., (NBS) Sullivan, F. E., (NBS) Wisniewski, J. A., (SNLA)

DESCRIPTION
HPSORT returns the permutation vector IPERM generated by sorting the substrings beginning with the character STRBEG and ending with the character STREND within the strings in array HX and, optionally, rearranges the strings in HX. HX may be sorted in increasing or decreasing lexicographical order. A slightly modified quicksort algorithm is used. IPERM is such that HX(IPERM(I)) is the Ith value in the rearrangement of HX. IPERM may be applied to another array by calling IPPERM, SPPERM, DPPERM or HPPERM. An active sort of numerical data is expected to execute somewhat more quickly than a passive sort because there is no need to use indirect references. But for the character data in HPSORT, integers in the IPERM vector are manipulated rather than the strings in HX. Moving integers may be enough faster than moving character strings to more than offset the penalty of indirect referencing. Description of Parameters HX - input/output -- array of type character to be sorted. For example, to sort a 80 element array of names, each of length 6, declare HX as character HX(100)*6. If ABS(KFLAG) = 2, then the values in HX will be rearranged on output; otherwise, they are unchanged. N - input -- number of values in array HX to be sorted. STRBEG - input -- the index of the initial character in the string HX that is to be sorted. STREND - input -- the index of the final character in the string HX that is to be sorted. IPERM - output -- permutation array such that IPERM(I) is the index of the string in the original order of the HX array that is in the Ith location in the sorted order. KFLAG - input -- control parameter: = 2 means return the permutation vector resulting from sorting HX in lexicographical order and sort HX also. = 1 means return the permutation vector resulting from sorting HX in lexicographical order and do not sort HX. = -1 means return the permutation vector resulting from sorting HX in reverse lexicographical order and do not sort HX. = -2 means return the permutation vector resulting from sorting HX in reverse lexicographical order and sort HX also. WORK - character variable which must have a length specification at least as great as that of HX. IER - output -- error indicator: = 0 if no error, = 1 if N is zero or negative, = 2 if KFLAG is not 2, 1, -1, or -2, = 3 if work array is not long enough, = 4 if string beginning is beyond its end, = 5 if string beginning is out-of-range, = 6 if string end is out-of-range. E X A M P L E O F U S E CHARACTER*2 HX, W INTEGER STRBEG, STREND DIMENSION HX(10), IPERM(10) DATA (HX(I),I=1,10)/ '05','I ',' I',' ','Rs','9R','R9','89', 1 ',*','N"'/ DATA STRBEG, STREND / 1, 2 / CALL HPSORT (HX,10,STRBEG,STREND,IPERM,1,W) PRINT 100, (HX(IPERM(I)),I=1,10) 100 FORMAT (2X, A2) STOP END

REFERENCES
R. C. Singleton, Algorithm 347, An efficient algorithm for sorting with minimal storage, Communications of the ACM, 12, 3 (1969), pp. 185-187.

ROUTINES CALLED
XERMSG

REVISION HISTORY (YYMMDD)
761101 DATE WRITTEN
761118 Modified by John A. Wisniewski to use the Singleton quicksort algorithm.
811001 Modified by Francis Sullivan for string data.
850326 Documentation slightly modified by D. Kahaner.
870423 Modified by Gregory S. Rhoads for passive sorting with the option for the rearrangement of the original data.
890620 Algorithm for rearranging the data vector corrected by R. Boisvert.
890622 Prologue upgraded to Version 4.0 style by D. Lozier.
920507 Modified by M. McClain to revise prologue text.
920818 Declarations section rebuilt and code restructured to use IF-THEN-ELSE-ENDIF. (SMR, WRB)