Re: table.sort: invalid order function for sorting

Thanks for replies, Francisco!

(bsearch is lame! cool kids code interpolation search with O(1) asymptotic!)

Let's talk about sorts!

Tony Hoare invented and published what is known as QuickSort in 1960.
(My university's mentor independently invented it in similar years
but was too late about publishing. He was sad about this all his life. :( )

You have array segment of items. You select some "pivot" item from segment
and split segment into several segments according to items relation to
that pivot item. Then you do recursive calls for them if it's needed.

Tricky part is produce that sub-segments inside original array segment
using constant memory. It's known as "partitioning".

Hoare's partitioning was two-way: "<" and ">=" (not "<").

Edsger Dijkstra published three-way partitioning in 1976.
There are "<", "==" and ">" parts. Profit here is that you exclude
sub-segments with equal values. They are never touched after initial
comparison with pivot and relocation.

Two-way partitioning requires just two-way comparator.
That's practically easy.

Three-way unsurprisingly requires three-way comparator.
That's mathematically nice.

But none of them uses "is_equal == not is_less(a, b) and not is_less(b, a)"
because it's two calls and is not needed.

(My note that you need two boolean comparators is wrong. Sorry about that.)


I'm stressing out that calling comparison function is a lot more
costly than executing algorithm. We are no longer sorting integers.

Execution time of comparator eclipse any cool algorithm coding in C.
We should try to minimize number of comparison calls.

And so three-way partitioning inherently requires less calls
of comparison function when there are some "equal" items.
But it requires three-way comparator (aka "spaceship operator").


I've implemented like 6-8 different sorts as programming assignments
in university. (But never needed them in career.) You have different
background. Have you ever met the case when you need to code effective
sorting in practice?

-- Martin

-- 
You received this message because you are subscribed to the Google Groups "lua-l" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [email protected].
To view this discussion visit https://groups.google.com/d/msgid/lua-l/4cd562dd-5361-42e6-a3f8-252b43d0f6eb%40disroot.org.