21.14 Sorting Lists

sorts the list list in increasing order. In the first form Sort uses the operator < to compare the elements. In the second form Sort uses the function func to compare elements. func must be a function taking two arguments that returns true if the first is regarded as strictly smaller than the second, and false otherwise.

Sort does not return anything, it just changes the argument list. Use ShallowCopy (see ShallowCopy) if you want to keep list. Use Reversed (see Reversed) if you want to get a new list sorted in decreasing order.

It is possible to sort lists that contain multiple elements which compare equal. It is not guaranteed that those elements keep their relative order, i.e., Sort is not stable.

gap> list := [ 5, 4, 6, 1, 7, 5 ];; Sort( list ); list;
[ 1, 4, 5, 5, 6, 7 ]
gap> list := [ [0,6], [1,2], [1,3], [1,5], [0,4], [3,4] ];;
gap> Sort( list, function(v,w) return v*v < w*w; end ); list;
[ [ 1, 2 ], [ 1, 3 ], [ 0, 4 ], [ 3, 4 ], [ 1, 5 ], [ 0, 6 ] ]
# sorted according to the Euclidian distance from [0,0]
gap> list := [ [0,6], [1,3], [3,4], [1,5], [1,2], [0,4], ];;
gap> Sort( list, function(v,w) return v[1] < w[1]; end ); list;
[ [ 0, 6 ], [ 0, 4 ], [ 1, 3 ], [ 1, 5 ], [ 1, 2 ], [ 3, 4 ] ]
# note the random order of the elements with equal first component

sorts the list list1 in increasing order just as Sort (see Sort) does. In parallel it applies the same exchanges that are necessary to sort list1 to the list list2, which must of course have at least as many elements as list1 does.

gap> list1 := [ 5, 4, 6, 1, 7, 5 ];;
gap> list2 := [ 2, 3, 5, 7, 8, 9 ];;
gap> SortParallel( list1, list2 );
gap> list1;
[ 1, 4, 5, 5, 6, 7 ]
gap> list2;
[ 7, 3, 2, 9, 5, 8 ]  # [ 7, 3, 9, 2, 5, 8 ] is also possible

sorts the list list and returns the permutation that must be applied to list to obtain the sorted list.

Permuted (see Permuted) allows you to rearrange a list according to a given permutation.

gap> list1 := [ 5, 4, 6, 1, 7, 5 ];;
gap> list2 := ShallowCopy( list1 );;
gap> perm := Sortex( list1 );
(1,3,5,6,4)
gap> list1;
[ 1, 4, 5, 5, 6, 7 ]
gap> Permuted( list2, perm );
[ 1, 4, 5, 5, 6, 7 ]

SortingPerm returns the same as Sortex( list ) but does not change the argument.

gap> list1 := [ 5, 4, 6, 1, 7, 5 ];;
gap> list2 := ShallowCopy( list1 );;
gap> perm := SortingPerm( list1 );
(1,3,5,6,4)
gap> list1;
[ 5, 4, 6, 1, 7, 5 ]
gap> Permuted( list2, perm );
[ 1, 4, 5, 5, 6, 7 ]

Currently GAP uses shellsort.

[Top] [Previous] [Up] [Next] [Index]