OpenEuphoria: Euphoria v4.1

# OpenEuphoria Manual

## Euphoria v4.1

routine or constant name search

| Up |  |  | TOC | Index
<< 7 Included Tools | < 8.17 Serialization of Euphoria Objects | Up: 8 API Reference | 8.19 Locale Routines > | 9 Release Notes >>

## 8.18 Sorting

### 8.18.1 Constants

#### 8.18.1.1 ASCENDING

    include std/sort.e
    namespace stdsort
    public constant ASCENDING

Ascending sort order, always the default.

When a sequence is sorted in `ASCENDING` order, its first element is the smallest as per the sort order and its last element is the largest

#### 8.18.1.2 NORMAL_ORDER

    include std/sort.e
    namespace stdsort
    public constant NORMAL_ORDER

The normal sort order used by the custom comparison routine.

#### 8.18.1.3 DESCENDING

    include std/sort.e
    namespace stdsort
    public constant DESCENDING

Descending sort order, which is the reverse of `ASCENDING`.

#### 8.18.1.4 REVERSE_ORDER

    include std/sort.e
    namespace stdsort
    public constant REVERSE_ORDER

Reverses the sense of the order returned by a custom comparison routine.

### 8.18.2 Routines

#### 8.18.2.1 sort

    include std/sort.e
    namespace stdsort
    public function sort(sequence x, integer order = ASCENDING)

sorts the elements of a sequence into ascending order.

##### Parameters:

1. `x` : The sequence to be sorted.
2. `order` : the sort order. Default is `ASCENDING`.

##### Returns:

A sequence, a copy of the original sequence in ascending order

##### Comments:

The elements can be atoms or sequences.

The standard `compare` routine is used to compare elements. This means that "`y` is greater than `x`" is defined by `compare(y, x)=1`.

This function uses the "Shell" sort algorithm. This sort is not "stable" which means elements that are considered equal might change position relative to each other.

##### Example 1:

    constant student_ages = {18,21,16,23,17,16,20,20,19}
    sequence sorted_ages
    sorted_ages = sort( student_ages )
    -- result is {16,16,17,18,19,20,20,21,23}

##### See Also:

compare, custom_sort

#### 8.18.2.2 custom_sort

    include std/sort.e
    namespace stdsort
    public function custom_sort(integer custom_compare, sequence x, object data = {},
            integer order = NORMAL_ORDER)

sorts the elements of a sequence according to a user-defined order.

##### Parameters:

1. `custom_compare` : an integer, the routine-id of the user defined routine that compares two items which appear in the sequence to sort.
2. `x` : the sequence of items to be sorted.
3. `data` : an object, either `{}` (no custom data, the default), an atom or a non-empty sequence.
4. `order` : an integer, either `NORMAL_ORDER` (the default) or `REVERSE_ORDER`.

##### Returns:

A sequence, a copy of the original sequence in sorted order

##### Errors:

If the user defined routine does not return according to the specifications in the Comments section below, an error will occur.

##### Comments:

- If some user data is being provided, that data must be either an atom or a sequence with at least one element. NOTE only the first element is passed to the user defined comparison routine, any other elements are just ignored. The user data is not used or inspected it in any way other than passing it to the user defined routine.

- The user defined routine must return an integer comparison result
  - a negative value if object A must appear before object B
  - a positive value if object B must appear before object A
  - 0 if the order does not matter

NOTE: The meaning of the value returned by the user-defined routine is reversed when `order = REVERSE_ORDER`. The default is `order = NORMAL_ORDER`, which sorts in order returned by the custom comparison routine.

- When no user data is provided, the user defined routine must accept two objects (A, B) and return just the comparison result.

- When some user data is provided, the user defined routine must take three objects (A, B , data). It must return either...
  - an integer, which is a comparison result
  - a two-element sequence, in which the first element is a comparison result and the second element is the updated user data that is to be used for the next call to the user defined routine.

- The elements of `x` can be atoms or sequences. Each time that the sort needs to compare two items in the sequence, it calls the user-defined function to determine the order.

- This function uses the "Shell" sort algorithm. This sort is not "stable" which means the elements that are considered equal might change position relative to each other.

##### Example 1:

    constant students = {{"Anne",18},   {"Bob",21},
                         {"Chris",16},  {"Diane",23},
                         {"Eddy",17},   {"Freya",16},
                         {"George",20}, {"Heidi",20},
                         {"Ian",19}}
    sequence sorted_byage
    function byage(object a, object b)
     ----- If the ages are the same, compare the names otherwise just compare ages.
        if equal(a[2], b[2]) then
            return compare(upper(a[1]), upper(b[1]))
        end if
        return compare(a[2], b[2])
    end function

    sorted_byage = custom_sort( routine_id("byage"), students )
    -- result is {{"Chris",16}, {"Freya",16},
    --            {"Eddy",17},  {"Anne",18},
    --            {"Ian",19},   {"George",20},
    --            {"Heidi",20}, {"Bob",21},
    --            {"Diane",23}}

    sorted_byage = custom_sort( routine_id("byage"), students,, REVERSE_ORDER )
    -- result is {{"Diane",23}, {"Bob",21},
    --            {"Heidi",20}, {"George",20},
    --            {"Ian",19},   {"Anne",18},
    --            {"Eddy",17},  {"Freya",16},
    --            {"Chris",16}}
    --

