sort_ascending_64 Subroutine

private subroutine sort_ascending_64(ivec)

Arguments

Type IntentOptional Attributes Name
integer(kind=ip), intent(inout), dimension(:) :: ivec

Calls

proc~~sort_ascending_64~~CallsGraph proc~sort_ascending_64 aoc_utilities::sort_ascending_64 proc~swap64 aoc_utilities::swap64 proc~sort_ascending_64->proc~swap64

Called by

proc~~sort_ascending_64~~CalledByGraph proc~sort_ascending_64 aoc_utilities::sort_ascending_64 interface~sort aoc_utilities::sort interface~sort->proc~sort_ascending_64 proc~unique32 aoc_utilities::unique32 proc~unique32->interface~sort proc~unique64 aoc_utilities::unique64 proc~unique64->interface~sort interface~unique~2 aoc_utilities::unique interface~unique~2->proc~unique32 interface~unique~2->proc~unique64 proc~get_all_pieces_above problem_22::get_all_pieces_above proc~get_all_pieces_above->interface~unique~2 proc~get_all_pieces_above->proc~get_all_pieces_above proc~get_pieces_above problem_22::get_pieces_above proc~get_all_pieces_above->proc~get_pieces_above proc~get_all_pieces_below problem_22::get_all_pieces_below proc~get_all_pieces_below->interface~unique~2 proc~get_all_pieces_below->proc~get_all_pieces_below proc~get_pieces_below problem_22::get_pieces_below proc~get_all_pieces_below->proc~get_pieces_below proc~get_pieces_above->interface~unique~2 proc~get_pieces_below->interface~unique~2 proc~hand_type problem_7::hand_type proc~hand_type->interface~unique~2 program~problem_25 problem_25 program~problem_25->interface~unique~2 proc~beats problem_7::beats proc~beats->proc~hand_type proc~move_piece_down problem_22::move_piece_down proc~move_piece_down->proc~get_pieces_below program~problem_22 problem_22 program~problem_22->proc~get_all_pieces_above program~problem_22->proc~get_all_pieces_below program~problem_22->proc~get_pieces_above program~problem_22->proc~get_pieces_below proc~initialize problem_22::initialize program~problem_22->proc~initialize proc~drop problem_22::drop proc~drop->proc~move_piece_down program~problem_7 problem_7 program~problem_7->proc~beats proc~initialize->proc~drop

Source Code

    subroutine sort_ascending_64(ivec)

    integer(ip),dimension(:),intent(inout) :: ivec

    integer(ip),parameter :: max_size_for_insertion_sort = 20 !! 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,ihigh
                do j = i,ilow + 1,-1
                    if ( ivec(j) < ivec(j-1) ) then
                        call swap64(ivec(j),ivec(j-1))
                    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)
            call quicksort(ipivot + 1,ihigh)

        end if

        end subroutine quicksort

        subroutine partition(ilow,ihigh,ipivot)

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

        implicit none

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

        integer(ip) :: i,ip

        call swap64(ivec(ilow),ivec((ilow+ihigh)/2))
        ip = ilow
        do i = ilow + 1, ihigh
            if ( ivec(i) < ivec(ilow) ) then
                ip = ip + 1
                call swap64(ivec(ip),ivec(i))
            end if
        end do
        call swap64(ivec(ilow),ivec(ip))
        ipivot = ip

        end subroutine partition

    end subroutine sort_ascending_64