Bug in Sort(_DESCENDING_)

[Carlo Hogeveen]

In a macro I need to check if a Sort() did something.
The easiest way seemed to be to compare FileChanged() before and after the Sort().
Unfortunately FileChanged() also changed when the Sort() did nothing.
Further testing revealed that this problem is specific to a descending sort, i.e. Sort(_DESCENDING_).

Below is a demo macro.
It should report 5 identical values, but it does report 5 different ones.
I think this demonstrates a bug in the Sort(_DESCENDING_) statement.

Carlo


proc Main()
integer i = 0
integer tmp_id = 0
PushLocation()
tmp_id = CreateTempBuffer()
for i = Asc('A') to Asc('Z')
AddLine(Chr(i))
endfor
MarkLine(1, NumLines())
for i = 1 to 5
Sort(_DESCENDING_)
Warn('FileChanged()'; i; '='; FileChanged())
endfor
PopLocation()
AbandonFile(tmp_id)
PurgeMacro(CurrMacroFilename())
end Main

[Knud van Eeden]

Reproduced here too.

with friendly greetings

Knud van Eeden

--

---
You received this message because you are subscribed to the Google Groups "SemWare TSE Pro text editor" group.
To unsubscribe from this group and stop receiving emails from it, send an email to semware+u...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/semware/000501dcb5a8%24db66c1b0%2492344510%24%40ecarlo.nl.

[Carlo Hogeveen]

Correction:

Further testing with the demo macro suggests, that the bug does not occur specifically for descending sorts, but for sorting more than 4 lines.

In the demo macro, if I remove the "_DESCENDING_", then the bug still occurs.
If I replace "Z" by "D", which creates only 4 test lines, then the bug disappears.
If I replace that "D" by "E", which creates 5 test lines, then the bug reappears.

The bug being, that if the Sort() statement makes no changes, because the marked lines are already sorted, then Sort() still changes the return value of FileChanged().

Carlo

[S.E. Mitchell]

Hi Carlo,

I have been using a sort function based on J. L. Bentley and M. D.
McIlroy's "Engineering a sort function" from Software Practice and
Experience. This version goes to great lengths to avoid a "bad"
pivot, using Tukey's ninther and other means to improve performance.
This implementation swaps equal keys, which explains why FileChanged()
is triggered even when the final order remains the same.

I did some more research, and found that by using Niklaus Wirth's
version of quicksort published in "Algorithms + Data Structures =
Programs" (1976!), and by changing the pivot calculation from the
median of three to using a (fast: x ^= x << 17; x ^= x >> 13; x ^= x
<< 5) randomly generated index, the O(n**2) case is avoided. In my
tests, this change actually makes the sort faster than
Bentley/McIlroy's version, for TSE at least. Plus, Wirth's version
does not swap already ordered keys, which prevents the file from
changing if it is already in order.

I also added test cases to sanity2 to verify this actually works.

I'm using it now, and it will be in the next version.

> --
>
> ---
> You received this message because you are subscribed to the Google Groups "SemWare TSE Pro text editor" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to semware+u...@googlegroups.com.

> To view this discussion visit https://groups.google.com/d/msgid/semware/000c01dcb5f9%2482d036c0%248870a440%24%40ecarlo.nl.

[Carlo Hogeveen]

Sammy,

I was already impressed by and happy with TSE's Sort()'s speed.
Good to read that besides fixing the problem the new version will be even faster.

> I also added test cases to sanity2 to verify this actually works.

I would like to remind you, that the last time the sort statement and tools were rewritten, I created a test tool for them:
https://ecarlo.nl/tse/DemosAndTests.html#sort_test
Just execute it to run the test.

Carlo

[Knud van Eeden]

FYIO

Quicksort inventor Tony Hoare about his invention of the quicksort in 1959.

https://youtu.be/pJgKYn0lcno?is=zTQgGe6FIUsl4ZmM

with friendly greetings 

Knud van Eeden 

To view this discussion visit https://groups.google.com/d/msgid/semware/CA%2BgEvkb-NcKMqixxruConArtEkDYOyqmb1ZSLCe0qK9RucNEPA%40mail.gmail.com.

[Guy Rouillier]

On Wed, 2026-03-18 at 06:24 -0400, S.E. Mitchell wrote:
> Niklaus Wirth's version of quicksort published in
> "Algorithms + Data Structures = Programs" (1976!)

My data structures class used that brand new book in my 
sophomore year of college, in 1976. :) I remember the 
quicksort algorithm as a homework assignment.

--
Guy Rouillier

[knud van eeden]

I have it also in my collection.

Niklaus Wirth used e.g. syntax diagrams often, applied e.g. in Pascal.

Very good book.

Page 79 quicksort.

with friendly greetings 

Knud van Eeden

Sent from Yahoo Mail on Samsung Galaxy S24 Ultra / 1 terabyte / artificial intelligence

--

---

You received this message because you are subscribed to the Google Groups "SemWare TSE Pro text editor" group.

To unsubscribe from this group and stop receiving emails from it, send an email to semware+u...@googlegroups.com.

To view this discussion visit https://groups.google.com/d/msgid/semware/1cdbe58845f3026dfd9cd75384dc7ba79717639e.camel%40gmail.com.

[zhong zhao]

Classics that stand the test of time.