|
interface | isAscending |
| Generate and return .true. if the input array is sorted in ascending order (with the possibility elements being equal), otherwise, generate and return .false. . More...
|
|
interface | isDescending |
| Generate and return .true. if the input array is sorted in descending order (with the possibility elements being equal), otherwise, generate and return .false. . More...
|
|
interface | isSorted |
| Return .true. if the input array is sorted, either ascending or descending, or all equal. More...
|
|
interface | merge |
| Merge two ascending-sorted arrays such that the resulting merged array contains all elements of the two arrays in ascending order. More...
|
|
interface | operator(.merge.) |
| Generate an ascending-sorted merger of the two ascending-sorted input arrays. More...
|
|
interface | sort |
| Sort the input contiguous Array of rank 1 in ascending order, using a mixture of Quicksort algorithm (for large arrays) and selection-sort algorithm (for small arrays). More...
|
|
interface | sortBubble |
| Sort the input contiguous Array of rank 1 in ascending order, using the Bubble sorting algorithm. More...
|
|
interface | sortDualPivotRecursive |
| Sort the input contiguous Array of rank 1 in ascending order, using a mixture of merge-sort and Dual-Pivot Quicksort algorithms. More...
|
|
interface | sortHeap |
| Sort the input contiguous Array of rank 1 in ascending order, using the Heapsort algorithm. More...
|
|
interface | sortHeapRecursive |
| Sort the input contiguous Array of rank 1 in ascending order, using the recursive Heapsort algorithm. More...
|
|
interface | sortIndex |
| Return the sorted indices of the input contiguous Array of rank 1 in ascending order using the Quicksort algorithm, such that Array(Index) will be in ascending order. More...
|
|
interface | sortInsertion |
| Sort the input contiguous Array of rank 1 in ascending order, using the Insertion algorithm. More...
|
|
interface | sortInsertionBinary |
| Sort the input contiguous Array of rank 1 in ascending order, using the Insertion algorithm with Binary search. The Binary search method yields better performance for larger input arrays. More...
|
|
interface | sortInsertionDouble |
| Sort the input contiguous Array of rank 1 in ascending order, using the Double Insertion algorithm. The Binary search method yields better performance for larger input arrays. More...
|
|
interface | sortMergeRecursive |
| Sort the input contiguous Array of rank 1 in ascending order, using a mixture of insertion-sort and merge-sort algorithms. More...
|
|
interface | sortRecursive |
| Sort the input contiguous Array of rank 1 in ascending order, using a mixture of merge-sort and Quicksort algorithms. More...
|
|
interface | sortSelection |
| Sort the input contiguous Array of rank 1 in ascending order, using the Selection sorting algorithm. More...
|
|
interface | sortShell |
| Sort the input contiguous Array of rank 1 in ascending order, using the Shell sorting algorithm. More...
|
|
This module contains procedures for sorting arrays and merging sorted arrays.
- Note
- Recommended routines for sorting arrays:
- The procedures under the generic interface sort are among the fastest sorting algorithms particularly for fully random input arrays.
- Benchmarks:
Benchmark :: sorting ⛓
- Here is a code snippet for a performance comparison of the different sorting algorithms in this module.
12 integer(IK) :: fileUnitRandom
13 integer(IK) :: fileUnitSorted
14 integer(IK) ,
parameter :: NARR
= 12_IK
15 integer(IK) ,
parameter :: NBENCH
= 12_IK
16 integer(IK) :: ArraySize(NARR)
17 real(RK) ,
allocatable :: Array(:)
18 type(Bench_type) :: Bench(
2,NBENCH)
35 ArraySize
= [(
2_IK**iarr, iarr
= 3_IK, NARR
+ 2_IK )]
37 write(
*,
"(*(g0,:,' '))")
38 write(
*,
"(*(g0,:,' '))")
"sort() vs. others."
39 write(
*,
"(*(g0,:,' '))")
41 open(newunit
= fileUnitRandom, file
= "main.random.out", status
= "replace")
42 open(newunit
= fileUnitSorted, file
= "main.sorted.out", status
= "replace")
44 write(fileUnitRandom ,
"(*(g0,:,','))")
"ArraySize", (Bench(
1,i)
%name, i
= 1, NBENCH)
45 write(fileUnitSorted,
"(*(g0,:,','))")
"ArraySize", (Bench(
2,i)
%name, i
= 1, NBENCH)
47 loopOverArraySize:
do iarr
= 1, NARR
49 allocate(Array(ArraySize(iarr)))
50 write(
*,
"(*(g0,:,' '))")
"Benchmarking sorting algorithms with array size", ArraySize(iarr)
58 call Bench(
1,i)
%time(Bench(
1,i)
%Timing)
60 write(fileUnitRandom,
"(*(g0,:,','))") ArraySize(iarr), (Bench(
1,i)
%Timing
%Stat
%mean, i
= 1, NBENCH)
68 call Bench(
2,i)
%time(Bench(
2,i)
%Timing)
70 write(fileUnitSorted,
"(*(g0,:,','))") ArraySize(iarr), (Bench(
2,i)
%Timing
%Stat
%mean, i
= 1, NBENCH)
74 end do loopOverArraySize
75 write(
*,
"(*(g0,:,' '))")
93 Array(:)
= genLinSpace(
0._RK,
1._RK, count
= size(Array,
kind = IK))
95 call random_number(Array)
Sort the input contiguous Array of rank 1 in ascending order, using the Bubble sorting algorithm.
Sort the input contiguous Array of rank 1 in ascending order, using a mixture of merge-sort and Dual-...
Sort the input contiguous Array of rank 1 in ascending order, using the recursive Heapsort algorithm.
Sort the input contiguous Array of rank 1 in ascending order, using the Heapsort algorithm.
Sort the input contiguous Array of rank 1 in ascending order, using the Insertion algorithm with Bina...
Sort the input contiguous Array of rank 1 in ascending order, using the Double Insertion algorithm....
Sort the input contiguous Array of rank 1 in ascending order, using the Insertion algorithm.
Sort the input contiguous Array of rank 1 in ascending order, using a mixture of insertion-sort and m...
Sort the input contiguous Array of rank 1 in ascending order, using a mixture of merge-sort and Quick...
Sort the input contiguous Array of rank 1 in ascending order, using the Selection sorting algorithm.
Sort the input contiguous Array of rank 1 in ascending order, using the Shell sorting algorithm.
Sort the input contiguous Array of rank 1 in ascending order, using a mixture of Quicksort algorithm ...
This module contains procedures for sorting arrays and merging sorted arrays.
This module contains abstract interfaces and types that facilitate benchmarking of different procedur...
This module contains the mathematical and programming constants.
integer, parameter IK
default integer kind in Fortran mode.
integer, parameter RK
default real kind in Fortran mode.
This module contains mathematical procedures.
This is the class for creating benchmark and performance-profiling objects.
Example Unix compile command via GNU gfortran
compiler ⛓
2gfortran -O3 -ffree-line-length-none -Wl,-rpath,../../../../lib -I../../../../include main.f90 ../../../../lib/libparamonte_fortran_*_gnu_*.so -o main.exe
Example Unix compile command via Intel ifort
compiler ⛓
2ifort -standard-semantics -O3 -Wl,-rpath,../../../../lib -I../../../../include main.f90 ../../../../lib/libparamonte_fortran_*_intel_*.so -o main.exe
Postprocessing of the output ⛓
3import matplotlib.pyplot
as plt
9colnames = [
"sortBubble"
14 ,
"sortInsertionDouble"
15 ,
"sortMergeRecursive"
18 ,
"sortDualPivotRecursive"
22dtypes = [
"random",
"sorted"]
30 df[dtype] = pd.read_csv(
"main.{}.out".format(dtype))
32 ax = plt.figure(figsize = 1.25*np.array([9.4,4.8]), dpi = 200)
35 for colname
in colnames:
36 plt.plot( df[dtype].values[:,0]
37 , df[dtype][colname].values / df[dtype][
"sort"].values
41 plt.xticks(fontsize = fontsize)
42 plt.yticks(fontsize = fontsize)
43 ax.set_xlabel(
"Array Size (# elements)", fontsize = fontsize)
44 ax.set_ylabel(
"Time normalized to sort() timing", fontsize = fontsize)
45 ax.set_title(
"Benchmarking of sorting algorithms compared to sort().\nInput data is " +
r"$\mathrm{\bf{" + dtype +
"}}$. Lower is better.", fontsize = fontsize)
49 plt.grid(b =
True, which =
"both", axis =
"both", color =
"0.85", linestyle =
"-")
50 ax.tick_params(axis =
"y", which =
"minor")
51 ax.tick_params(axis =
"x", which =
"minor")
54 , bbox_to_anchor=(1, 0.5)
59 plt.savefig(
"benchmark.sorting.{}.png".format(dtype))
63ax = plt.figure(figsize = 1.25*np.array([9.4,4.8]), dpi = 200)
66colnames.append(
"sort")
68for colname
in colnames:
69 plt.plot( df[
"random"].values[:,0]
70 , df[
"sorted"][colname].values / df[
"random"][colname].values
74plt.xticks(fontsize = fontsize)
75plt.yticks(fontsize = fontsize)
76ax.set_xlabel(
"Array Size (# elements)", fontsize = fontsize)
77ax.set_ylabel(
"Sorting Time Ratio ( Sorted / Random Input Array )", fontsize = fontsize)
78ax.set_title(
"Sorted / Random input-arrays sorting-time ratio. Lower is better.", fontsize = fontsize)
82plt.grid(b =
True, which =
"both", axis =
"both", color =
"0.85", linestyle =
"-")
83ax.tick_params(axis =
"y", which =
"minor")
84ax.tick_params(axis =
"x", which =
"minor")
87 , bbox_to_anchor=(1, 0.5)
92plt.savefig(
"benchmark.sorting.random.sorted.ratio.png")
Visualization of the benchmark output ⛓
Benchmark :: sorting vs. indexing ⛓
- The following program generates a performance comparison of the sort algorithm with sortIndex.
9 integer(IK) :: fileUnitRandom
10 integer(IK) :: fileUnitSorted
11 integer(IK) ,
parameter :: NARR
= 12_IK
12 integer(IK) ,
parameter :: NBENCH
= 3_IK
13 integer(IK) :: ArraySize(NARR)
14 real(RK) ,
allocatable :: Array(:)
15 integer(IK) ,
allocatable ::
Index(:)
17 type(Bench_type) :: Bench(
2,NBENCH)
23 ArraySize
= [(
2_IK**i, i
= 3_IK, NARR
+ 2_IK )]
29 write(
*,
"(*(g0,:,' '))")
30 write(
*,
"(*(g0,:,' '))")
"sort() vs. sortIndex."
31 write(
*,
"(*(g0,:,' '))")
33 open(newunit
= fileUnitRandom, file
= "main.random.out", status
= "replace")
34 open(newunit
= fileUnitSorted, file
= "main.sorted.out", status
= "replace")
35 write(fileUnitRandom,
"(*(g0,:,','))")
"ArraySize", (Bench(
1,i)
%name, i
= 1, NBENCH)
36 write(fileUnitSorted,
"(*(g0,:,','))")
"ArraySize", (Bench(
2,i)
%name, i
= 1, NBENCH)
38 loopOverArraySize:
do iarr
= 1, NARR
40 write(
*,
"(*(g0,:,' '))")
"Benchmarking with array size", ArraySize(iarr)
42 allocate(Array(ArraySize(iarr)),
Index(ArraySize(iarr)))
46 call Bench(
1,i)
%time(Bench(
1,i)
%Timing)
49 write(fileUnitRandom,
"(*(g0,:,','))") ArraySize(iarr), (Bench(
1,i)
%Timing
%Stat
%mean, i
= 1, NBENCH)
53 call Bench(
2,i)
%time(Bench(
2,i)
%Timing)
56 write(fileUnitSorted,
"(*(g0,:,','))") ArraySize(iarr), (Bench(
2,i)
%Timing
%Stat
%mean, i
= 1, NBENCH)
58 deallocate(Array, Index)
60 end do loopOverArraySize
70 Array(:)
= genLinSpace(
0._RK,
1._RK, count
= size(Array,
kind = IK))
72 call random_number(Array)
88 subroutine sortIndexWithSorting()
90 Array(:)
= Array(Index)
Return the sorted indices of the input contiguous Array of rank 1 in ascending order using the Quicks...
Example Unix compile command via GNU gfortran
compiler ⛓
2gfortran -O3 -ffree-line-length-none -Wl,-rpath,../../../../lib -I../../../../include main.f90 ../../../../lib/libparamonte_fortran_*_gnu_*.so -o main.exe
Example Unix compile command via Intel ifort
compiler ⛓
2ifort -standard-semantics -O3 -Wl,-rpath,../../../../lib -I../../../../include main.f90 ../../../../lib/libparamonte_fortran_*_intel_*.so -o main.exe
Postprocessing of the output ⛓
3import matplotlib.pyplot
as plt
11dtypes = [
"random",
"sorted"]
15 df = pd.read_csv(
"main.{}.out".format(dtype))
19 ax = plt.figure(figsize = 1.25*np.array([9.4,4.8]), dpi = 200)
22 for colname
in df.columns[1:]:
23 plt.plot( df.values[:,0]
28 plt.xticks(fontsize = fontsize)
29 plt.yticks(fontsize = fontsize)
30 ax.set_xlabel(
"Array Size (# elements)", fontsize = fontsize)
31 ax.set_ylabel(
"Time [ seconds ]", fontsize = fontsize)
32 ax.set_title(
"Timing of sort() vs. sortIndex(). Input data is {}.\n Lower is better.".format(dtype), fontsize = fontsize)
36 plt.grid(b =
True, which =
"both", axis =
"both", color =
"0.85", linestyle =
"-")
37 ax.tick_params(axis =
"y", which =
"minor")
38 ax.tick_params(axis =
"x", which =
"minor")
39 ax.legend ( df.columns[1:]
46 plt.savefig(
"benchmark.sorting_vs_indexing.{}.png".format(dtype))
50 ax = plt.figure(figsize = 1.25*np.array([9.4,4.8]), dpi = 200)
55 plt.plot( df.values[:,0]
56 , np.ones(len(df.values[:,0]))
61 for colname
in df.columns[2:]:
62 plt.plot( df.values[start:,0]
63 , df[colname].values[start:] / df[
"sort"].values[start:]
67 plt.xticks(fontsize = fontsize)
68 plt.yticks(fontsize = fontsize)
69 ax.set_xlabel(
"Array Size (# elements)", fontsize = fontsize)
70 ax.set_ylabel(
"Time Ratio ( sortIndex() / sort() )", fontsize = fontsize)
71 ax.set_title(
"Ratio of timing of sortIndex() to sort(). Input data is {}.".format(dtype), fontsize = fontsize)
75 plt.grid(b =
True, which =
"both", axis =
"both", color =
"0.85", linestyle =
"-")
76 ax.tick_params(axis =
"y", which =
"minor")
77 ax.tick_params(axis =
"x", which =
"minor")
78 ax.legend ( [
"Equality Line"] + list(df.columns[2:])
85 plt.savefig(
"benchmark.sorting_vs_indexing.{}.ratio.png".format(dtype))
Visualization of the benchmark output ⛓
The observed difference in the performance of sort vs. sortIndex is likely due to the current use of sortSelection and sortInsertion for small array sizes in sort and sortIndex, respectively.
- Author
- Amir Shahmoradi, April 21, 2017, 1:54 AM, ICES, The University of Texas at Austin