pic_sorting_sort Module

This submodule implements the overloaded sorting subroutine SORT that can be used to sort four kinds of INTEGER arrays and three kinds of REAL arrays. Sorting is in order of increasing value, with the worst case run time performance of O(N Ln(N)).

SORT uses the INTROSORT sorting algorithm of David Musser, http://www.cs.rpi.edu/~musser/gp/introsort.ps. introsort is a hybrid unstable comparison algorithm combining quicksort, insertion sort, and heap sort. While this algorithm is always O(N Ln(N)) it is relatively fast on randomly ordered data, but inconsistent in performance on partly sorted data, sometimes having merge sort performance, sometimes having better than quicksort performance.

The generic subroutine implementing the SORT algorithm to return an input array with its elements sorted in order of (non-)decreasing value. Its use has the syntax:

 call sort( array[, reverse] )

with the arguments:

  • array: the rank 1 array to be sorted. It is an intent(inout) argument of any of the types integer(int8), integer(int16), integer(int32), integer(int64), real(real32), real(real64), real(real128), character(*), type(string_type), type(bitset_64), type(bitset_large). If both the type of array is real and at least one of the elements is a NaN, then the ordering of the result is undefined. Otherwise it is defined to be the original elements in non-decreasing order.
  • reverse (optional): shall be a scalar of type default logical. It is an intent(in) argument. If present with a value of .true. then array will be sorted in order of non-increasing values in unstable order. Otherwise index will sort array in order of non-decreasing values in unstable order.

Example

    ...
    ! Read random data from a file
    call read_file( 'dummy_file', array )
    ! Sort the random data
    call sort( array )
    ! Process the sorted data
    call array_search( array, values )
    ...

Uses

  • module~~pic_sorting_sort~~UsesGraph module~pic_sorting_sort pic_sorting_sort module~pic_optional_value pic_optional_value module~pic_sorting_sort->module~pic_optional_value module~pic_types pic_types module~pic_sorting_sort->module~pic_types module~pic_optional_value->module~pic_types iso_fortran_env iso_fortran_env module~pic_types->iso_fortran_env

Used by

  • module~~pic_sorting_sort~~UsedByGraph module~pic_sorting_sort pic_sorting_sort module~pic_sorting pic_sorting module~pic_sorting->module~pic_sorting_sort

Interfaces

public interface sort

The generic subroutine interface implementing the SORT algorithm, based on the introsort of David Musser. (Specification)

  • private pure module subroutine char_sort(array, reverse)

    char_sort( array[, reverse] ) sorts the input ARRAY of type character(len=*) using a hybrid sort based on the introsort of David Musser. The algorithm is of order O(N Ln(N)) for all inputs. Because it relies on quicksort, the coefficient of the O(N Ln(N)) behavior is small for random data compared to other sorting algorithms.

    Arguments

    Type IntentOptional Attributes Name
    character(len=*), intent(inout) :: array(0:)
    logical, intent(in), optional :: reverse

  • private pure module subroutine dp_sort(array, reverse)

    dp_sort( array[, reverse] ) sorts the input ARRAY of type real(dp) using a hybrid sort based on the introsort of David Musser. The algorithm is of order O(N Ln(N)) for all inputs. Because it relies on quicksort, the coefficient of the O(N Ln(N)) behavior is small for random data compared to other sorting algorithms.

    Arguments

    Type IntentOptional Attributes Name
    real(kind=dp), intent(inout) :: array(0:)
    logical, intent(in), optional :: reverse

  • private pure module subroutine int32_sort(array, reverse)

    int32_sort( array[, reverse] ) sorts the input ARRAY of type integer(int32) using a hybrid sort based on the introsort of David Musser. The algorithm is of order O(N Ln(N)) for all inputs. Because it relies on quicksort, the coefficient of the O(N Ln(N)) behavior is small for random data compared to other sorting algorithms.

    Arguments

    Type IntentOptional Attributes Name
    integer(kind=int32), intent(inout) :: array(0:)
    logical, intent(in), optional :: reverse

  • private pure module subroutine int64_sort(array, reverse)

    int64_sort( array[, reverse] ) sorts the input ARRAY of type integer(int64) using a hybrid sort based on the introsort of David Musser. The algorithm is of order O(N Ln(N)) for all inputs. Because it relies on quicksort, the coefficient of the O(N Ln(N)) behavior is small for random data compared to other sorting algorithms.

    Arguments

    Type IntentOptional Attributes Name
    integer(kind=int64), intent(inout) :: array(0:)
    logical, intent(in), optional :: reverse

  • private pure module subroutine sp_sort(array, reverse)

    sp_sort( array[, reverse] ) sorts the input ARRAY of type real(sp) using a hybrid sort based on the introsort of David Musser. The algorithm is of order O(N Ln(N)) for all inputs. Because it relies on quicksort, the coefficient of the O(N Ln(N)) behavior is small for random data compared to other sorting algorithms.

    Arguments

    Type IntentOptional Attributes Name
    real(kind=sp), intent(inout) :: array(0:)
    logical, intent(in), optional :: reverse

Subroutines

private pure subroutine char_decrease_sort(array)

Arguments

Type IntentOptional Attributes Name
character(len=*), intent(inout) :: array(0:)

private pure subroutine char_increase_sort(array)

Arguments

Type IntentOptional Attributes Name
character(len=*), intent(inout) :: array(0:)

private pure module subroutine char_sort(array, reverse)

Arguments

Type IntentOptional Attributes Name
character(len=*), intent(inout) :: array(0:)
logical, intent(in), optional :: reverse

private pure subroutine dp_decrease_sort(array)

Arguments

Type IntentOptional Attributes Name
real(kind=dp), intent(inout) :: array(0:)

private pure subroutine dp_increase_sort(array)

Arguments

Type IntentOptional Attributes Name
real(kind=dp), intent(inout) :: array(0:)

private pure module subroutine dp_sort(array, reverse)

Arguments

Type IntentOptional Attributes Name
real(kind=dp), intent(inout) :: array(0:)
logical, intent(in), optional :: reverse

private pure subroutine int32_decrease_sort(array)

Arguments

Type IntentOptional Attributes Name
integer(kind=int32), intent(inout) :: array(0:)

private pure subroutine int32_increase_sort(array)

Arguments

Type IntentOptional Attributes Name
integer(kind=int32), intent(inout) :: array(0:)

private pure module subroutine int32_sort(array, reverse)

Arguments

Type IntentOptional Attributes Name
integer(kind=int32), intent(inout) :: array(0:)
logical, intent(in), optional :: reverse

private pure subroutine int64_decrease_sort(array)

Arguments

Type IntentOptional Attributes Name
integer(kind=int64), intent(inout) :: array(0:)

private pure subroutine int64_increase_sort(array)

Arguments

Type IntentOptional Attributes Name
integer(kind=int64), intent(inout) :: array(0:)

private pure module subroutine int64_sort(array, reverse)

Arguments

Type IntentOptional Attributes Name
integer(kind=int64), intent(inout) :: array(0:)
logical, intent(in), optional :: reverse

private pure subroutine sp_decrease_sort(array)

Arguments

Type IntentOptional Attributes Name
real(kind=sp), intent(inout) :: array(0:)

private pure subroutine sp_increase_sort(array)

Arguments

Type IntentOptional Attributes Name
real(kind=sp), intent(inout) :: array(0:)

private pure module subroutine sp_sort(array, reverse)

Arguments

Type IntentOptional Attributes Name
real(kind=sp), intent(inout) :: array(0:)
logical, intent(in), optional :: reverse