Sorting Algorithms

General information

The sorting problem is one of the most frequent algorthmic problems. Its simplest form is to sort a finit set of numbers ascending or descending.

Instead of numbers you can sort any data, e.g. string. There must be a relation between the elements of the set, so to say, an ordering relation [math]\displaystyle{ \leq }[/math] has to be defined.

Often, the data is a set of complex data types, that has to be sorted by a special criteria. For example you have a set of person descriptions to be sorted by the birth dates.

Definition

Let [math]\displaystyle{ n \in \N }[/math] and [math]\displaystyle{ a = a_0, \dots, a_{n-1} }[/math] a finit sequence with [math]\displaystyle{ a_i \in \N \quad (i = 0, \dots, n-1) }[/math]

The sorting problem is to find a sequence [math]\displaystyle{ a_{\varphi (0)}, \dots, a_{\varphi (n-1)} }[/math] with folloing constraints:

• [math]\displaystyle{ a_{\varphi(i)} \leq a_{\varphi(j)} \quad \forall i,j \in \{0, \dots, n-1\}, i \lt j }[/math]
• the mapping [math]\displaystyle{ \varphi }[/math] is a permutation of the index set [math]\displaystyle{ \{0, \dots, n-1\} }[/math]

Example

Let [math]\displaystyle{ n = 8 }[/math] and [math]\displaystyle{ a = 3 \ 8 \ 1 \ 4 \ 3 \ 3 \ 2 \ 6 }[/math]

[math]\displaystyle{ i: }[/math]	[math]\displaystyle{ 0 \ 1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7 }[/math]
[math]\displaystyle{ a_i: }[/math]	[math]\displaystyle{ 3 \ 8 \ 1 \ 4 \ 3 \ 3 \ 2 \ 6 }[/math]
[math]\displaystyle{ \varphi(i): }[/math]	[math]\displaystyle{ 2 \ 6 \ 5 \ 0 \ 4 \ 3 \ 7 \ 1 }[/math]
[math]\displaystyle{ a_{\varphi(i)}: }[/math]	[math]\displaystyle{ 1 \ 2 \ 3 \ 3 \ 3 \ 4 \ 6 \ 8 }[/math]