sort a list of values or a polynomial - Maple Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Programming : Operations : Ordering : sort

sort - sort a list of values or a polynomial

Calling Sequence

sort(L)

sort(L, output=out)

sort(L, `>`, output=out)

sort(L, `<`, output=out)

sort(L, address, output=out)

sort(L, length, output=out)

sort(L, lexorder, output=out)

sort(L, F)

sort(L, comptype = F)

sort(L, F, output=out)

sort(L, comptype = F, output=out)

sort(A)

sort(A, V, opt)

sort(A, order=o, opt)

Parameters

L

-

list, Vector, or one-dimensional Array; values to be sorted

out

-

(optional) sorted or permutation or [sorted, permutation]

F

-

(optional) symbol or Boolean function of two arguments; sort ordering

A

-

algebraic; expression to be sorted

V

-

(optional) variables

o

-

(optional) monomial order

opt

-

(optional) either ascending or descending

Description

• 

By default, the sort command sorts the elements of a list, Vector, or one-dimensional Array, L, into ascending order and sorts the terms of polynomials in an algebraic expression A into descending order.

• 

sort is stable when applied to L. This means that equal elements are ordered by their position in L. In other words, the relative order of equal elements is maintained.

• 

If F is given, it specifies the ordering for sorting elements.

– 

`<`:  If F is the symbol `<` or numeric, then L is sorted in ascending numerical order.  L must contain elements of type({numeric, real_infinity}),

– 

`>`:  If F is the symbol `>`, then L is sorted into descending numerical order.

– 

address:  If F is the symbol address, then the elements are sorted by address (a non-deterministic run-time specific property of the underlying data structure).

– 

length:  If F is the symbol length, then the elements are sorted by length where length is as determined by the length function.

– 

lexorder:  If F is the symbol lexorder or string, then lists of strings or symbols are sorted into lexicographic order.

– 

'lexorder'[n]:  If L is a list of lists and F is the indexed symbol 'lexorder'[n], where n is a positive integer, then L is sorted into lexicographic order based on the nth element of each sublist of L.

– 

Otherwise, F must be a Boolean-valued function of two arguments.  Specifically, Fa&comma;b returns false if and only if b must precede a in the sorted output.  That is Fa&comma;b is a non-strict less than comparison function.  In addition, Fa&comma;b must be defined for all pairs a&comma;b for a and b in the input structure and Fa&comma;b must be transitive, that is, if Fa&comma;b&equals;true and Fb&comma;c&equals;true then Fa&comma;c&equals;true.

• 

By specifying comptype=F, different styles of comparison functions can be given to sort.  The supported values for comptype are:

– 

nonstrict: the comparison function F is a non-strict less than function, as described above.

– 

strict: the comparison function F is a strict less than function.  That is Fa&comma;b returns true if and only if a must precede b in the sorted output.  F must still be defined for all pairs of inputs and be transitive, as described above.  This argument is necessary if you want to specify a less than or equal to comparison function and want stable sorting.  Specifying a strict less than function without using the strict option will result in an non-stable, sorted output.

– 

key: the function F maps each element in L to a key value.  L is sorted by sorting the corresponding keys.  Using a key function is preferable to a comparison function because the key function is called On times, whereas a comparison function will be called Onlogn times.  This is generally faster.  In addition, sorting the keys may be done in parallel, whereas this may not be possible with a comparison function.

• 

If no ordering function F is specified, a list, Vector, or Array with elements of type{numeric, real_infinity} is sorted into increasing numerical order.  The default sorting order when all elements are strings or symbols is lexicographical order. Otherwise, elements of L are sorted by the same rules used to sort sets.  This mixed-element sort is optimized to balance speed and "niceness" of the result.  Data-types of the same structure will be grouped together; within that internal object length is used as the next criteria; further down, individual properties such as numeric order are used when comparing elements during the sort process.

• 

If an argument output=permutation is supplied, then sort does not return the sorted argument, but the permutation that would be applied to the argument in order to sort it. The permutation is given as a list of integers: the ith entry of the permutation is the integer j such that the jth entry of L would occur at the ith position in the sorted argument. This means that if a&equals;sortL&comma;&apos;output&equals;permutation&apos; for a list L, then sortL could be obtained as La. (For 1-dimensional Arrays A, there may be an offset between the jth entry and the entry obtained as A[j], but the correctly sorted result can be obtained using programmer indexing as Aa.)

  

