Sorting Algorithms: Difference between revisions
| Line 10: | Line 10: | ||
The numbers we wish to sort are also known as '''keys'''. | The numbers we wish to sort are also known as '''keys'''. | ||
<font color=darkgray> | |||
<span id='Comparison_Sort'></span>'''Comparison sort'''. Cannot do better than n lg n. Proof in a separate article. | <span id='Comparison_Sort'></span>'''Comparison sort'''. Cannot do better than n lg n. Proof in a separate article. | ||
| Line 18: | Line 20: | ||
* <span id='In-place'></span>'''in-place''' | * <span id='In-place'></span>'''in-place''' | ||
* <span id='Stability'><span>'''stability''' | * <span id='Stability'><span>'''stability''' | ||
</font> | |||
=Sorting Algorithms= | =Sorting Algorithms= | ||
Revision as of 18:00, 5 August 2018
Internal
Overview
Many programs use sorting as an intermediate step, and that is why sorting is considered a fundamental operation in computer science.
The sorting problem if formally defined as follows: given a sequence of n numbers (a1, a2, ... an) provided as input, the algorithm must produce as output a permutation (reordering) (a'1, a'2, ... a'n) of the input sequence such that a'1 ≤ a'2 ≤ ... ≤ a'n. A specific input sequence is called an instance of the sorting problem. Although conceptually we are sorting a sequence, the input comes to the sorting function as an array with n elements.
The numbers we wish to sort are also known as keys.
Comparison sort. Cannot do better than n lg n. Proof in a separate article.
Non-comparison sort.
Sorting algorithms characteristics:
- in-place
- stability