C Library Functions - sortc (3)
NAME
sortc(3f) - [M_datapac:SORT] sort a vector of sample observations and "carry" a second vector
CONTENTS
Synopsis
Description
Input Arguments
Output Arguments
Examples
Author
Maintainer
References
License
SYNOPSIS
Subroutine sortc(X,Y,N,Xs,Yc)
Real(kind=wp), Intent (In) :: X Real(kind=wp), Intent (In) :: Y Integer, Intent (In) :: N Real(kind=wp), Intent (Out) :: Xs Real(kind=wp), Intent (Out) :: Yc
DESCRIPTION
SORTC(3f) sorts (in ascending order) the N elements of the vector X, puts the resulting N sorted values into the vector XS, rearranges the elements of the vector Y (according to the sort on X), and puts the rearranged Y values into the vector YC. This subroutine gives the data analyst the ability to sort one data vector while ’carrying along’ the elements of a second data vector.
The smallest element of the vector X will be placed in the first position of the vector XS, the second smallest element in the vector X will be placed in the second position of the vector XS, etc.
The element in the vector Y corresponding to the smallest element in X will be placed in the first position of the vector YC, the element in the vector Y corresponding to the second smallest element in X will be placed in the second position of the vector YC, etc.
The input vector X remains unaltered.
If the analyst desires a sort ’in place’, this is done by having the same output vector as input vector in the calling sequence. Thus, for example, the calling sequence CALL SORTC(X,Y,N,X,YC) is allowable and will result in the desired ’in-place’ sort.
The sorting algorithm used herein is the binary sort. This algorithm is extremely fast as the following time trials indicate. These time trials were carried out on the UNIVAC 1108 EXEC 8 system at NBS in August of 1974. By way of comparison, the time trial values for the easy-to-program but extremely inefficient bubble sort algorithm have also been included--
Number of Random Binary Sort Bubble Sort Numbers Sorted N = 10 .002 sec .002 sec N = 100 .011 sec .045 sec N = 1000 .141 sec 4.332 sec N = 3000 .476 sec 37.683 sec N = 10000 1.887 sec NOT COMPUTED
INPUT ARGUMENTS
X The vector of observations to be sorted. Y The vector of observations to be ’carried along’, that is, to be rearranged according to the sort on X. N The integer number of observations in the vector X.
OUTPUT ARGUMENTS
XS The vector into which the sorted data values from X will be placed in ascending order. YC The vector into which the rearranged (according to the sort of the vector X) values of the vector Y will be placed.
EXAMPLES
Sample program:
program demo_sortc use M_datapac, only : sortc, label implicit none integer,parameter :: isz=20 real :: aa(isz) real :: bb(isz) real :: cc(isz) real :: dd(isz) integer :: i call label(’sortc’) write(*,*)’initializing array with ’,isz,’ random numbers’ call random_seed() CALL RANDOM_NUMBER(aa) aa=aa*450000.0 bb=real([(i,i=1,isz)]) call sortc(aa,bb,size(aa),cc,dd)Results:write(*,*)’checking if real values are sorted(3f)’ do i=1,isz-1 if(cc(i).gt.cc(i+1))then write(*,*)’Error in sorting reals small to large ’,i,cc(i),cc(i+1) endif enddo write(*,*)’test of sortc(3f) complete’ write(*,’(4(g0,1x))’)(aa(i),bb(i),cc(i),dd(i),i=1,isz) write(*,’(*(g0,1x))’)sum(aa),sum(cc) ! should be the same if no truncation write(*,’(*(g0,1x))’)sum(bb),sum(dd)
end program demo_sortc
AUTHOR
The original DATAPAC library was written by James Filliben of the Statistical Engineering Division, National Institute of Standards and Technology.
MAINTAINER
John Urban, 2022.05.31
REFERENCES
1. CACM MARCH 1969, page 186 (BINARY SORT ALGORITHM BY RICHARD C. SINGLETON). 2. CACM JANUARY 1970, page 54. 3. CACM OCTOBER 1970, page 624. 4. JACM JANUARY 1961, page 41.
LICENSE
CC0-1.0
| Nemo Release 3.1 | sortc (3) | July 22, 2023 |
