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: 1368

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: 6466
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
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