0.6.2-dev0
 |
FORCES
FORtran lib for Comp. Env. Sys.
|
|
FORCES
FORtran lib for Comp. Env. Sys.
|
Sort and ranking routines. More...
Go to the source code of this file.
Data Types | |
| interface | mo_orderpack::sort |
| Sorts the input array in ascending order. More... | |
| interface | mo_orderpack::sort_index |
| Gives the indeces that would sort an array in ascending order. More... | |
| interface | mo_orderpack::ctrper |
| Random permutation ranking. More... | |
| interface | mo_orderpack::fndnth |
| Find N-th value in array from insertion sort. More... | |
| interface | mo_orderpack::indmed |
| Median index of skewed-pivot with quicksort ranking. More... | |
| interface | mo_orderpack::indnth |
| Nth index of skewed-pivot with quicksort ranking. More... | |
| interface | mo_orderpack::inspar |
| Partial insertion sort ranking,. More... | |
| interface | mo_orderpack::inssor |
| Insertion sort ranking. More... | |
| interface | mo_orderpack::omedian |
| Find median value of array (case for even elements) More... | |
| interface | mo_orderpack::mrgref |
| Merge-sort ranking (unoptimized) More... | |
| interface | mo_orderpack::mrgrnk |
| Merge-sort ranking. More... | |
| interface | mo_orderpack::mulcnt |
| Multiplicity of array values. More... | |
| interface | mo_orderpack::rapknr |
| Skewed-pivot with quicksort ranking (reversed). More... | |
| interface | mo_orderpack::refpar |
| Skewed-pivot with quicksort ranking (unoptimized). More... | |
| interface | mo_orderpack::refsor |
| Quicksort ranking, with insertion sort at last step (unoptimized) More... | |
| interface | mo_orderpack::rinpar |
| Insertion sort ranking (unoptimized). More... | |
| interface | mo_orderpack::rnkpar |
| Skewed-pivot with quicksort ranking. More... | |
| interface | mo_orderpack::uniinv |
| Merge-sort ranking, with removal of duplicate entries (reversed). More... | |
| interface | mo_orderpack::nearless |
| interface | mo_orderpack::unipar |
| Partial quicksort/insertion sort ranking, with removal of duplicate entries. More... | |
| interface | mo_orderpack::unirnk |
| Merge-sort ranking, with removal of duplicate entries. More... | |
| interface | mo_orderpack::unista |
| Merge-sort unique inverse ranking. More... | |
| interface | mo_orderpack::valmed |
| Find median value of array. More... | |
| interface | mo_orderpack::valnth |
| Find N-th value in array from quicksort. More... | |
Modules | |
| module | mo_orderpack |
| Sort and ranking routines. | |
Functions/Subroutines | |
| integer(i4) function, dimension(size(arr)) | mo_orderpack::sort_index_dp (arr) |
| integer(i4) function, dimension(size(arr)) | mo_orderpack::sort_index_sp (arr) |
| integer(i4) function, dimension(size(arr)) | mo_orderpack::sort_index_i4 (arr) |
| subroutine, private | mo_orderpack::d_ctrper (xdont, pcls) |
| subroutine, private | mo_orderpack::r_ctrper (xdont, pcls) |
| subroutine, private | mo_orderpack::i_ctrper (xdont, pcls) |
| real(kind=dp) function, private | mo_orderpack::d_fndnth (xdont, nord) |
| real(kind=sp) function, private | mo_orderpack::r_fndnth (xdont, nord) |
| integer(kind=i4) function, private | mo_orderpack::i_fndnth (xdont, nord) |
| subroutine, private | mo_orderpack::d_indmed (xdont, indm) |
| recursive subroutine, private | mo_orderpack::d_med (xdatt, idatt, ires_med) |
| subroutine, private | mo_orderpack::r_indmed (xdont, indm) |
| recursive subroutine, private | mo_orderpack::r_med (xdatt, idatt, ires_med) |
| subroutine, private | mo_orderpack::i_indmed (xdont, indm) |
| recursive subroutine, private | mo_orderpack::i_med (xdatt, idatt, ires_med) |
| integer(kind=i4) function, private | mo_orderpack::d_indnth (xdont, nord) |
| integer(kind=i4) function, private | mo_orderpack::r_indnth (xdont, nord) |
| integer(kind=i4) function, private | mo_orderpack::i_indnth (xdont, nord) |
| subroutine, private | mo_orderpack::d_inspar (xdont, nord) |
| subroutine, private | mo_orderpack::r_inspar (xdont, nord) |
| subroutine, private | mo_orderpack::i_inspar (xdont, nord) |
| subroutine, private | mo_orderpack::d_inssor (xdont) |
| subroutine, private | mo_orderpack::r_inssor (xdont) |
| subroutine, private | mo_orderpack::i_inssor (xdont) |
| subroutine, private | mo_orderpack::c_inssor (xdont) |
| real(kind=dp) function, private | mo_orderpack::d_median (xdont) |
| real(kind=sp) function, private | mo_orderpack::r_median (xdont) |
| integer(kind=i4) function, private | mo_orderpack::i_median (xdont) |
| subroutine, private | mo_orderpack::d_mrgref (xvalt, irngt) |
| subroutine, private | mo_orderpack::r_mrgref (xvalt, irngt) |
| subroutine, private | mo_orderpack::i_mrgref (xvalt, irngt) |
| subroutine, private | mo_orderpack::d_mrgrnk (xdont, irngt) |
| subroutine, private | mo_orderpack::r_mrgrnk (xdont, irngt) |
| subroutine, private | mo_orderpack::i_mrgrnk (xdont, irngt) |
| subroutine | mo_orderpack::c_mrgrnk (xdont, irngt) |
| subroutine, private | mo_orderpack::d_mulcnt (xdont, imult) |
| subroutine, private | mo_orderpack::r_mulcnt (xdont, imult) |
| subroutine, private | mo_orderpack::i_mulcnt (xdont, imult) |
| subroutine, private | mo_orderpack::d_rapknr (xdont, irngt, nord) |
| subroutine, private | mo_orderpack::r_rapknr (xdont, irngt, nord) |
| subroutine, private | mo_orderpack::i_rapknr (xdont, irngt, nord) |
| subroutine, private | mo_orderpack::d_refpar (xdont, irngt, nord) |
| subroutine, private | mo_orderpack::r_refpar (xdont, irngt, nord) |
| subroutine, private | mo_orderpack::i_refpar (xdont, irngt, nord) |
| subroutine, private | mo_orderpack::d_refsor (xdont) |
| recursive subroutine, private | mo_orderpack::d_subsor (xdont, ideb1, ifin1) |
| subroutine, private | mo_orderpack::r_refsor (xdont) |
| recursive subroutine, private | mo_orderpack::r_subsor (xdont, ideb1, ifin1) |
| subroutine, private | mo_orderpack::i_refsor (xdont) |
| recursive subroutine, private | mo_orderpack::i_subsor (xdont, ideb1, ifin1) |
| subroutine, private | mo_orderpack::c_refsor (xdont) |
| recursive subroutine, private | mo_orderpack::c_subsor (xdont, ideb1, ifin1) |
| subroutine, private | mo_orderpack::d_rinpar (xdont, irngt, nord) |
| subroutine, private | mo_orderpack::r_rinpar (xdont, irngt, nord) |
| subroutine, private | mo_orderpack::i_rinpar (xdont, irngt, nord) |
| subroutine, private | mo_orderpack::d_rnkpar (xdont, irngt, nord) |
| subroutine, private | mo_orderpack::r_rnkpar (xdont, irngt, nord) |
| subroutine, private | mo_orderpack::i_rnkpar (xdont, irngt, nord) |
| subroutine, private | mo_orderpack::d_uniinv (xdont, igoest) |
| subroutine, private | mo_orderpack::r_uniinv (xdont, igoest) |
| subroutine, private | mo_orderpack::i_uniinv (xdont, igoest) |
| real(kind=dp) function, private | mo_orderpack::d_nearless (xval) |
| real(kind=sp) function, private | mo_orderpack::r_nearless (xval) |
| integer(kind=i4) function, private | mo_orderpack::i_nearless (xval) |
| subroutine, private | mo_orderpack::d_unipar (xdont, irngt, nord) |
| subroutine, private | mo_orderpack::r_unipar (xdont, irngt, nord) |
| subroutine, private | mo_orderpack::i_unipar (xdont, irngt, nord) |
| subroutine, private | mo_orderpack::d_unirnk (xvalt, irngt, nuni) |
| subroutine, private | mo_orderpack::r_unirnk (xvalt, irngt, nuni) |
| subroutine, private | mo_orderpack::i_unirnk (xvalt, irngt, nuni) |
| subroutine, private | mo_orderpack::d_unista (xdont, nuni) |
| subroutine, private | mo_orderpack::r_unista (xdont, nuni) |
| subroutine, private | mo_orderpack::i_unista (xdont, nuni) |
| recursive real(kind=dp) function, private | mo_orderpack::d_valmed (xdont) |
| recursive real(kind=sp) function, private | mo_orderpack::r_valmed (xdont) |
| recursive integer(kind=i4) function, private | mo_orderpack::i_valmed (xdont) |
| real(kind=dp) function, private | mo_orderpack::d_valnth (xdont, nord) |
| real(kind=sp) function, private | mo_orderpack::r_valnth (xdont, nord) |
| integer(kind=i4) function, private | mo_orderpack::i_valnth (xdont, nord) |
Variables | |
| integer(kind=i4), dimension(:), allocatable, save | mo_orderpack::idont |
Sort and ranking routines.
This module is the Orderpack 2.0 from Michel Olagnon. It provides order and unconditional, unique, and partial ranking, sorting, and permutation.
Unconditional ranking
Ranks array XVALT into index array IRNGT, using merge-sort. For performance reasons, the first 2 passes are taken out of the standard loop, and use dedicated coding.
Ranks array XVALT into index array IRNGT, using merge-sort. This version is not optimized for performance, and is thus not as difficult to read as the previous one.
Partial ranking
Ranks partially XVALT by IRNGT, up to order NORD (refined for speed). This routine uses a pivoting strategy such as the one of finding the median based on the quicksort algorithm, but we skew the pivot choice to try to bring it to NORD as fast as possible. It uses 2 temporary arrays, one where it stores the indices of the values smaller than the pivot, and the other for the indices of values larger than the pivot that we might still need later on. It iterates until it can bring the number of values in ILOWT to exactly NORD, and then uses an insertion sort to rank this set, since it is supposedly small.
Same as RNKPAR, but in decreasing order (RAPKNR = RNKPAR spelt backwards).
Ranks partially XVALT by IRNGT, up to order NORD This version is not optimized for performance, and is thus not as difficult to read as some other ones. It uses a pivoting strategy such as the one of finding the median based on the quicksort algorithm. It uses a temporary array, where it stores the partially ranked indices of the values. It iterates until it can bring the number of values lower than the pivot to exactly NORD, and then uses an insertion sort to rank this set, since it is supposedly small.
Ranks partially XVALT by IRNGT, up to order NORD This version is not optimized for performance, and is thus not as difficult to read as some other ones. It uses insertion sort, limiting insertion to the first NORD values. It does not use any work array and is faster when NORD is very small (2-5), but worst case behavior (intially inverse sorted) can easily happen. In many cases, the refined quicksort method is faster.
Returns the index of the NORDth value of XVALT (in increasing order) This routine uses a pivoting strategy such as the one of finding the median based on the quicksort algorithm, but we skew the pivot choice to try to bring it to NORD as fast as possible. It uses 2 temporary arrays, one where it stores the indices of the values smaller than the pivot, and the other for the indices of values larger than the pivot that we might still need later on. It iterates until it can bring the number of values in ILOWT to exactly NORD, and then takes out the original index of the maximum value in this set.
Returns the index of the median (((Size(XVALT)+1))/2th value) of XVALT This routine uses the recursive procedure described in Knuth, The Art of Computer Programming, vol. 3, 5.3.3 - This procedure is linear in time, and does not require to be able to interpolate in the set as the one used in INDNTH. It also has better worst case behavior than INDNTH, but is about 10% slower in average for random uniformly distributed values.
Note that in Orderpack 1.0, this routine was a Function procedure, and is now changed to a Subroutine.
Unique ranking
Ranks an array, removing duplicate entries (uses merge sort). The routine is similar to pure merge-sort ranking, but on the last pass, it discards indices that correspond to duplicate entries. For performance reasons, the first 2 passes are taken out of the standard loop, and use dedicated coding.
Ranks partially XVALT by IRNGT, up to order NORD at most, removing duplicate entries This routine uses a pivoting strategy such as the one of finding the median based on the quicksort algorithm, but we skew the pivot choice to try to bring it to NORD as quickly as possible. It uses 2 temporary arrays, one where it stores the indices of the values smaller than the pivot, and the other for the indices of values larger than the pivot that we might still need later on. It iterates until it can bring the number of values in ILOWT to exactly NORD, and then uses an insertion sort to rank this set, since it is supposedly small. At all times, the NORD first values in ILOWT correspond to distinct values of the input array.
Inverse ranking of an array, with removal of duplicate entries The routine is similar to pure merge-sort ranking, but on the last pass, it sets indices in IGOEST to the rank of the original value in an ordered set with duplicates removed. For performance reasons, the first 2 passes are taken out of the standard loop, and use dedicated coding.
Gives, for each array value, its multiplicity The number of times that a value appears in the array is computed by using inverse ranking, counting for each rank the number of values that `‘collide’' to this rank, and returning this sum to the locations in the original set. Uses subroutine UNIINV.
Random permutation: an interesting use of ranking
A variation of the following problem was raised on the internet sci.math.num-analysis news group: Given an array, I would like to find a random permutation of this array that I could control with a "nearbyness" parameter so that elements stay close to their initial locations. The "nearbyness" parameter ranges from 0 to 1, with 0 such that no element moves from its initial location, and 1 such that the permutation is fully random.
Permute array XVALT randomly, but leaving elements close to their initial locations The routine takes the 1...size(XVALT) index array as real values, takes a combination of these values and of random values as a perturbation of the index array, and sorts the initial set according to the ranks of these perturbated indices. The relative proportion of initial order and random order is 1-PCLS / PCLS, thus when PCLS = 0, there is no change in the order whereas the new order is fully random when PCLS = 1. Uses subroutine MRGRNK.
The above solution found another application when I was asked the following question: I am given two arrays, representing parents' incomes and their children's incomes, but I do not know which parents correspond to which children. I know from an independent source the value of the correlation coefficient between the incomes of the parents and of their children. I would like to pair the elements of these arrays so that the given correlation coefficient is attained, i.e. to reconstruct a realistic dataset, though very likely not to be the true one.
Given two arrays of equal length of unordered values, find a "matching value" in the second array for each value in the first so that the global correlation coefficient reaches exactly a given target The routine first sorts the two arrays, so as to get the match of maximum possible correlation. It then iterates, applying the random permutation algorithm of controlled disorder ctrper to the second array. When the resulting correlation goes beyond (lower than) the target correlation, one steps back and reduces the disorder parameter of the permutation. When the resulting correlation lies between the current one and the target, one replaces the array with the newly permuted one. When the resulting correlation increases from the current value, one increases the disorder parameter. That way, the target correlation is approached from above, by a controlled increase in randomness. Since full randomness leads to zero correlation, the iterations meet the desired coefficient at some point. It may be noted that there could be some cases when one would get stuck in a sort of local minimum, where local perturbations cannot further reduce the correlation and where global ones lead to overpass the target. It seems easier to restart the program with a different seed when this occurs than to design an avoidance scheme. Also, should a negative correlation be desired, the program should be modified to start with one array in reverse order with respect to the other, i.e. coorelation as close to -1 as possible.
Full sorting
Sorts XVALT into increasing order (Insertion sort) This subroutine uses insertion sort. It does not use any work array and is faster when XVALT is of very small size (< 20), or already almost sorted, but worst case behavior (intially inverse sorted) can easily happen. In most cases, the quicksort or merge sort method is faster.
Sorts XVALT into increasing order (Quick sort) This version is not optimized for performance, and is thus not as difficult to read as some other ones. This subroutine uses quicksort in a recursive implementation, and insertion sort for the last steps with small subsets. It does not use any work array
Partial sorting
Sorts partially XVALT, bringing the NORD lowest values at the begining of the array. This subroutine uses insertion sort, limiting insertion to the first NORD values. It does not use any work array and is faster when NORD is very small (2-5), but worst case behavior can happen fairly probably (initially inverse sorted). In many cases, the refined quicksort method is faster.
Finds out and returns the NORDth value in XVALT (ascending order) This subroutine uses insertion sort, limiting insertion to the first NORD values, and even less when one can know that the value that is considered will not be the NORDth. It uses only a work array of size NORD and is faster when NORD is very small (2-5), but worst case behavior can happen fairly probably (initially inverse sorted). In many cases, the refined quicksort method implemented by VALNTH / INDNTH is faster, though much more difficult to read and understand.
Finds out and returns the NORDth value in XVALT (ascending order) This subroutine simply calls INDNTH.
Finds out and returns the median(((Size(XVALT)+1))/2th value) of XVALT This routine uses the recursive procedure described in Knuth, The Art of Computer Programming, vol. 3, 5.3.3 - This procedure is linear in time, and does not require to be able to interpolate in the set as the one used in VALNTH/INDNTH. It also has better worst case behavior than VALNTH/INDNTH, and is about 20% faster in average for random uniformly distributed values.
It is a modified version of VALMED that provides the average between the two middle values in the case Size(XVALT) is even.
Unique sorting
Removes duplicates from an array This subroutine uses merge sort unique inverse ranking. It leaves in the initial set only those entries that are unique, packing the array, and leaving the order of the retained values unchanged.
COPYING and COPYING.LESSER provided with this software. The complete GNU license text can also be found at http://www.gnu.org/licenses/. Definition in file mo_orderpack.f90.
1.9.7