##### Example 2:

    constant students = {{"Anne","Baxter",18}, {"Bob","Palmer",21},
                         {"Chris","du Pont",16},{"Diane","Fry",23},
                         {"Eddy","Ammon",17},{"Freya","Brash",16},
                         {"George","Gungle",20},{"Heidi","Smith",20},
                         {"Ian","Sidebottom",19}}
    sequence sorted
    function colsort(object a, object b, sequence cols)
        integer sign
        for i = 1 to length(cols) do
            if cols[i] < 0 then
                sign = -1
                cols[i] = -cols[i]
            else
                sign = 1
            end if
            if not equal(a[cols[i]], b[cols[i]]) then
                return sign * compare(upper(a[cols[i]]), upper(b[cols[i]]))
            end if
        end for

        return 0
    end function

    -- Order is age:descending, Surname, Given Name
    sequence column_order = {-3,2,1}
    sorted = custom_sort( routine_id("colsort"), students, {column_order} )
    -- result is
    {
        {"Diane","Fry",23},
        {"Bob","Palmer",21},
        {"George","Gungle",20},
        {"Heidi","Smith",20},
        {"Ian","Sidebottom",19},
        {"Anne", "Baxter", 18 },
        {"Eddy","Ammon",17},
        {"Freya","Brash",16},
        {"Chris","du Pont",16}
    }

    sorted = custom_sort( routine_id("colsort"), students, {column_order}, REVERSE_ORDER )
    -- result is
    {
        {"Chris","du Pont",16},
        {"Freya","Brash",16},
        {"Eddy","Ammon",17},
        {"Anne", "Baxter", 18 },
        {"Ian","Sidebottom",19},
        {"Heidi","Smith",20},
        {"George","Gungle",20},
        {"Bob","Palmer",21},
        {"Diane","Fry",23}
    }

##### See Also:

compare, sort

#### 8.18.2.3 sort_columns

    include std/sort.e
    namespace stdsort
    public function sort_columns(sequence x, sequence column_list)

sorts the rows in a sequence according to a user-defined column order.

##### Parameters:

1. `x` : a sequence, holding the sequences to be sorted.
2. `column_list` : a list of columns indexes `x` is to be sorted by.

##### Returns:

A sequence, a copy of the original sequence in sorted order.

##### Comments:

`x` must be a sequence of sequences.

A non-existent column is treated as coming before an existing column. This allows sorting of records that are shorter than the columns in the column list.

By default columns are sorted in ascending order. To sort in descending order make the column number negative.

This function uses the "Shell" sort algorithm. This sort is not "stable" which means elements that are considered equal might change position relative to each other.

##### Example 1:

    sequence dirlist
    dirlist = dir("c:\\temp")
    sequence sorted
    -- Order is Size:descending, Name
    sorted = sort_columns( dirlist, {-D_SIZE, D_NAME} )

##### See Also:

compare, sort

#### 8.18.2.4 merge

    include std/sort.e
    namespace stdsort
    public function merge(sequence a, sequence b, integer compfunc = - 1, object userdata = "")

merges two pre-sorted sequences into a single sequence.

##### Parameters:

1. `a` : a sequence, holding pre-sorted data.
2. `b` : a sequence, holding pre-sorted data.
3. `compfunc` : an integer, either -1 or the routine id of a user-defined comparision function.

##### Returns:

A sequence, consisting of `a` and `b` merged together.

##### Comments:

- If `a` or `b` is not already sorted, the resulting sequence might not be sorted either.
- The input sequences do not have to be the same size.
- The user-defined comparision function must accept two objects and return an integer. It returns -1 if the first object must appear before the second one, and 1 if the first object must after before the second one, and 0 if the order doesn't matter.

##### Example 1:

    sequence X,Y
    X = sort( {5,3,7,1,9,0} ) --> {0,1,3,5,7,9}
    Y = sort( {6,8,10,2} ) --> {2,6,8,10}
    ? merge(X,Y) --> {0,1,2,3,5,6,7,8,9,10}

##### See Also:

compare, sort

#### 8.18.2.5 insertion_sort

    include std/sort.e
    namespace stdsort
    public function insertion_sort(sequence s, object e = "", integer compfunc = - 1,
            object userdata = "")

sorts a sequence and optionally another object together.

##### Parameters:

1. `s` : a sequence, holding data to be sorted.
2. `e` : an object. If this is an atom, it is sorted in with `s`. If this is a non-empty sequence then `s` and `e` are both sorted independantly using this `insertion_sort` function and then the results are merged and returned.
3. `compfunc` : an integer, either -1 or the routine id of a user-defined comparision function.

##### Returns:

A sequence, consisting of `s` and `e` sorted together.

##### Comments:

- This routine is usually a lot faster than the standard sort when `s` and `e` are (mostly) sorted before calling the function. For example, you can use this routine to quickly add to a sorted list.
- The input sequences do not have to be the same size.
- The user-defined comparision function must accept two objects and return an integer. It returns -1 if the first object must appear before the second one, and 1 if the first object must after before the second one, and 0 if the order does not matter.

##### Example 1:

    sequence X = {}
    while true do
       newdata = get_data()
       if compare(-1, newdata) then
          exit
       end if
       X = insertion_sort(X, newdata)
       process(new_data)
    end while

##### See Also:

compare, sort, merge

| Up |  |  | TOC | Index
<< 7 Included Tools | < 8.17 Serialization of Euphoria Objects | Up: 8 API Reference | 8.19 Locale Routines > | 9 Release Notes >>