std-sort, std-stable-sort,std-fast-sort


Synopsis

(std-sort <lst> <less-pred>)

(std-stable-sort <lst> <less-pred>) ; keeps order intact

(std-fast-sort <lst> <less-pred>) ; may remove duplicates

Description

All return a sorted list, sort order determined by the less predicate. Increasing numbers should be sorted with <

Most of the time you may use STD-FAST-SORT, if you accept the restrictions.

STD-SORT may be slower than STD-FAST-SORT but keeps all elements of the list. Duplicates are not removed.

STD-STABLE-SORT maybe slower than STD-SORT and STD-FAST-SORT but keeps the elements in its original order. Only on VILL and VLISP it is different from std-sort, which is the same as STD-FAST-SORT.

STD-FAST-SORT may remove duplicate entries. (implementation dependent). To keep all elements use STD-SORT instead. This was introduced with VLX-SORT and VL-SORT. On VILL and VLISP this is the same as STD-SORT.

All the functions besides the internal VL[X]-SORT use a stable and iterative merge-sort algorithm, which is equally fast for ordered or random lists and has no stack overflow problems.

So STD-STABLE-SORT is for now the same as std-sort, until a faster but not stable sort algorithm is found. In plain AutoLISP even all three of them are the same.

Examples

(std-fast-sort '(2 0 1 2 3 4 0) '<)
=> (0 1 2 3 4)
or (0 0 1 2 2 3 4)

(std-stable-sort '(2 0 1 2 3 4 0) '<)      => (0 0 1 2 2 3 4)
(std-fast-sort '("2" "1" "3" "4" "0") '<)  => ("0" "1" "2" "3" "4")
(std-sort pointlist '(lambda (x y) (< (car x) (car y))))

=> pointlist sorted according increasing x-value

Arguments

lst: any proper list

less-pred: a function or lambda list accepting 2 arguments, and returning nil if the second argument is lower or equal than the first. For numbers and strings use '<.

Return Value

A sorted list. STD-SORT and STD-STABLE SORT return a list of the same length as the argument.

Side Effects

Not confirmed yet: STD-FAST-SORT is the only function which might destructivly change the original list (in Vital Lisp or Visual Lisp). So if you want to keep the original list intact, use a copy of the list, use STD-COPY-TREE, just for safety reasons.

The predicate also might produce side-effects, but this is generally not a good idea!

Module

(std-require 'STDLIST)

Defined in STDLIST