Sorting Algorithms: Difference between revisions

From Algowiki
Jump to navigation Jump to search
No edit summary
No edit summary
Line 19: Line 19:
Let <math>n = 8</math> and <math>a = 3 \ 8 \ 1 \ 4 \ 3 \ 3 \ 2 \ 6</math>
Let <math>n = 8</math> and <math>a = 3 \ 8 \ 1 \ 4 \ 3 \ 3 \ 2 \ 6</math>
:{|
:{|
| <math>i:</math> || <math>0 \ 1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7</math>
|style="width: 4em"| <math>i:</math> || <math>0 \ 1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7</math>
|-
|-
| <math>a_i:</math> || <math>3 \ 8 \ 1 \ 4 \ 3 \ 3 \ 2 \ 6</math>
| <math>a_i:</math> || <math>3 \ 8 \ 1 \ 4 \ 3 \ 3 \ 2 \ 6</math>

Revision as of 11:45, 9 November 2014

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]