If an argument output = sorted is supplied, sort returns the sorted argument. This is the default behavior. In order to obtain both the sorted argument and the permutation, one can supply the argument output = [sorted, permutation]. This will return a sequence of two elements, the first being the sorted argument, the second the permutation.

• 

In Maple, polynomials are not automatically stored in sorted order. They are stored in the order they were first created and printed in the order they are stored. The sort command can be used to sort polynomials.

  

Note: Sorting polynomials is a destructive operation: the input polynomial is sorted "in-place".

• 

If V is given, it specifies the variable ordering to be used when sorting polynomials. It can be a name, a function, or a list or set of names (for the multivariate case).

  

All polynomials in the expression A are sorted into decreasing order in V. If V is a list or set then polynomials in V are sorted in total degree with ties broken by lexicographic order (this is called graded lexicographic order). If neither V nor o is specified then the indets appearing in A and graded lexicographic order are used.

• 

Other monomial orders can be specified by using the order=o calling sequence. The supported orders are:

  

plex(x1, ..., xn) - lexicographic order

  

grlex(x1, ..., xn) - graded lexicographic order

  

tdeg(x1, ..., xn) - graded reverse lexicographic order

  

for indeterminates x1, ..., xn. For a description of these orders, see Monomial orders for multivariate polynomials.

• 

When sorting polynomials the optional argument ascending or descending may be specified to put the terms into ascending or descending order, respectively. The default is descending order, which puts higher-degree terms before lower-degree terms.

• 

The sorting algorithm used for sorting lists is a recursive implementation of Merge sort with early detection of sorted sequences. The sorting algorithm used for sorting polynomials is an in-place Shell sort. Lexicographic ordering of strings and symbols assumes the collating sequence of the US-ASCII character set.

Thread Safety

• 

The sort command is thread safe as of Maple 15, provided that a polynomial is not being sorted.  Sorting polynomials is not thread safe.

• 

For more information on thread safety, see index/threadsafe.

Examples

sort2&comma;1&comma;3

1&comma;2&comma;3

(1)

sort2&comma;1&comma;3&comma;numeric

1&comma;2&comma;3

(2)

sort2&comma;1&comma;3&comma;`>`

3&comma;2&comma;1

(3)

sort1&plus;x&plus;x2

x2&plus;x&plus;1

(4)

sortc&comma;a&comma;d&comma;lexorder

a&comma;c&comma;d

(5)

sorta&comma;ba&comma;aaa&comma;aa&comma;length

a&comma;ba&comma;aa&comma;aaa

(6)

sorta&comma;ax&comma;bb&comma;bf&comma;address

ax&comma;bb&comma;bf&comma;a

(7)

z1:=three&comma;four&comma;two

z1:=three&comma;four&comma;two

(8)

z2:=3&comma;4&comma;2

z2:=3&comma;4&comma;2

(9)

permutation:=sortz2&comma;&apos;output&equals;permutation&apos;

permutation:=3&comma;1&comma;2

(10)

z1permutation

two&comma;three&comma;four

(11)

z3:=five&comma;eight&comma;two&comma;four

z3:=fiveeighttwofour

(12)

z4:=Array5&comma;8&comma;2&comma;4

z4:=5824

(13)

result&comma;permutation2:=sortz4&comma;&apos;output&equals;sorted&comma;permutation&apos;

result&comma;permutation2:=2458&comma;3&comma;4&comma;1&comma;2

(14)

result

2458

(15)

z3permutation2

twofourfiveeight

(16)

f:=4x3&plus;5x2z2&plus;2xy2z&plus;1

f:=5x2z2&plus;2xy2z&plus;4x3&plus;1

(17)

sortf&comma;x&comma;y&comma;z

5x2z2&plus;2xy2z&plus;4x3&plus;1

(18)

sortf&comma;x&comma;y&comma;z&comma;ascending

1&plus;4x3&plus;2xy2z&plus;5x2z2

(19)

sortf&comma;order&equals;grlexx&comma;y&comma;z

5x2z2&plus;2xy2z&plus;4x3&plus;1

(20)

sortf&comma;order&equals;tdegx&comma;y&comma;z

2xy2z&plus;5x2z2&plus;4x3&plus;1

(21)

sortf&comma;order&equals;plexx&comma;y&comma;z

4x3&plus;5x2z2&plus;2xy2z&plus;1

(22)

