forums.silverfrost.com Forum Index forums.silverfrost.com
Welcome to the Silverfrost forums
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Sorting an array

 
Post new topic   Reply to topic    forums.silverfrost.com Forum Index -> General
View previous topic :: View next topic  
Author Message
AKS



Joined: 19 Mar 2008
Posts: 29

PostPosted: Wed Jul 01, 2020 5:25 pm    Post subject: Sorting an array Reply with quote

Would anyone know of a simple, free sort routine for Fortran 95?
Back to top
View user's profile Send private message
Kenneth_Smith



Joined: 18 May 2012
Posts: 370
Location: Hamilton, Lanarkshire, Scotland.

PostPosted: Wed Jul 01, 2020 5:36 pm    Post subject: Reply with quote

The following data sorting routines are available within FTN95:

CHSORT@ Sorts an array of characters.

DSORT@ Sorts a REAL(KIND=2) array.

ISORT@ Sorts an integer array.

RSORT@ Sorts a REAL(KIND=1) array.

See the following link for more information:-

https://silverfrost.com/ftn95-help/sort/idh_sorting_routines.aspx
Back to top
View user's profile Send private message Visit poster's website
mecej4



Joined: 31 Oct 2006
Posts: 1411

PostPosted: Wed Jul 01, 2020 5:52 pm    Post subject: Reply with quote

AKS,

Please list more detailed specifications for what you want from the sort routine. Does it have to be stable? Do you want a sort index returned? Is there an associated array to reorder? How big are the unsorted data sets? What are the types of the data to be sorted? Are there sorted runs already present in the data?
Back to top
View user's profile Send private message
AKS



Joined: 19 Mar 2008
Posts: 29

PostPosted: Wed Jul 01, 2020 10:55 pm    Post subject: Sorting an array Reply with quote

Thanks all for your response. I didn't know FTN95 had its own sort routines. I made some online searches, but musn't have used the right keywords. I have a program which has X and Y values in an array. I wanted to sort the X,Y pairs in ascending order for X and find the corresponding Y values. I found a routine on the web for sorting a single array (X) - bubble sort- and modified it to give me X sorted with the corresponding Y values. Thank everyone for your help. It's nice to know that this forum and you guys are so supportive. EJY
Back to top
View user's profile Send private message
mecej4



Joined: 31 Oct 2006
Posts: 1411

PostPosted: Wed Jul 01, 2020 11:23 pm    Post subject: Reply with quote

Bubble sort is simple to program, but it is among the worst in terms of performance. Insertion sort is about the same in complexity, but performs better in most cases.

Try one of the built-in sort routines that Kenneth mentioned.

If you are going to sort arrays larger than about 100 or you are going to sort many times, use mergesort. If you don't care for stability (i.e., if the order of equal items need not be preserved), use quicksort or a variant.

You can find code in many languages for the various sort algorithms at http://rosettacode.org/wiki/Category:Sorting_Algorithms .
Back to top
View user's profile Send private message
LitusSaxonicum



Joined: 23 Aug 2005
Posts: 2172
Location: Yateley, Hants, UK

PostPosted: Thu Jul 02, 2020 10:55 am    Post subject: Reply with quote

Quote:
"Bubble sort is simple to program, but it is among the worst in terms of performance."


Spot on. A really accurate statement, and I remember being astonished in about 1970 to read this somewhere, and that there were more efficient methods, even if they were far more complicated, both to understand and to program. The real issue with what method to use lies within the issues mentioned by Mecej4 in his earlier post with an additional observation or two from me:

Quote:
Does it have to be stable? Do you want a sort index returned? Is there an associated array to reorder? How big are the unsorted data sets? What are the types of the data to be sorted? Are there sorted runs already present in the data?


('Stable' has a specific meaning here, I believe, not being 'does it crash'. Mecej4 may well correct me.)

If the list is short, the speed may not be a factor, and also to get one value into the right place in an already sorted list is not the same as sorting a list that has some degree of unsortedness in it. Finally, you have to ask yourself does efficiency matter?

Here is an example from my own work. I have a line comprised of n (x,y) pairs. Using Clearwin+'s graphics, I define another x,y point with a mouse click and convert that from pixel coordinates to real world coordinates, including any rounding. I then want to insert that point into the list which is already sorted in order of ascending x. The line is usually made up of less than a dozen x,y pairs. Frankly, does it matter how quick the sort is? Just about anything you do will be done, including redrawing on the computer screen, faster than the user can click the mouse button to insert another point.

The method I use is to put the inserted point at the end of the list, then bubble sort it working backwards through the list, The new point simply moves through the list until it reaches the right place. Because I don't permit two points to share the same x coordinate, I am not concerned for the case where the order of two points with the same x coordinate is important (and I understand this to be the problem that 'stable' refers to). If it was, then I think I would simply start from the appropriate end of the list, or use an insertion method.

The bubble sort is easy to program, and as the x values are moved about in the list they can carry the associated y (or y,z) with them. The method works largely in the original list, and as the original list does not have to be preserved, takes little memory (Incidentally, 'Undo' works by taking the point out of the list and closing up to remove the gap).

I'm sure that there's a more efficient way to do it, but the time saving in running the program isn't worth spending the programming time on, especially as the impact on a user is non-existent already. That may not be the case with a huge list say a database of road junctions, where the more efficient methods certainly do have a role.

Eddie
Back to top
View user's profile Send private message
Kenneth_Smith



Joined: 18 May 2012
Posts: 370
Location: Hamilton, Lanarkshire, Scotland.

PostPosted: Thu Jul 02, 2020 4:00 pm    Post subject: Reply with quote

There is a discussion of this topic and benchmarks for different methods here:

https://www.mjr19.org.uk/IT/sorts/#:~:text=Sorting%20in%20Fortran&text=All%20the%20routines%20simply%20sort,correctness%20or%20fitness%20for%20purpose.&text=The%20very%20different%20scaling%20of%20the%20different%20algorithms%20is%20clear.
Back to top
View user's profile Send private message Visit poster's website
Display posts from previous:   
Post new topic   Reply to topic    forums.silverfrost.com Forum Index -> General All times are GMT + 1 Hour
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2001, 2005 phpBB Group