sort_ascending Subroutine

private subroutine sort_ascending(ivec)

Sorts an edge array ivec in increasing order by vertex number. Uses a basic recursive quicksort (with insertion sort for partitions with 20 elements).

Arguments

Type IntentOptional Attributes Name
type(edge), intent(inout), dimension(:) :: ivec

Calls

proc~~sort_ascending~~CallsGraph proc~sort_ascending dag_module::sort_ascending proc~swap dag_module::swap proc~sort_ascending->proc~swap

Called by

proc~~sort_ascending~~CalledByGraph proc~sort_ascending dag_module::sort_ascending proc~add_edge dag_module::vertex%add_edge proc~add_edge->proc~sort_ascending proc~set_edge_vector_vector dag_module::vertex%set_edge_vector_vector proc~set_edge_vector_vector->proc~sort_ascending proc~unique dag_module::unique proc~unique->proc~sort_ascending none~set_edges dag_module::vertex%set_edges none~set_edges->proc~add_edge none~set_edges->proc~set_edge_vector_vector proc~dag_add_edge dag_module::dag%dag_add_edge proc~dag_add_edge->none~set_edges proc~dag_set_edges_no_atts dag_module::dag%dag_set_edges_no_atts proc~dag_set_edges_no_atts->none~set_edges proc~dag_set_edges_vector_atts dag_module::dag%dag_set_edges_vector_atts proc~dag_set_edges_vector_atts->none~set_edges

Source Code

    subroutine sort_ascending(ivec)

    type(edge),dimension(:),intent(inout) :: ivec

    integer(ip),parameter :: max_size_for_insertion_sort = 20_ip !! max size for using insertion sort.

    call quicksort(1_ip,size(ivec,kind=ip))

    contains

        recursive subroutine quicksort(ilow,ihigh)

        !! Sort the array

        integer(ip),intent(in) :: ilow
        integer(ip),intent(in) :: ihigh

        integer(ip) :: ipivot !! pivot element
        integer(ip) :: i      !! counter
        integer(ip) :: j      !! counter

        if ( ihigh-ilow<=max_size_for_insertion_sort .and. ihigh>ilow ) then

            ! do insertion sort:
            do i = ilow + 1_ip,ihigh
                do j = i,ilow + 1_ip,-1_ip
                    if ( ivec(j)%ivertex < ivec(j-1_ip)%ivertex ) then
                        call swap(ivec(j),ivec(j-1_ip))
                    else
                        exit
                    end if
                end do
            end do

        elseif ( ihigh-ilow>max_size_for_insertion_sort ) then

            ! do the normal quicksort:
            call partition(ilow,ihigh,ipivot)
            call quicksort(ilow,ipivot - 1_ip)
            call quicksort(ipivot + 1_ip,ihigh)

        end if

        end subroutine quicksort

        subroutine partition(ilow,ihigh,ipivot)

        !! Partition the array, based on the
        !! lexical ivecing comparison.

        integer(ip),intent(in)  :: ilow
        integer(ip),intent(in)  :: ihigh
        integer(ip),intent(out) :: ipivot

        integer(ip) :: i,ii

        call swap(ivec(ilow),ivec((ilow+ihigh)/2_ip))
        ii = ilow
        do i = ilow + 1_ip, ihigh
            if ( ivec(i)%ivertex < ivec(ilow)%ivertex ) then
                ii = ii + 1_ip
                call swap(ivec(ii),ivec(i))
            end if
        end do
        call swap(ivec(ilow),ivec(ii))
        ipivot = ii

        end subroutine partition

    end subroutine sort_ascending