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 

Using PACK on TYPE's
Goto page Previous  1, 2
 
Post new topic   Reply to topic    forums.silverfrost.com Forum Index -> Support
View previous topic :: View next topic  
Author Message
mecej4



Joined: 31 Oct 2006
Posts: 1372

PostPosted: Sat Aug 01, 2020 7:23 am    Post subject: Reply with quote

For instructional purposes, that code for Qsort is fine. However, it is neither stable (in the sense of preserving the order of items with equal sort keys), nor efficient.

It is not stable since items equal to data(1) are placed earlier than data(1), regardless of their prior positions.

It is well-known (as you recognised with your own Qsort code a few months ago) that when the sublists become smaller than a cutoff (about 50 to 100, depending on the size of the data associated with the sort key), one should use insertion sort on the sublists. Furthermore, the heavy reliance on PACK makes the efficiency of the sorting highly dependent on the efficiency of the algorithm used by PACK itself.

The choice of data(1) as the pivot element will cause O(n^2) performance deterioration when the list is already sorted. There are, of course, remedies for this.

Arjen Markus posts regularly on CLF and in the Intel forums, and I am impressed by his willingness to make helpful comments and his prompt responses to questions.
Back to top
View user's profile Send private message
PaulLaidler
Site Admin


Joined: 21 Feb 2005
Posts: 6472
Location: Salford, UK

PostPosted: Fri Aug 07, 2020 12:24 pm    Post subject: Reply with quote

The bug reported at the start of this thread has now been fixed for the next release of FTN95.
Back to top
View user's profile Send private message AIM Address
JohnCampbell



Joined: 16 Feb 2006
Posts: 2200
Location: Sydney

PostPosted: Sun Aug 09, 2020 3:30 am    Post subject: Reply with quote

Paul,

Thanks for the fix.
What will be the response to "mine = pack(mine,selection)"?
I presume it will not re-allocate mine ? (F03)

The sort example I posted also fails with FTN95. Is that a similar problem ?
I don't think there is a requirement for F03+ re-allocate capability in the sort.
Back to top
View user's profile Send private message
PaulLaidler
Site Admin


Joined: 21 Feb 2005
Posts: 6472
Location: Salford, UK

PostPosted: Sun Aug 09, 2020 8:23 am    Post subject: Reply with quote

John

There is no re-allocation. I don't know if it is relevant in this context.

I have not tested other code in this thread. If you want to post it on a new thread then I will test it for you.
Back to top
View user's profile Send private message AIM Address
mecej4



Joined: 31 Oct 2006
Posts: 1372

PostPosted: Mon Aug 10, 2020 1:17 am    Post subject: Reply with quote

Paul,

I noticed several problems when attempting to compile simplified versions of John Campbell's quicksort test code. One of these versions causes the compiler to abort with an access violation, as I have reported in a new thread:

http://forums.silverfrost.com/viewtopic.php?t=4296

I believe that the code in that thread is free of errors.
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    forums.silverfrost.com Forum Index -> Support All times are GMT + 1 Hour
Goto page Previous  1, 2
Page 2 of 2

 
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