Re: lhs and rhs in table.sort

[Paul K <paul@...>]

>> 3. (Worst) The sort routine does not return at all. (I have
>> been told this but never actually encountered it.)

> Bubble sort, on the other hand, is especially vulnerable to bad
> comparators, because it tries to sort the entire array on every pass.

I made a "bad" sort comparator once, as described in this thread:
http://lua-users.org/lists/lua-l/2012-06/msg00312.html

The easiest way to trigger "invalid order function for sorting" with
Lua 5.2+ is to run something like this: table.sort({1,2,3,4,5},
function() return true end).

Paul.

On Thu, Aug 27, 2015 at 8:55 AM, Coda Highland <chighland@gmail.com> wrote:
> On Wed, Aug 26, 2015 at 11:58 PM, Dirk Laurie <dirk.laurie@gmail.com> wrote:
>> 2015-08-26 23:47 GMT+02:00 Tim Hill <drtimhill@gmail.com>:
>>
>>> When the sorter calls your compare function, it is asking
>>> “Here are two of the items in the list you told me to sort ..
>>> please tell me which one should come first in the sort?”.
>>
>> You can supply any function you like as long as it satisfies
>> the basic rules of ordering.
>>
>> 1. "A must come before B" and "B must come before A"
>> may not both be true (but may both be false).
>> 2. If "A must come before B" and "B must come before C"
>> are both true, then "C must come before A" may not also
>> be true.
>>
>> If you function is capricious, anything can happen.
>>
>> 1. (Best) The sort routine detects it and give an error.
>> 2. (Bad) The sort routine returns the original items in some
>> meaningless order.
>> 3. (Worst) The sort routine does not return at all. (I have
>> been told this but never actually encountered it.)
>>
>
> 3 can't happen with most sorting algorithms. Merge sort has a fixed
> running time regardless of the input or the comparator. Selection sort
> and insertion sort never move elements after they've been put in their
> final sorted position. Quicksort can have really bad performance
> characteristics in the face of a bad comparator, but its methodology
> protects it from hitting an infinite loop. (I'm not sure about heap
> sort.)
>
> Bubble sort, on the other hand, is especially vulnerable to bad
> comparators, because it tries to sort the entire array on every pass.
> An example of a comparator that would get a bubble sort stuck in an
> infinite loop is one that tries to break ties between equal elements
> by comparing their positions in the array and always saying the one
> with the higher index is the smaller one. (This could, for example, be
> a buggy implementation of a stable-sort comparator; for a stable sort,
> it should break ties by saying the one with the SMALLER index is the
> smaller element.) The bubble sort would swap their positions on every
> pass through the loop and therefore never reach its termination
> condition.
>
> /s/ Adam
>