(sort) semantics: stable ordering of elements compared '=' ?
Posted: Sun Dec 29, 2013 9:02 am
[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:
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).
[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
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).