Sorting Algorithms: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
|||
| Line 9: | Line 9: | ||
The '''sorting problem''' if formally defined as follows: given a sequence of n numbers (a<sub>1</sub>, a<sub>2</sub>, ... a<sub>n</sub>) provided as input, the algorithm must produce as output a permutation (reordering) (a<sup>'</sup><sub>1</sub>, a<sup>'</sup><sub>2</sub>, ... a<sup>'</sup><sub>n</sub>) of the input sequence such that a<sup>'</sup><sub>1</sub> ≤ a<sup>'</sup><sub>2</sub> ≤ ... ≤ a<sup>'</sup><sub>n</sub>. A specific input sequence is called an '''[[Data Structures and Algorithms#Instance_of_the_problem|instance]]''' of the sorting problem. | The '''sorting problem''' if formally defined as follows: given a sequence of n numbers (a<sub>1</sub>, a<sub>2</sub>, ... a<sub>n</sub>) provided as input, the algorithm must produce as output a permutation (reordering) (a<sup>'</sup><sub>1</sub>, a<sup>'</sup><sub>2</sub>, ... a<sup>'</sup><sub>n</sub>) of the input sequence such that a<sup>'</sup><sub>1</sub> ≤ a<sup>'</sup><sub>2</sub> ≤ ... ≤ a<sup>'</sup><sub>n</sub>. A specific input sequence is called an '''[[Data Structures and Algorithms#Instance_of_the_problem|instance]]''' of the sorting problem. | ||
<span id='Comparison_Sort'></span>'''Comparison sort'''. Cannot do better than n | <span id='Comparison_Sort'></span>'''Comparison sort'''. Cannot do better than n lg n. Proof in a separate article. | ||
<span id='Non-Comparison_Sort'></span>'''Non-comparison sort'''. | <span id='Non-Comparison_Sort'></span>'''Non-comparison sort'''. | ||
Revision as of 04:15, 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.
Comparison sort. Cannot do better than n lg n. Proof in a separate article.
Non-comparison sort.
Sorting algorithms characteristics:
- in-place
- stability