(sort) semantics: stable ordering of elements compared '=' ?

Q&A's, tips, howto's
Locked
hartrock
Posts: 136
Joined: Wed Aug 07, 2013 9:37 pm

(sort) semantics: stable ordering of elements compared '=' ?

Post by hartrock »

[2. Update 2014-01-02]: it has a stable ordering (see Lutz' reply).
[1. Update 2014-01-02]: added 'stable' to title (see replies below).

Example:

Code: Select all

> (setq l '( ("0" 3) ("1" 3) ("2" 3) ("3" 3) ("4" 3)  ("foo" 2) ("bar" 4) ("foo" 1) ("bar" 5)  ("5" 3) ("6" 3) ("7" 3) ("8" 3) ("9" 3)))
(("0" 3) ("1" 3) ("2" 3) ("3" 3) ("4" 3) ("foo" 2) ("bar" 4) ("foo" 1) ("bar" 5) ("5" 3) ("6" 3) ("7" 3) ("8" 3) ("9" 3))
> (sort (copy l) (fn (x y) (<= (last x) (last y))))
(("foo" 1) ("foo" 2) ("0" 3) ("1" 3) ("2" 3) ("3" 3) ("4" 3) ("5" 3) ("6" 3) ("7" 3) ("8" 3) ("9" 3) ("bar" 4) ("bar" 5))
> (sort (copy l) (fn (x y) (< (last x) (last y))))
(("foo" 1) ("foo" 2) ("9" 3) ("8" 3) ("7" 3) ("6" 3) ("5" 3) ("4" 3) ("3" 3) ("2" 3) ("1" 3) ("0" 3) ("bar" 4) ("bar" 5))
> ;;
> (= (sort (copy l) (fn (x y) (< (last x) (last y)))) (reverse (sort (copy l) (fn (x y) (>= (last x) (last y))))))
true
> (= (sort (copy l) (fn (x y) (> (last x) (last y)))) (reverse (sort (copy l) (fn (x y) (<= (last x) (last y))))))
true
Observations:
Sorting with
- '<=' or '>=' does not change the order of elements compared '=';
- '<=' results into reversed elements of sorting with '>', and
- '>=' resutls into reversed elements of sorting with '<' .

Is this behavior guaranteed?
In the (sort) section of the manual there is no statement regarding the '=' case.
Sorting behavior of elements compared equal could be different without violating their sorting relation '<', '<=', '>' or '>=': in principle the ordering amongst elements compared '=' could be *arbitrary* after sorting.

Motivation:
I've started sorting a similar list with '<' and handled '=' elements specifically, because their order had changed compared with the original list (without being surprised about this effect). After that I've seen, that sorting with '<=' does exactly what I wanted (keeping original ordering of elements compared '='), without specific handling of the '=' case.
Question remains, if this can be exploited or is just an implementation incident (which may change in a later newLISP version).
Last edited by hartrock on Thu Jan 02, 2014 3:38 pm, edited 4 times in total.

Astrobe
Posts: 43
Joined: Mon Jan 11, 2010 9:41 pm

Re: (sort) semantics: ordering of elements compared '=' ?

Post by Astrobe »

This is a property named stability (https://en.wikipedia.org/wiki/Sorting_a ... #Stability), which depends on the sorting algorithm.

hartrock
Posts: 136
Joined: Wed Aug 07, 2013 9:37 pm

Re: (sort) semantics: ordering of elements compared '=' ?

Post by hartrock »

Astrobe wrote:This is a property named stability (https://en.wikipedia.org/wiki/Sorting_a ... #Stability), which depends on the sorting algorithm.
Thanks to the pointer: this is the point of my question.
I've updated the post title accordingly.

Condensed the question could be: is (sort) stable according the link above?

Lutz
Posts: 5289
Joined: Thu Sep 26, 2002 4:45 pm
Location: Pasadena, California
Contact:

Re: (sort) semantics: stable ordering of elements compared '

Post by Lutz »

Yes, it is a stable binary (two groups) merge-sort with almost linear O(n log2 n) performance preserving the order of adjacent elements which are equal when using <= or >=.


ps: this will be added to the manual

Locked