Re: zipcode selection sort in MR&C

On Wed, 27 Aug 2008 03:44:58 -0800, glen herrmannsfeldt posted:

Ron Ford wrote:
(snip)

I've got one other question for you, Glen, while I've got your attention
(or anyone else whose opinion is more informed than mine). It's on its way
to being OT, so I'll promise not to pursue it to it's algorithmic end.

I've had some time now to look at this sort and figure out what it is
doing. With integers populating the array, it tells maxlox to find the
biggest one, put it at the end; it decrements the size and true to its
"recursive" descriptor, calls itself.

Yes, selection sort shouldn't be implemented with recursion,
and especially not passing a copy of (part of) the array.

I can see that now.


If array_size is 100, what can you say about the stack size as it executes,
if the fortran implementation uses a stack. Is it as simple as 99 high?

I executed the sort with 500,000 instead of 50,000 elements. It went from
taking fifteen seconds to taking a half hour. If the implementation were
via a stack, was the stack half a million high?

In some cases compilers can recognize tail recursion and
change it to a branch to the entry point. That is, if the last
statement of a subroutine (before RETURN) is a call to a
subroutine it can be replaced with a jump (not a call) to
the subroutine. (Assuming nothing else has to be done, such
as copying arguments back or deallocating automatic variables.)

-- glen

I see. I'm surprised that compilation time has increased as I ratchet up
trials with the same curve.

I may have hit the end of utility that this routine has been for me. I get
a runtime in the swap routine with the assignment of a value to temp. Is
temp of kind i13?

module sort4
implicit none
integer, parameter :: i13 = selected_int_kind(13)
private
public :: selection_sort
! type definition includes only an integer
type, public :: address
integer(i13) :: zip_code
end type address
contains
recursive subroutine selection_sort (array_arg)
integer, parameter :: i13 = selected_int_kind(13)
type (address), dimension(:), intent (inout) &
:: array_arg
integer(i13) :: current_size
integer(i13) :: big
current_size = size (array_arg)
if (current_size > 0) then
big = maxloc(array_arg(:)%zip_code, dim=1)
call swap (big, current_size)
call selection_sort (array_arg(1: current_size -1))
end if
contains
subroutine swap(i,j)
integer, parameter :: i13 = selected_int_kind(13)
integer(i13), intent (in) :: i,j
type (address) :: temp
temp = array_arg(i)
array_arg(i) = array_arg(j)
array_arg(j) = temp
end subroutine swap
end subroutine selection_sort
end module sort4

I love Joe Biden. That he went through a hippy phase is how he must have
named his boy: Bo. Must have been some kind buds in the sixties to make
Bo Biden sound like a reasonable name. Of course, people call me Sioux.
--
We are here and it is now. Further than that, all human knowledge is
moonshine. 3
H. L. Mencken
.

Relevant Pages

  • Re: Yet Another Spinoza Challenge
    ...  > free language can only be compiled with a stack, ... If it also has recursive subroutine call, ...  > has subroutine call, but no recursion, is dead on arrival. ... that was why Fortran was dead on arrival. ...
    (comp.lang.c)
  • Re: busting sp datatypes
    ... While the routines I call are sorts, ... recursive subroutine selection_sort ... type:: temp ... sort into bins ...
    (comp.lang.fortran)
  • Re: subroutines as arguments
    ... it is passing me by. ... subroutine bar in the original example. ... independent of issues of recursion. ... that the lack of an external statement is a reason for this being ...
    (comp.lang.fortran)
  • Re: perldocs (etc) on recursion in Perl? Dont understand _WCPS_ example
    ... but I know little about how recursion is implemented in Perl ... Let's ignore the fact that he's using a subroutine prototype (Mr. ... This is a subroutine declaration. ... Recursing again, arg = 4 ...
    (comp.lang.perl.misc)
  • Re: adapting a quicksort
    ... recursive subroutine selection_sort ... type:: temp ... tab, maxput ... real:: harvest, tot ...
    (comp.lang.fortran)