NAME
M_sort(3fm) - [M_sort::INTRO] Fortran module containing sorting
algorithms for arrays of standard scalar types
(LICENSE:PD)
SYNOPSIS
use M_sort, only : sort_quick_rx, sort_quick_compact
use M_sort, only : sort_shell, sort_heap
use M_sort, only : unique
DESCRIPTION
Under development. Currently only provides a few common routines,
but it is intended that other procedures will provide a variety of
sort methods, including ...
Exchange sorts Bubble sort, Cocktail shaker sort, Odd-even sort,
Comb sort, Gnome sort, Quicksort, Stooge sort,
Bogosort
Selection sorts Selection sort, Heapsort, Smoothsort, Cartesian
tree sort, Tournament sort, Cycle sort
Insertion sorts Insertion sort, Shellsort, Splaysort, Tree sort,
Library sort, Patience sorting
Merge sorts Merge sort, Cascade merge sort, Oscillating merge
sort, Polyphase merge sort
Distribution sorts American flag sort, Bead sort, Bucket sort,
Burstsort, Counting sort, Pigeonhole sort,
Proxmap sort, Radix sort, Flashsort
Concurrent sorts Bitonic sorter, Batcher odd-even mergesort,
Pairwise sorting network
Hybrid sorts Block merge sortTimsort, Introsort, Spreadsort
Other Topological sorting, Pancake sorting, Spaghetti
sort
and an overview of topics concerning sorting
Theory Computational complexity theory, Big O notation,
Total orderLists, InplacementStabilityComparison
sort, Adaptive sort, Sorting network, Integer
sorting, X + Y sorting, Transdichotomous model,
Quantum sort
In the mean time those keywords can be useful in locating materials
on the WWW, especially in Wikipedia.
RANKING
Sorting generally refers to rearranging data in a specific order.
Ranking consists in finding, for each element of a set, its rank in
the sorted set, without changing the initial order of the set. In many
instances ranking is more flexible in that the order may be based
on one value of a user-defined type, and the indices can be used to
reorder virtually any type or related set; but it requires creating
an array of indices as well as the data being sorted.
Ranking is also useful when the sizes of the elements being sorted
are large, and therefore moving them around is resource-consuming.
QUICKSORT
Quicksort, also known as partition-exchange sort, uses these steps
o Choose any element of the array to be the pivot.
o Divide all other elements (except the pivot) into two partitions.
o All elements less than the pivot must be in the first partition.
o All elements greater than the pivot must be in the second partition.
o Use recursion to sort both partitions.
o Join the first sorted partition, the pivot, and the second sorted
partition.
The best pivot creates partitions of equal length (or lengths differing
by 1).
The worst pivot creates an empty partition (for example, if the pivot
is the first or last element of a sorted array).
The run-time of Quicksort ranges from O(n log n) with the best pivots,
to O(n2) with the worst pivots, where n is the number of elements in
the array.
Quicksort has a reputation as the fastest sort. Optimized variants
of quicksort are common features of many languages and libraries.
NAME
sort_shell(3f) - [M_sort:sort:shellsort] Generic subroutine sorts the array X using
Shell's Method
(LICENSE:PD)
SYNOPSIS
subroutine sort_shell(lines,order[,startcol,endcol])
character(len=*),intent(inout) :: lines(:)
character(len=*),intent(in) :: order
integer,optional,intent(in) :: startcol, endcol
subroutine sort_shell(ints,order)
integer,intent(inout) :: ints(:)
character(len=*),intent(in) :: order
subroutine sort_shell(reals,order)
real,intent(inout) :: reals(:)
character(len=*),intent(in) :: order
subroutine sort_shell(complexs,order,type)
character(len=*),intent(inout) :: lines(:)
character(len=*),intent(in) :: order
character(len=*),intent(in) :: type
DESCRIPTION
subroutine sort_shell(3f) sorts an array over a specified field
in numeric or alphanumeric order.
From Wikipedia, the free encyclopedia:
The step-by-step process of replacing pairs of items during the shell
sorting algorithm. Shellsort, also known as Shell sort or Shell's
method, is an in-place comparison sort. It can be seen as either a
generalization of sorting by exchange (bubble sort) or sorting by
insertion (insertion sort).[3] The method starts by sorting pairs of
elements far apart from each other, then progressively reducing the gap
between elements to be compared. Starting with far apart elements, it
can move some out-of-place elements into position faster than a simple
nearest neighbor exchange. Donald Shell published the first version
of this sort in 1959.[4][5] The running time of Shellsort is heavily
dependent on the gap sequence it uses. For many practical variants,
determining their time complexity remains an open problem.
Shellsort is a generalization of insertion sort that allows the
exchange of items that are far apart. The idea is to arrange the list
of elements so that, starting anywhere, considering every hth element
gives a sorted list. Such a list is said to be h-sorted. Equivalently,
it can be thought of as h interleaved lists, each individually sorted.[6]
Beginning with large values of h, this rearrangement allows elements
to move long distances in the original list, reducing large amounts
of disorder quickly, and leaving less work for smaller h-sort steps to
do. If the file is then k-sorted for some smaller integer k, then the
file remains h-sorted. Following this idea for a decreasing sequence of
h values ending in 1 is guaranteed to leave a sorted list in the end.
F90 NOTES:
o procedure names are declared private in this module so they are
not accessible except by their generic name
o procedures must include a "use M_sort" to access the generic
name SORT_SHELL
o if these routines are recompiled, routines with the use statement
should then be recompiled and reloaded.
OPTIONS
Usage:
X input/output array to sort of type CHARACTER, INTEGER,
REAL, DOUBLEPRECISION, COMPLEX, or DOUBLEPRECISION COMPLEX.
order sort order
o A for Ascending (a-z for strings, small to large for values)
o D for Descending (z-a for strings, large to small for
values, default)
FOR CHARACTER DATA:
startcol character position in strings which starts sort field.
Only applies to character values. Defaults to 1. Optional.
endcol character position in strings which ends sort field
Only applies to character values. Defaults to end of string.
Optional.
FOR COMPLEX AND COMPLEX(KIND=KIND(0.0D0)) DATA:
type Sort by
R for Real component,
I for Imaginary component,
S for the magnitude Sqrt(R**2+I**2)
EXAMPLE
Sample program
program demo_sort_shell
use M_sort, only : sort_shell
implicit none
character(len=:),allocatable :: array(:)
integer :: i
array = [ &
& 'red ','green ','blue ','yellow ','orange ','black ',&
& 'white ','brown ','gray ','cyan ','magenta', &
& 'purple ']
write(*,'(a,*(a:,","))')'BEFORE ',(trim(array(i)),i=1,size(array))
call sort_shell(array,order='a')
write(*,'(a,*(a:,","))')'A-Z ',(trim(array(i)),i=1,size(array))
do i=1,size(array)-1
if(array(i).gt.array(i+1))then
write(*,*)'Error in sorting strings a-z'
endif
enddo
array= [ &
& 'RED ','GREEN ','BLUE ','YELLOW ','ORANGE ','BLACK ',&
& 'WHITE ','BROWN ','GRAY ','CYAN ','MAGENTA', &
& 'PURPLE ']
write(*,'(a,*(a:,","))')'Before ',(trim(array(i)),i=1,size(array))
call sort_shell(array,order='d')
write(*,'(a,*(a:,","))')'Z-A ',(trim(array(i)),i=1,size(array))
do i=1,size(array)-1
if(array(i).lt.array(i+1))then
write(*,*)'Error in sorting strings z-a'
endif
enddo
end program demo_sort_shell
Expected output
Before
red,green,blue,yellow,orange,black,white,brown,gray,cyan,magenta,purple
A-Z
black,blue,brown,cyan,gray,green,magenta,orange,purple,red,white,yellow
Before
RED,GREEN,BLUE,YELLOW,ORANGE,BLACK,WHITE,BROWN,GRAY,CYAN,MAGENTA,PURPLE
Z-A
YELLOW,WHITE,RED,PURPLE,ORANGE,MAGENTA,GREEN,GRAY,CYAN,BROWN,BLUE,BLACK
REFERENCE
1. Algorithm 201, SHELLSORT, J. Boothroyd, CACM Vol. 6, No. 8, P 445, (1963)
2. D. L. Shell, CACM, Vol. 2, P. 30, (1959)
AUTHOR
Arguments
Type |
Intent | Optional | Attributes |
|
Name |
|
character(len=*),
|
intent(inout) |
|
|
:: |
lines(:) |
|
character(len=*),
|
intent(in) |
|
|
:: |
order |
|
integer,
|
intent(in), |
optional |
|
:: |
startcol |
|
integer,
|
intent(in), |
optional |
|
:: |
endcol |
|