# Difference between revisions of "Tutorial:Advanced List Sorting"

(more motivation for Noel's extension of the algorithm) |
m |
||

Line 29: | Line 29: | ||

# Define <code>list=Sequence[Object[Element[list_n, k]], k, 1, Length[list_n]]</code>.<br />This creates the list of objects we want to sort based upon the name list. | # Define <code>list=Sequence[Object[Element[list_n, k]], k, 1, Length[list_n]]</code>.<br />This creates the list of objects we want to sort based upon the name list. | ||

# <code>list_h = Sort[Sequence[('''*number based upon Element[list, i]*''', i), i, 1, Length[list]]]</code> <br /> This is step 2 of our original algorithm. | # <code>list_h = Sort[Sequence[('''*number based upon Element[list, i]*''', i), i, 1, Length[list]]]</code> <br /> This is step 2 of our original algorithm. | ||

− | # <code>list_{ns} | + | # <code>list_{ns} = Sequence[Element[list_n, y(Element[list_h, i])], i, 1, Length[list]]</code> <br />This is now a list with the sorted names of the objects, like <code>{"B", "A", "E", "F", "D"}</code>. If you also want a sorted list with the values you can just use <code>list_s</code> as defined in the original algorithm. |

## Revision as of 21:47, 12 April 2012

If you want to sort a list of objects in GeoGebra it is not unlikely that the kind of sorting you want is not possible with the Sort command. (If you just want to inverse the results you can use `Sort[]`

together with Reverse[]).

But in case the kind of object is not supported by `Sort[]`

or you want a completely different sorting criterion this tutorial may help you with your task. If you're having problem with the algorithm you can read the explanation and examples below.

## Algorithm

- Let
`list`

be the list we want to sort. `list_h = Sort[Sequence[(`

***number based upon Element[list, i]***, i), i, 1, Length[list]]]

This corresponds to c in the explanation (the helper list). The bold section is called f in the explanation.`list_s = Sequence[Element[list, y(Element[list_h, i])], i, 1, Length[list]]`

This is the sorted list.

## Explanation

To clarify the situation let us try to formulate the task mathematically: Given a list (a_1, a_2, \ldots, a_n) \subset X and a mapping f: X \to \mathbb R we want to find a permutation \sigma \in S_n such that f(a_{\sigma(k)}) \leq f(a_{\sigma(l)}) \; \forall (k,l) \in \mathbb N^2: 1 \leq k \leq l \leq n. You can think of the permutation \sigma as a renumbering such that (a_{\sigma(1)}, a_{\sigma(2)}, \ldots, a_{\sigma(n)}) will be the sorted list.

So we first have to come up with a mapping f for the correct sorting, for example:

**Example:**If want to sort a list of points such that their distance to the origin is increasing we have X := \mathbb R^2 and f((x,y)) := \sqrt{x^2 + y^2}. In GeoGebra f for a point

`A`

would be `Length[A]`

, so the bold section in the algorithm would read `Length[Element[list,i]]`

.**Example:**If want to sort a list of circles such that their radius is increasing the bold section in the algorithm would read

`Radius[Element[list,i]]`

.**Example:**A complete construction to sort a list of complex numbers by their argument can be found on GeoGebra: http://www.geogebra.org/material/show/id/7518

The trick to solve this problem in GeoGebra is to use the existing command to sort a list of points. Instead of thinking of points geometrically we think of those just as pairs of numbers. GeoGebra allows us to sort those points by their x-coordinates, so we create a list of points \tilde c = (\tilde c_1, \ldots, \tilde c_n) with \tilde c_k := (f(a_k), k) and sort this list. Let's call the sorted list c = (c_1, \ldots, c_n). This sorted list now allows us to construct \sigma, because y(c_{\sigma(k)}) = k. Using \sigma we can then construct the sorted version of our original list.

## And for the names?

Imagine we have constructed five points called `A`

, `B`

, `C`

, `D`

and `E`

and we want to sort those points based upon some criterion. Using `list = {A,B,C,D,E}`

the algorithm above can be used to achieve this, but it will just return a sorted list with the coordinates of the points, not a sorted list with their original names, which could have a meaning in the construction and thus also helpful to display to the user. To also display those names in a sorted manner we have to extend our algorithm slightly:

- Let
`list_n`

be a list with the*names of the objects*we want to sort.

For example:`list_n = {"A", "B","C","D","E"}`

. Do not forget the quotes: We want the names of the objects and not the objects themselves! - Define
`list=Sequence[Object[Element[list_n, k]], k, 1, Length[list_n]]`

.

This creates the list of objects we want to sort based upon the name list. `list_h = Sort[Sequence[(`

***number based upon Element[list, i]***, i), i, 1, Length[list]]]

This is step 2 of our original algorithm.`list_{ns} = Sequence[Element[list_n, y(Element[list_h, i])], i, 1, Length[list]]`

This is now a list with the sorted names of the objects, like`{"B", "A", "E", "F", "D"}`

. If you also want a sorted list with the values you can just use`list_s`

as defined in the original algorithm.

es:Tutorial:Orden de Listas Avanzado fr:Tutoriel:Tri pointu pour une liste