Sorting Algorithms - Revision history

Mahn89 at 14:21, 12 November 2014

2014-11-12T14:21:33Z

← Older revision		Revision as of 14:21, 12 November 2014
Line 1:		Line 1:
	== General ~~information~~ ==		== 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.		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.

Mahn89 at 14:29, 10 November 2014

2014-11-10T14:29:21Z

← Older revision		Revision as of 14:29, 10 November 2014
Line 3:		Line 3:
	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.		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> \leq </math> has to be defined.		Instead of numbers you can sort any data, e.g. strings. There must be a relation between the elements of the set, so to say, an ordering relation <math> \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.		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.

Mahn89 at 14:18, 9 November 2014

2014-11-09T14:18:14Z

← Older revision		Revision as of 14:18, 9 November 2014
Line 27:		Line 27:
	\| <math>a_{\varphi(i)}:</math> \|\| <math>1 \ 2 \ 3 \ 3 \ 3 \ 4 \ 6 \ 8</math>		\| <math>a_{\varphi(i)}:</math> \|\| <math>1 \ 2 \ 3 \ 3 \ 3 \ 4 \ 6 \ 8</math>
	\|}		\|}


			== Important algorithms ==
			* [[Bogosort]]
			* [[Bubble]]
			* [[Bubblesort]]
			* [[Bucketsort]]
			* [[Insertion sort]]
			* [[Mergesort]]
			* [[Quicksort]]
			* [[Selection sort]]

Mahn89 at 11:45, 9 November 2014

2014-11-09T11:45:54Z

← Older revision		Revision as of 11:45, 9 November 2014
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>

Mahn89 at 11:39, 9 November 2014

2014-11-09T11:39:21Z

← Older revision		Revision as of 11:39, 9 November 2014
Line 18:		Line 18:
	== Example ==		== Example ==
	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>i:</math> \|\| <math>0 \ 1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7</math>
	\| <math>0 \ 1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7</math>
	\|-		\|-
	\| <math>a_i:</math>		\| <math>a_i:</math> \|\| <math>3 \ 8 \ 1 \ 4 \ 3 \ 3 \ 2 \ 6</math>
	\| <math>0 \ 1 \ 2 \ 3 \ 4 \ 5 \ 6 ~~\ 7~~</math>
	\|-		\|-
	\| <math>\varphi(i):</math>		\| <math>\varphi(i):</math> \|\| <math>2 \ 6 \ 5 \ 0 \ 4 \ 3 \ 7 \ 1</math>
	\| <math>0 \ 1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7</math>
	\|-		\|-
	\| <math>a_{\varphi(i)}:</math>~~\quad~~		\| <math>a_{\varphi(i)}:</math> \|\| <math>1 \ 2 \ 3 \ 3 \ 3 \ 4 \ 6 \ 8</math>
	\| <math>~~0 \~~ 1 \ 2 \ 3 \ 4 ~~\ 5~~ \ 6 \ 7</math>
	\|
	\|}		\|}

Mahn89 at 11:34, 9 November 2014

2014-11-09T11:34:22Z

← Older revision		Revision as of 11:34, 9 November 2014
Line 6:		Line 6:

	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.		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>n \in \N</math> and <math>a = a_0, \dots, a_{n-1}</math> a finit sequence with <math>a_i \in \N \quad (i = 0, \dots, n-1)</math>

			The ''sorting problem'' is to find a sequence <math>a_{\varphi (0)}, \dots, a_{\varphi (n-1)}</math> with folloing constraints:
			:* <math>a_{\varphi(i)} \leq a_{\varphi(j)} \quad \forall i,j \in \{0, \dots, n-1\}, i < j</math>
			:* the mapping <math>\varphi</math> is a permutation of the index set <math>\{0, \dots, n-1\}</math>


			== Example ==
			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>
			\|-
			\| <math>a_i:</math>
			\| <math>0 \ 1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7</math>
			\|-
			\| <math>\varphi(i):</math>
			\| <math>0 \ 1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7</math>
			\|-
			\| <math>a_{\varphi(i)}:</math>\quad
			\| <math>0 \ 1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7</math>
			\|
			\|}

Mahn89: Created page with "== 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. I..."

2014-11-09T10:53:19Z

Created page with "== 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. I..."

New page

== 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> \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.