sortf&comma;order&equals;plexx&comma;y&comma;z&comma;descending

4x3&plus;5x2z2&plus;2xy2z&plus;1

(23)

sortf&comma;order&equals;plexx&comma;y&comma;z&comma;ascending

1&plus;2xy2z&plus;5x2z2&plus;4x3

(24)

sorty&plus;xyx&comma;x

x&plus;yx&plus;y

(25)

sortax&plus;by&plus;cx2&comma;x

cx2&plus;ax&plus;by

(26)

sortax&plus;by&plus;cx2&comma;x&comma;ascending

by&plus;ax&plus;cx2

(27)

The powers in an algebraic expression do not have to be positive integers. They can be negative integers or fractions.

f:=ax2&plus;bx6&plus;cx4&plus;dx32

f:=ax2&plus;bx6&plus;cx4&plus;dx3&sol;2

(28)

sortf&comma;x

dx3&sol;2&plus;ax2&plus;cx4&plus;bx6

(29)

l:=LibraryTools:-ShowContents&colon;

sl:=sortl&comma;lexorder1&colon;

sl1..10

#msup(mi("a"),mo("+")).m&comma;2015&comma;2&comma;17&comma;22&comma;21&comma;39&comma;28392932&comma;43&comma;#msup(mi("a"),mo("−")).m&comma;2015&comma;2&comma;17&comma;22&comma;21&comma;39&comma;85268546&comma;46&comma;%?.m&comma;2015&comma;2&comma;17&comma;22&comma;13&comma;32&comma;76659395&comma;35&comma;%T.m&comma;2015&comma;2&comma;17&comma;22&comma;13&comma;32&comma;85302428&comma;35&comma;∞.m&comma;2015&comma;2&comma;17&comma;22&comma;13&comma;41&comma;75955457&comma;36&comma;&where.m&comma;2015&comma;2&comma;17&comma;22&comma;18&comma;5&comma;71126257&comma;385&comma;-.m&comma;2015&comma;2&comma;17&comma;22&comma;18&comma;24&comma;24098648&comma;182&comma;....m&comma;2015&comma;2&comma;17&comma;22&comma;13&comma;32&comma;29341562&comma;36&comma;..m&comma;2015&comma;2&comma;17&comma;22&comma;13&comma;39&comma;60244625&comma;1675&comma;/.m&comma;2015&comma;2&comma;17&comma;22&comma;18&comma;24&comma;86519625&comma;182

(30)

An example of stable sorting.  Sort based on the first element in the sublist. Notice that sublists whose first elements are equal are ordered based on their position in the input list.

sort1&comma;1&comma;2&comma;1&comma;3&comma;1&comma;1&comma;2&comma;2&comma;2&comma;3&comma;2&comma;1&comma;3&comma;2&comma;3&comma;3&comma;3&comma;x&comma;y&rarr;x1y1

1&comma;1&comma;1&comma;2&comma;1&comma;3&comma;2&comma;1&comma;2&comma;2&comma;2&comma;3&comma;3&comma;1&comma;3&comma;2&comma;3&comma;3

(31)

Specifying the strict option allows the use of a strict less than comparison function while still producing stable sorting.

sort1&comma;1&comma;2&comma;1&comma;3&comma;1&comma;1&comma;2&comma;2&comma;2&comma;3&comma;2&comma;1&comma;3&comma;2&comma;3&comma;3&comma;3&comma;strict&equals;x&comma;y&rarr;x1<y1

1&comma;1&comma;1&comma;2&comma;1&comma;3&comma;2&comma;1&comma;2&comma;2&comma;2&comma;3&comma;3&comma;1&comma;3&comma;2&comma;3&comma;3

(32)

This example could also be sorted using the key option.

sort1&comma;1&comma;2&comma;1&comma;3&comma;1&comma;1&comma;2&comma;2&comma;2&comma;3&comma;2&comma;1&comma;3&comma;2&comma;3&comma;3&comma;3&comma;key&equals;x&rarr;x1

1&comma;1&comma;1&comma;2&comma;1&comma;3&comma;2&comma;1&comma;2&comma;2&comma;2&comma;3&comma;3&comma;1&comma;3&comma;2&comma;3&comma;3

(33)

See Also

degree, Groebner/MonomialOrders, indets, length, lexorder, list, polynom


Download Help Document

Was this information helpful?



Please add your Comment (Optional)
E-mail Address (Optional)
What is ? This question helps us to combat spam