Next: Searching Up: Lists and Arrays Revisited Previous: Zippable Commands

# Sorting

For arrays with elements of an homogeneous type, it is a simple matter to place them in ascending order with Darwin's sort function.
```> numbers := [1971, -1554, 1449, -45, 9000, 2001];
> sort(numbers);
[-1554, -45, 1449, 1971, 2001, 9000]
```
The list may contain elements of any type; the only requirement is that the elements are comparable, that is, the <, >, <=, <> and >= operators are applicable. For real values, these operators act in the typical manner. For string objects, the ordering is lexicographic. If, instead, we desire the elements placed in descending order, we must pass a second argument to sort.
```> sort(numbers, x -> -x);
[9000, 2001, 1971, 1449, -45, -1554]
```
The choice of the name x in the above example is irrelevant, any legal Darwin variable name will suffice. The name x represents one item of the list numbers. In this case, Darwin first negates each element of numbers and then performs the sort operation on the resulting vector.

The x -> -x is simply syntatic sugar for a procedure definition. We could re-write this call as follows:

```> neg := proc(x)
>   return(-x);
> end;
> sort(numbers, neg);
[9000, 2001, 1971, 1449, -45, -1554]
```
If we issue
```> sort(numbers, x -> -abs(x));
[9000, 2001, 1971, -1554, 1449, -45]
```
we receive back the vector consisting of the absolute values of numbers in descending order. Now suppose we are given a multi-dimensional array of heterogeneous data such as the following4.1
```> ReadProgram('Sample/arrays'):
> print(classics);
[
[Joseph Felsenstein,
Phylogenies from molecular sequences:  inference and reliability,
Annual Revue of Genetics, 1988, 22, 521--565]
[Smith, Temple F. and Waterman, Michael S.,
Identification of common molecular subsequences, J. Mol. Biol., 1981, 147,
195--197]
[Dayhoff, Margaret O. and Schwartz, R. M. and Orcutt, B. C.,
A model for evolutionary change in proteins,
Atlas of Protein Sequence and Structure, 1978, 5, 345--352]
[Needleman, S. B. and Wunsch, C. D., A general method applicable to the search \
for similarities in the amino acid sequence of two proteins, J. Mol. Biol., 1970
, 48, 443--453]
]
> length(classics);
4
```
where each entry is composed of an ordered list of six items. The field order is authors' names, title of paper, journal, year, volume and page numbers. To sort the list into alphabetical order by authors' names, we need only specify the correct field of classics.
```> print(sort( classics, x -> x[1] ));    # (ascending) sort by author's name
[
[Dayhoff, Margaret O. and Schwartz, R. M. and Orcutt, B. C.,
A model for evolutionary change in proteins,
Atlas of Protein Sequence and Structure, 1978, 5, 345--352]
[Joseph Felsenstein,
Phylogenies from molecular sequences:  inference and reliability,
Annual Revue of Genetics, 1988, 22, 521--565]
[Needleman, S. B. and Wunsch, C. D., A general method applicable to the search \
for similarities in the amino acid sequence of two proteins, J. Mol. Biol., 1970
, 48, 443--453]
[Smith, Temple F. and Waterman, Michael S.,
Identification of common molecular subsequences, J. Mol. Biol., 1981, 147,
195--197]
]
> print(sort( classics, x -> -x[1] ));   # (descending) sort by
author's name
(a system bug - must be fixed)
> print(sort( classics, x -> x[4] ));    # sort by year
[
[Needleman, S. B. and Wunsch, C. D., A general method applicable to the search \
for similarities in the amino acid sequence of two proteins, J. Mol. Biol., 1970
, 48, 443--453]
[Dayhoff, Margaret O. and Schwartz, R. M. and Orcutt, B. C.,
A model for evolutionary change in proteins,
Atlas of Protein Sequence and Structure, 1978, 5, 345--352]
[Smith, Temple F. and Waterman, Michael S.,
Identification of common molecular subsequences, J. Mol. Biol., 1981, 147,
195--197]
[Joseph Felsenstein,
Phylogenies from molecular sequences:  inference and reliability,
Annual Revue of Genetics, 1988, 22, 521--565]
]
```
Note, however, that the original copy of the array classics is unchanged. The sort statement returns a new copy of the array.

Next: Searching Up: Lists and Arrays Revisited Previous: Zippable Commands
Gaston Gonnet
1998-09-15