Sorting based on pairwise comparison - Revision history

Weihe: /* Complexity */

2015-05-17T12:30:21Z

Complexity

← Older revision		Revision as of 12:30, 17 May 2015
Line 14:		Line 14:

	==Complexity==		==Complexity==
	Polynomial.		Polynomial if the comparison is polynomial.

	==Known algorithms==		==Known algorithms==

Weihe: /* Remark */

2015-04-29T14:16:05Z

Remark

← Older revision		Revision as of 14:16, 29 April 2015
Line 24:		Line 24:
	==Remark==		==Remark==
	Some algorithms could be formulated in a much simpler way in case each key occurs at most once in <math>S</math>. Here all algorithms are formulated for the general case of arbitrary multiplicities. Alternatively, there are three options to make each key unique:		Some algorithms could be formulated in a much simpler way in case each key occurs at most once in <math>S</math>. Here all algorithms are formulated for the general case of arbitrary multiplicities. Alternatively, there are three options to make each key unique:
	# An additional generated key such as, for example, student ID or tax file number.		# An additional generated key such as, for example, the student ID or the tax file number.
	# If the keys are associated with values, they are additionally compared if the keys of two items are identical (e.g. date of birth and home address, if last and first names of two persons are identical).		# If the keys are associated with values, they are additionally compared if the keys of two items are identical (e.g. date of birth and home address, if last and first names of two persons are identical).
	# On the other hand, if the keys are '''not''' associated with values, we may remove the duplicates and store their multiplicities separately.		# On the other hand, if the keys are '''not''' associated with values, we may remove the duplicates and store their multiplicities separately.

Weihe: /* Remark */

2015-04-29T14:15:34Z

Remark

← Older revision		Revision as of 14:15, 29 April 2015
Line 24:		Line 24:
	==Remark==		==Remark==
	Some algorithms could be formulated in a much simpler way in case each key occurs at most once in <math>S</math>. Here all algorithms are formulated for the general case of arbitrary multiplicities. Alternatively, there are three options to make each key unique:		Some algorithms could be formulated in a much simpler way in case each key occurs at most once in <math>S</math>. Here all algorithms are formulated for the general case of arbitrary multiplicities. Alternatively, there are three options to make each key unique:
	# An additional generated key, for example, student ID or tax file number.		# An additional generated key such as, for example, student ID or tax file number.
	# If the keys are associated with values, they are additionally compared if the keys of two items are identical (e.g. date of birth and home address, if last and first names of two persons are identical).		# If the keys are associated with values, they are additionally compared if the keys of two items are identical (e.g. date of birth and home address, if last and first names of two persons are identical).
	# If the keys are '''not''' associated with values, we may remove the duplicates and store their multiplicities separately.		# On the other hand, if the keys are '''not''' associated with values, we may remove the duplicates and store their multiplicities separately.

Cuozzo: Created page with "NOTOC Category:Checkup Category:Algorithmic Problem Category:Sorting ==Input== # An ordered sequence $..."$

2014-10-02T12:29:35Z

Created page with "__NOTOC__ Category:Checkup Category:Algorithmic Problem Category:Sorting ==Input== # An ordered sequence <math>..."

New page

__NOTOC__
[[Category:Checkup]]
[[Category:Algorithmic Problem]]
[[Category:Sorting]]
==Input==
# An [[Sets and sequences#Ordered and sorted sequences|ordered sequence]] <math>S</math> of length <math>n</math>.
# A definition of [[Genericity#Comparison|comparison]] on the component type of <math>S</math>.

==Output==
A permutation of <math>S</math> such that <math>S[i] \le S[i+1]</math> for all <math>i\in \{1,...,n-1\}</math>.

==Objective==
N/A

==Complexity==
Polynomial.

==Known algorithms==
# [[Bubblesort]]
# [[Mergesort]]
# [[Quicksort]]
# [[Selection sort]]

==Remark==
Some algorithms could be formulated in a much simpler way in case each key occurs at most once in <math>S</math>. Here all algorithms are formulated for the general case of arbitrary multiplicities. Alternatively, there are three options to make each key unique:
# An additional generated key, for example, student ID or tax file number.
# If the keys are associated with values, they are additionally compared if the keys of two items are identical (e.g. date of birth and home address, if last and first names of two persons are identical).
# If the keys are '''not''' associated with values, we may remove the duplicates and store their multiplicities separately.

Sorting based on pairwise comparison - Revision history

Weihe: /* Complexity */

Weihe: /* Remark */

Weihe: /* Remark */

Cuozzo: Created page with "__NOTOC__ Category:Checkup Category:Algorithmic Problem Category:Sorting ==Input== # An ordered sequence ..."

Cuozzo: Created page with "NOTOC Category:Checkup Category:Algorithmic Problem Category:Sorting ==Input== # An ordered sequence $..."$