On 11/30/22 08:30, Nikolay Nikolov wrote:
On 11/30/22 01:57, J. Gareth Moreton via fpc-devel wrote:
Familarity mostly. More people are familiar with quicksort than
introsort. Are there any explicit code examples where quicksort
succeeds and introsort fails? I'm told even Lazarus crashes (or
On 11/30/22 01:57, J. Gareth Moreton via fpc-devel wrote:
Familarity mostly. More people are familiar with quicksort than
introsort. Are there any explicit code examples where quicksort
succeeds and introsort fails? I'm told even Lazarus crashes (or used
to crash), so I'll be interested to s
On Tue, 29 Nov 2022 23:57:14 +
"J. Gareth Moreton via fpc-devel"
wrote:
> Familarity mostly. More people are familiar with quicksort than
> introsort. Are there any explicit code examples where quicksort
> succeeds and introsort fails? I'm told even Lazarus crashes (or used
> to crash),
Familarity mostly. More people are familiar with quicksort than
introsort. Are there any explicit code examples where quicksort
succeeds and introsort fails? I'm told even Lazarus crashes (or used to
crash), so I'll be interested to see what code causes (or caused) it.
If the pivot is one o
On Tue, 29 Nov 2022 15:54:03 +0100
Benito van der Zander via fpc-devel
wrote:
> Hi,
> and the FPC implementation is actually documented to not be stable in
>[...]
> and one can see that it is indeed not stable, if you sort
> ['a','b','A'] case-insensitively, it becomes ['A', 'a','b']
If the cur
On 11/29/22 22:16, J. Gareth Moreton via fpc-devel wrote:
On 29/11/2022 20:03, Nikolay Nikolov via fpc-devel wrote:
if (a
That's the big one that sorting algorithms rely on... the transitive
law. If that is violated, then you cannot guarantee a sorted result.
It doesn't matter if (a < b)
On 29/11/2022 20:03, Nikolay Nikolov via fpc-devel wrote:
if (a
That's the big one that sorting algorithms rely on... the transitive
law. If that is violated, then you cannot guarantee a sorted result.
It doesn't matter if (a < b) or (b < a) return False for equal elements,
or use (a <=b)
On 11/29/22 16:44, Ondrej Pokorny via fpc-devel wrote:
Am 29.11.2022 um 14:25 schrieb Sven Barth via fpc-devel:
For such a comparison function the issue is indeed in the comparison
function, but Nikolay also mentioned "ais the case for equal elements.
I assume this was some kind of typo or re
How so? Heapsort isn't stable either. Is there a variant I'm not aware of?
Kit
On 29/11/2022 16:36, Marco van de Voort via fpc-devel wrote:
On 29-11-2022 17:34, J. Gareth Moreton via fpc-devel wrote:
This is why I hope my own improvement to the version in TArrayHelper
could be used instead:
On 29-11-2022 17:34, J. Gareth Moreton via fpc-devel wrote:
This is why I hope my own improvement to the version in TArrayHelper
could be used instead:
https://gitlab.com/freepascal.org/fpc/source/-/merge_requests/334
Now that I know where Introsort is in the sortalgs.pp unit, I'll see
about
This is why I hope my own improvement to the version in TArrayHelper
could be used instead:
https://gitlab.com/freepascal.org/fpc/source/-/merge_requests/334
Now that I know where Introsort is in the sortalgs.pp unit, I'll see
about improving Introsort there too.
Regarding a stable sort, wha
More like a variation of that: TimSort - but that's rather a beast to
implement properly and efficient.
Am 29.11.2022 um 14:41 schrieb J. Gareth Moreton via fpc-devel:
Quicksort is not inherently stable because of what happens if a value
is equal to the pivot - more specifically, which of the
That is not a very good IntroSort to be honest. It is missing using
InsertionSort for small numbers and it does not do the median-of-3 pivot
selection.
Am 29.11.2022 um 09:22 schrieb Nikolay Nikolov via fpc-devel:
On 11/24/22 20:51, J. Gareth Moreton via fpc-devel wrote:
Hi everyone,
I just
Hi,
and the FPC implementation is actually documented to not be stable in
the code:
{
QuickSort
Average performance: O(n log n)
Worst performance: O(n*n)
Extra memory use: O(log n) on the stack
Stable: no
Additional notes: Uses the middle element asthe pivot. This makes it work
well also on a
Where exactly can that stable quicksort be found? rtl/inc/sortbase.pp
looks pretty much like standard quicksort to me.
Am 29.11.2022 um 11:08 schrieb Sven Barth via fpc-devel:
J. Gareth Moreton via fpc-devel
schrieb am Di., 29. Nov. 2022, 10:09:
Surely that's a bug in the comparison func
Am 29.11.2022 um 14:25 schrieb Sven Barth via fpc-devel:
For such a comparison function the issue is indeed in the comparison
function, but Nikolay also mentioned "ais the case for equal elements.
I assume this was some kind of typo or reasoning error because
"acompare function is correct. And
Quicksort is not inherently stable because of what happens if a value is
equal to the pivot - more specifically, which of the identical values is
selected as the pivot - for example, if you try to sort a list of
identical values, they will inevitably change order because each stage
will move al
Ondrej Pokorny via fpc-devel schrieb am
Di., 29. Nov. 2022, 11:39:
> Am 29.11.2022 um 11:08 schrieb Sven Barth via fpc-devel:
>
> J. Gareth Moreton via fpc-devel schrieb
> am Di., 29. Nov. 2022, 10:09:
>
>> Surely that's a bug in the comparison functions that should be fixed and
>> not something
Am 29.11.2022 um 11:08 schrieb Sven Barth via fpc-devel:
J. Gareth Moreton via fpc-devel
schrieb am Di., 29. Nov. 2022, 10:09:
Surely that's a bug in the comparison functions that should be
fixed and
not something that can be blamed on introsort. If a comparison
function
i
J. Gareth Moreton via fpc-devel schrieb am
Di., 29. Nov. 2022, 10:09:
> Surely that's a bug in the comparison functions that should be fixed and
> not something that can be blamed on introsort. If a comparison function
> is faulty, then pretty nuch any sorting algorithm can be considered to
> ha
Hmmm, that's a problem! Fair enough.
Kit
On 29/11/2022 09:21, Michael Van Canneyt via fpc-devel wrote:
On Tue, 29 Nov 2022, J. Gareth Moreton via fpc-devel wrote:
Surely that's a bug in the comparison functions that should be fixed
and not something that can be blamed on introsort. If a c
On Tue, 29 Nov 2022, J. Gareth Moreton via fpc-devel wrote:
Surely that's a bug in the comparison functions that should be fixed and
not something that can be blamed on introsort. If a comparison function
is faulty, then pretty nuch any sorting algorithm can be considered to
have unpredicta
Surely that's a bug in the comparison functions that should be fixed and
not something that can be blamed on introsort. If a comparison function
is faulty, then pretty nuch any sorting algorithm can be considered to
have unpredictable behaviour.
Kit
On 29/11/2022 08:22, Nikolay Nikolov via f
On 11/24/22 20:51, J. Gareth Moreton via fpc-devel wrote:
Hi everyone,
I just need to touch on the knowledge base. What tests exist that
test the functionality of rtl/inc/sortbase.pp? As Olly suggested, I'm
looking at creating Introsort for this unit as well, but I need to
know if such a u
Stefan Glienke via fpc-devel schrieb am
Mo., 28. Nov. 2022, 12:39:
> In Delphi that would be the
> https://docwiki.embarcadero.com/Libraries/Alexandria/en/System.GetTypeKind
> intrinsic - I could not find that one in the 3.2.0 feature list.
>
That one is also supported since 3.2.0, though it see
That could work - could be interesting to experiment with.
Kit
On 28/11/2022 11:43, Stefan Glienke via fpc-devel wrote:
Nevermind - I guess there is:
https://www.freepascal.org/docs-html/rtl/system/gettypekind.html
Am 28.11.2022 um 12:35 schrieb Stefan Glienke via fpc-devel:
In Delphi tha
Nevermind - I guess there is:
https://www.freepascal.org/docs-html/rtl/system/gettypekind.html
Am 28.11.2022 um 12:35 schrieb Stefan Glienke via fpc-devel:
In Delphi that would be the
https://docwiki.embarcadero.com/Libraries/Alexandria/en/System.GetTypeKind
intrinsic - I could not find that
In Delphi that would be the
https://docwiki.embarcadero.com/Libraries/Alexandria/en/System.GetTypeKind
intrinsic - I could not find that one in the 3.2.0 feature list.
Am 28.11.2022 um 11:17 schrieb J. Gareth Moreton via fpc-devel:
Well that spoils that idea! Is there any way to determine if
Well that spoils that idea! Is there any way to determine if it's
pointer-based so you can swap references instead of going through the
whole penalty of creating and destroying temporary objects?
Kit
On 28/11/2022 10:07, Sven Barth wrote:
J. Gareth Moreton via fpc-devel
schrieb am Mo., 28.
J. Gareth Moreton via fpc-devel schrieb am
Mo., 28. Nov. 2022, 11:01:
> Just want to clarify something... if a type is managed, can it be safely
> typecast to a pointer in all instances and on all platforms? (The
> purpose being so if I wanted to swap two items, so there's no overall
> change in
This is something I want to experiment with now. Still waiting on
approval of the TArrayHelper sort merge request though before I start
playing around with reference counts.
Just want to clarify something... if a type is managed, can it be safely
typecast to a pointer in all instances and on
On Mon, 28 Nov 2022, Sven Barth via fpc-devel wrote:
Stefan Glienke via fpc-devel schrieb am
Mo., 28. Nov. 2022, 00:20:
Probably not unless FPC has something similar to
https://docwiki.embarcadero.com/Libraries/Alexandria/en/System.IsManagedType
(that function among a few others is compil
Stefan Glienke via fpc-devel schrieb am
Mo., 28. Nov. 2022, 00:20:
> Probably not unless FPC has something similar to
>
> https://docwiki.embarcadero.com/Libraries/Alexandria/en/System.IsManagedType
> (that function among a few others is compiletime evaluated).
>
It's supported since 3.2.0: http
Probably not unless FPC has something similar to
https://docwiki.embarcadero.com/Libraries/Alexandria/en/System.IsManagedType
(that function among a few others is compiletime evaluated).
Am 25.11.2022 um 18:57 schrieb J. Gareth Moreton via fpc-devel:
Indeed. I'm just trying to think if there's
Indeed. I'm just trying to think if there's a way that that can be
implemented in a cross-platform way, or if there's a wa to identify if a
generic type is a pointer/managed type.
Kit
On 25/11/2022 16:00, Stefan Glienke via fpc-devel wrote:
>From experience I can tell that IntroSort is fast
From experience I can tell that IntroSort is fast enough.
The main performance improvement usually comes from treating anything that is a
managed type such as strings as Pointers - instead of three string assignments
that cause a bunch of unnecessary atomic operations you then just have 3
point
These are nice but don't actually use the code in rtl/inc/sortbase.pp -
maybe they can be adapted though.
Kit
On 25/11/2022 10:10, Marco Borsari via fpc-devel wrote:
On Thu, 24 Nov 2022 18:51:12 +
"J. Gareth Moreton via fpc-devel" wrote:
Hi everyone,
I just need to touch on the knowled
On Thu, 24 Nov 2022 18:51:12 +
"J. Gareth Moreton via fpc-devel" wrote:
> Hi everyone,
>
> I just need to touch on the knowledge base. What tests exist that test
> the functionality of rtl/inc/sortbase.pp? As Olly suggested, I'm
> looking at creating Introsort for this unit as well, but
38 matches
Mail list logo
