View previous topic :: View next topic |
Author |
Message |
mecej4
Joined: 31 Oct 2006 Posts: 1886
|
Posted: Sat Aug 01, 2020 7:23 am Post subject: |
|
|
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 |
|
|
PaulLaidler Site Admin
Joined: 21 Feb 2005 Posts: 7924 Location: Salford, UK
|
Posted: Fri Aug 07, 2020 12:24 pm Post subject: |
|
|
The bug reported at the start of this thread has now been fixed for the next release of FTN95. |
|
Back to top |
|
|
JohnCampbell
Joined: 16 Feb 2006 Posts: 2554 Location: Sydney
|
Posted: Sun Aug 09, 2020 3:30 am Post subject: |
|
|
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 |
|
|
PaulLaidler Site Admin
Joined: 21 Feb 2005 Posts: 7924 Location: Salford, UK
|
Posted: Sun Aug 09, 2020 8:23 am Post subject: |
|
|
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 |
|
|
mecej4
Joined: 31 Oct 2006 Posts: 1886
|
Posted: Mon Aug 10, 2020 1:17 am Post subject: |
|
|
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 |
|
|
wahorger
Joined: 13 Oct 2014 Posts: 1217 Location: Morrison, CO, USA
|
Posted: Thu Dec 17, 2020 12:27 am Post subject: |
|
|
A follow-up.
As I was doing another task today, I ran the section of code that I had used PACK on intrinsic types. My comment (in this thread) was that it appeared that if the result had fewer elements that the destination array, the remaining elements would be filled with zeroes. While I know this to be the case back in the June/July time frame when this thread started, it is no longer the case.
I must specify that the destination array to hold the PACK operation be the same size as the result. Luckily for me, my result shape is known a priori.
It meant a frantic redelivery of the software to my users (two in one day is a bit embarrassing), but luckily while effect was wrong, it was benign. |
|
Back to top |
|
|
|