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
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
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
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
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
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
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,
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
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
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
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
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.
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
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
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
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
>
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
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
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
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
24 matches
Mail list logo
