zipcode selection sort in MR&C
Ron Ford
reverse this shortcoming by implementing the sort in §10 MR&C. I think
this is an example of fair use: I bought the guys' book, typed in
something close to its content as I watched the olympics and managed on my
girlfriend's laptop, and posted it on the net to work out the kinks.
I think that studying fortran and watching women's volleyball and handball
are tasks that improve the quality of the other. I must say I developed I
little crush on the handball hungarian sharpshooter Görnic and wish them
luck if they play the french tomorrow but wish for penalty cards if they
play the russians. Please punish the aggressors.
module sort
implicit none
private
public :: selection_sort
integer, parameter :: string_length = 30
type, public :: address
character(len = string_length) :: name, &
street, town, state*2
integer :: zip_code
end type address
contains
recursive subroutine selection_sort (array_arg)
type (address), dimension(:), intent (inout) &
:: array_arg
integer :: current_size
integer :: 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, 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 sort
This is the exact sort in MR&C.
program zippy
use sort
implicit none
integer, parameter :: array_size = 100
type (address), dimension (array_size) :: data_array
integer :: i,n, ios
open(2, file='addresses.txt', iostat=ios, err=99)
open(3, file='output.txt')
do i = 1, array_size
read (2, '(/a/a/a2,i8)',end=10) data_array(i)
write (3, '(/a/a/a/a2,i8)') data_array(i)
end do
10 n = i - 1
call selection_sort (data_array(1:n))
write(3, '(//a)') 'after sorting'
do i = 1, n
write (3, '(/a/a/a/a2,i8)') data_array(i)
end do
99 write(3,*) "99", ios
end program zippy
This is a modified caller that doesn't seem to work yet. Addresses.txt is
exactly:
T. Boone Pickens
350 Swiftboat Lane
Houston, TX 45536
Ev Bayh
1016 Humdity Bath
Indianapolis, IN 47250
Cindy McCain
1000 Richie Rich
Scottsdale, AZ 85250
Diane Feinstein
250 Harvey Milk Circle
San Fransisco, CA 96580
Tim Pawlenty
500 Olson way
St. Paul, MN 56674
Donald Trump
100 Trump Plaza
New York, NY 10080
Output.txt is:
after sorting
99 0
I'm looking for help to diagnose what's not clicking here yet. There's one
datum that I think is salient: When I run it, windows creates a second
file called addresses.txt that has nothing in it.
Thanks and cheers,
--
When a new source of taxation is found it never means, in practice, that
the old source is abandoned. It merely means that the politicians have two
ways of milking the taxpayer where they had one before. 8
H. L. Mencken
glen herrmannsfeldt
(snip)
> read (2, '(/a/a/a2,i8)',end=10) data_array(i)
I don't think this format can read the file the
way you want it read.
To start, the initial / will skip the first line.
Next, you should have four A descriptors
to match the four CHARACTER variables.
Third, the third A will read in the city, state, and zip
leaving nothing when it gets to reading the zip in I8 format.
The read will fail and on most systems will print a
message telling you that it failed.
> Addresses.txt is exactly:
> T. Boone Pickens
> 350 Swiftboat Lane
> Houston, TX 45536
>
> Ev Bayh
> 1016 Humdity Bath
> Indianapolis, IN 47250
>
> Cindy McCain
> 1000 Richie Rich
> Scottsdale, AZ 85250
>
> Diane Feinstein
> 250 Harvey Milk Circle
> San Fransisco, CA 96580
>
> Tim Pawlenty
> 500 Olson way
> St. Paul, MN 56674
>
> Donald Trump
> 100 Trump Plaza
> New York, NY 10080
>
> Output.txt is:
>
> after sorting
> 99 0
-- glen
Ron Ford
> Ron Ford wrote:
> (snip)
>
>> read (2, '(/a/a/a2,i8)',end=10) data_array(i)
>
> I don't think this format can read the file the
> way you want it read.
>
> To start, the initial / will skip the first line.
Alright, so I ace the initial backslash.
The read should read:
read (2, '(a/a/a/a2,i8)',end=10) data_array(i)
?
What if Donald Trump places another monument to his galactic ego by placing
'Trump' in a couple more places:
>> Donald Trump
>> 100 Trump Plaza trump
>> New trump York, NY 10080
?
--
We must be willing to pay a price for freedom. 4
H. L. Mencken
glen herrmannsfeldt
(snip)
>>>Donald Trump
>>>100 Trump Plaza
>>>New York, NY 10080
(snip)
> The read should read:
> read (2, '(a/a/a/a2,i8)',end=10) data_array(i)
and then put the state and zip code on the next line.
C has a format specifier that will allow reading up until
some set of characters appears to end on the comma.
-- glen
Ron Ford
Thanks, Glen. I had two errors going at the same time. One was that I
misspelled addresses.txt when I named the actual file (Germans use one d in
address). That was why windows was creating another one. The other was
that the addresses needed to formatted differently, as you indicated.
Output.txt is now:
T. Boone Pickens
350 Swiftboat Lane
Houston,
TX 45536
Ev Bayh
1016 Humdity Bath
Indianapolis,
IN 47250
Cindy McCain
1000 Richie Rich
Scottsdale,
AZ 85250
Diane Feinstein
250 Harvey Milk Circle
San Fransisco,
CA 96580
Tim Pawlenty
500 Olson way
St. Paul,
MN 56674
Donald Trump
100 Trump Plaza
New York,
NY 10080
after sorting
Donald Trump
100 Trump Plaza
New York,
NY 10080
T. Boone Pickens
350 Swiftboat Lane
Houston,
TX 45536
Ev Bayh
1016 Humdity Bath
Indianapolis,
IN 47250
Tim Pawlenty
500 Olson way
St. Paul,
MN 56674
Cindy McCain
1000 Richie Rich
Scottsdale,
AZ 85250
Diane Feinstein
250 Harvey Milk Circle
San Fransisco,
CA 96580
99 0
If zippy is now:
program zippy
use sort
implicit none
integer, parameter :: array_size = 100
type (address), dimension (array_size) :: data_array
integer :: i,n, ios
open(2, file='addresses2.txt', status='old', iostat=ios, err=99)
open(3, file='output.txt', status='replace')
do i = 1, array_size
read (2, '(/a/a/a/a2,i8)',end=10) data_array(i)
write (3, '(/a/a/a/a2,i8)') data_array(i)
end do
10 n = i - 1
call selection_sort (data_array(1:n))
write(3, '(//a)') 'after sorting'
do i = 1, n
write (3, '(/a/a/a/a2,i8)') data_array(i)
end do
99 write(3,*) "99", ios
end program zippy
, is maybe the source of error at the end that it appears to expect 100
entries? How can you tell it to read until there's no more to be read?
--
We are here and it is now. Further than that, all human knowledge is
moonshine. 3
H. L. Mencken
Gary Scott
> On Tue, 19 Aug 2008 21:03:22 -0800, glen herrmannsfeldt posted:
>
>
>>Ron Ford wrote:
>>(snip)
>>
>>
<snip>
> Thanks, Glen. I had two errors going at the same time. One was that I
> misspelled addresses.txt when I named the actual file (Germans use one d in
> address). That was why windows was creating another one. The other was
> that the addresses needed to formatted differently, as you indicated.
> Output.txt is now:
>
>
> T. Boone Pickens
> 350 Swiftboat Lane
> Houston,
> TX 45536
T. Boone may have a residence in Houston, I don't know, but he lives in
the TX panhandle.
>
> Ev Bayh
> 1016 Humdity Bath
> Indianapolis,
> IN 47250
>
Indianapolis may be humid, but Houston would probably win that contest.
<snip>
--
Gary Scott
mailto:garylscott@sbcglobal dot net
Fortran Library: http://www.fortranlib.com
Support the Original G95 Project: http://www.g95.org
-OR-
Support the GNU GFortran Project: http://gcc.gnu.org/fortran/index.html
If you want to do the impossible, don't hire an expert because he knows
it can't be done.
-- Henry Ford
e p chandler
[snip]
Input data records are of the form:
>
> Cindy McCain
> 1000 Richie Rich
> Scottsdale,
> AZ 85250
>
Program text:
> program zippy
> use sort
> implicit none
> integer, parameter :: array_size = 100
> type (address), dimension (array_size) :: data_array
> integer :: i,n, ios
>
> open(2, file='addresses2.txt', status='old', iostat=ios, err=99)
> open(3, file='output.txt', status='replace')
> do i = 1, array_size
> read (2, '(/a/a/a/a2,i8)',end=10) data_array(i)
> write (3, '(/a/a/a/a2,i8)') data_array(i)
> end do
> 10 n = i - 1
> call selection_sort (data_array(1:n))
>
> write(3, '(//a)') 'after sorting'
> do i = 1, n
> write (3, '(/a/a/a/a2,i8)') data_array(i)
> end do
>
> 99 write(3,*) "99", ios
> end program zippy
>
> , is maybe the source of error at the end that it appears to expect 100
> entries? How can you tell it to read until there's no more to be read?
The output file contains 99 ios because program execution falls
through to statement 99.
How about something like this?
program zippy
use sort
implicit none
integer, parameter :: array_size = 100
type (address), dimension (array_size) :: data_array
! temp variable - attempt to read here
type (address) :: input_record
integer :: i, n, ios
! no more statement 99
open(2, file='addresses2.txt', status='old', iostat=ios)
if (ios /= 0) then
write(*,*) 'error ',ios,' opening input file'
stop
end if
open(3, file='output.txt', status='replace')
n = 0
do
read (2, '(/a/a/a/a2,i8)',iostat=ios) input_record
! quit on end of file or other errors
if (ios /= 0) exit
! feel free to check the value of ios and do something with it here
write (3, '(/a/a/a/a2,i8)') input_record
! ok, we got another one
! who cares if we copy it to the array?
n = n + 1
data_array(n) = input_record
if (n == array_size) exit
end do
call selection_sort (data_array(1:n))
write(3, '(//a)') 'after sorting'
do i = 1, n
write (3, '(/a/a/a/a2,i8)') data_array(i)
end do
end program zippy
- e
Ron Ford
> On Aug 20, 8:58 pm, Ron Ford <r...@example.invalid> wrote:
>
> How about something like this?
[code elided]
Works like a charm, Elliot, thanks.
I've got one last thing I wanted to try with the zipcode sort for right
now. I thought I might write the city state and zip on one line, as is
customary. Removing the slash and adding a comma in the edit descriptor
gives:
Tim Pawlenty
500 Olson way
St. Paul, MN 56674
I tried to put St. Paul a little closer to Minnesota with:
write (3, '(/a/a/trim(a), a2,i8)') data_array(i)
, but my compiler said nix to that. Is there a(n easy) way to trim the
trailing blanks on the city?
I also had a question about the declaration of the derived type:
integer, parameter :: string_length = 30
type, public :: address
character(len = string_length) :: name, &
street, town, state*2
integer :: zip_code
end type address
As it is, am I correct that name, street and town are length 30, but state
is length 2?
One other thing. We don't close anything. Just to be thorough, would we
want to
close (2)
close (3)
before termination?
You've got the temperament of a teacher, which I, as a continuing learner,
appreciate. Please take a look at my integer sort thread now that I'll try
to sort something else.
Ron Ford
> Ron Ford wrote:
>
>> On Tue, 19 Aug 2008 21:03:22 -0800, glen herrmannsfeldt posted:
>>
>>
>>>Ron Ford wrote:
>>>(snip)
>>>
>>>
> <snip>
>> Thanks, Glen. I had two errors going at the same time. One was that I
>> misspelled addresses.txt when I named the actual file (Germans use one d in
>> address). That was why windows was creating another one. The other was
>> that the addresses needed to formatted differently, as you indicated.
>> Output.txt is now:
>>
>>
>> T. Boone Pickens
>> 350 Swiftboat Lane
>> Houston,
>> TX 45536
>
> T. Boone may have a residence in Houston, I don't know, but he lives in
> the TX panhandle.
>
>>
>> Ev Bayh
>> 1016 Humdity Bath
>> Indianapolis,
>> IN 47250
>>
>
> Indianapolis may be humid, but Houston would probably win that contest.
>
> <snip>
I wasn't short of reasons not to visit Texas (my ex's really do live in
Texas), but that's one contest I don't want to show up for.
e p chandler
> On Wed, 20 Aug 2008 19:19:37 -0700 (PDT), e p chandler posted:
>
> > On Aug 20, 8:58 pm, Ron Ford <r...@example.invalid> wrote:
>
> > How about something like this?
>
> [code elided]
>
> Works like a charm, Elliot, thanks.
>
> I've got one last thing I wanted to try with the zipcode sort for right
> now. I thought I might write the city state and zip on one line, as is
> customary. Removing the slash and adding a comma in the edit descriptor
> gives:
>
> Tim Pawlenty
> 500 Olson way
> St. Paul, MN 56674
>
> I tried to put St. Paul a little closer to Minnesota with:
> write (3, '(/a/a/trim(a), a2,i8)') data_array(i)
> , but my compiler said nix to that. Is there a(n easy) way to trim the
> trailing blanks on the city?
Not that I know about. What I would do create an array which contains
3 strings (of equal length). Then I would populate it
from name and street just by copying. The last line could be created
with something like:
write(output_record(3),'(a,', ',a2,' ',i5) trim(town), state,
zip_code
Then perhaps
write(3,'(/3a)') output_record
> I also had a question about the declaration of the derived type:
>
> integer, parameter :: string_length = 30
> type, public :: address
> character(len = string_length) :: name, &
> street, town, state*2
> integer :: zip_code
> end type address
>
> As it is, am I correct that name, street and town are length 30, but state
> is length 2?
I've never used that construction but if it works, then it appears so.
> One other thing. We don't close anything. Just to be thorough, would we
> want to
> close (2)
> close (3)
> before termination?
I don't know under what conditions not closing files makes a
difference.
> You've got the temperament of a teacher, which I, as a continuing learner,
> appreciate.
Thank you. I continually learn from other members of this newsgroup.
As well, I also continue to make mistakes .... and learn from
them :-).
> Please take a look at my integer sort thread now that I'll try
> to sort something else.
OK. I'm not finding it difficult at all to jump back and forth among
several threads. So far it looks like you are doing a good job of
developing components and putting them together.
[comment]
In my suggestions for the data file reading program, I chose
simplicity over absolute efficiency. I don't like bouncing out of a
counted do loop early. I would rather create a temporary variable if
it makes the code clearer. Some of my coding quirks show the influence
of other languages. For example, there is COBOL, where input records
and output records are bound to buffer variables associated with
files. So I often do the classical - read an input record, process it,
write an output record, lather, rinse, repeat.....
- e
glen herrmannsfeldt
(snip)
> I tried to put St. Paul a little closer to Minnesota with:
> write (3, '(/a/a/trim(a), a2,i8)') data_array(i)
> , but my compiler said nix to that. Is there a(n easy) way to trim the
> trailing blanks on the city?
write (3, '(/a/a/a,1x,a2,i8)') data_array(i)%name,
* data_array(i)%street, trim(data_array(i)%town),
* data_array(i)%state, data_array(i)%zip_code
(or the appropriate form in free-format source)
You can decide if that is easy or not.
I believe trim() is not elemental. Also, it seems that elemental
functions can't be applied to structures anyway, and even it
it could, zip_code isn't CHARACTER.
> I also had a question about the declaration of the derived type:
> integer, parameter :: string_length = 30
> type, public :: address
> character(len = string_length) :: name, &
> street, town, state*2
> integer :: zip_code
> end type address
> As it is, am I correct that name, street and town
> are length 30, but state is length 2?
I am pretty sure that is right outside a structure
definition. I believe it is also legal inside one.
> One other thing. We don't close anything.
> Just to be thorough, would we want to
> close (2)
> close (3)
> before termination?
I believe files are guaranteed closed on proper termination.
If the program ends in other ways, buffers might not get
flushed. Java is one language that I know of that requires
output files to be closed even for normal termination to
get the buffers written out.
-- glen
Richard Maine
> I believe trim() is not elemental.
That's correct. It can't reasonably be elemental because elementl
application of it would imply a result array where each element had a
different length. There ain't no such animal in the language.
> Also, it seems that elemental
> functions can't be applied to structures anyway
That's not correct. I don't know where you would get such an idea from
either.
Oh.. I bet I figured it out. Perhaps you are talking about automatically
applying the same function to each component of a structure. Considering
your interest in PL/I, that's probably it. No, you can't do that
(whatever it would be called; components aren't elements, so "elemental"
wouldn't seem quite the right term for such a thing anyway).
But elemental functions certainly can be "applied to structures" just
like they can be applied to any type of data.
--
Richard Maine | Good judgement comes from experience;
email: last name at domain . net | experience comes from bad judgement.
domain: summertriangle | -- Mark Twain
glen herrmannsfeldt
(snip)
> Oh.. I bet I figured it out. Perhaps you are talking about automatically
> applying the same function to each component of a structure. Considering
> your interest in PL/I, that's probably it. No, you can't do that
> (whatever it would be called; components aren't elements, so "elemental"
> wouldn't seem quite the right term for such a thing anyway).
The OP wanted a simple way to change the program.
write (3, '(/a/a/a,1x,a2,i8)') trim(data_array(i))
would have been nice and simple, but doesn't work,
and still wouldn't work if zip_code was changed
to CHARACTER. I don't know what it would be called, either.
One possibility would be a format descriptor that
would print trimmed character data.
-- glen
Ron Ford
> write (3, '(/a/a/a,1x,a2,i8)') data_array(i)%name,
> * data_array(i)%street, trim(data_array(i)%town),
> * data_array(i)%state, data_array(i)%zip_code
That does the trick, Glen:
input:
Diane Feinstein
250 Harvey Milk Circle
San Fransisco,
CA 96580
output:
Diane Feinstein
250 Harvey Milk Circle
San Fransisco, CA 96580
--
What men value in this world is not rights but privileges. 7
H. L. Mencken
Ron Ford
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.
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?
glen herrmannsfeldt
(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.
> 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
Ron Ford
> 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.