Sorting Algorithms: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
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 '''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 '''instance''' of the sorting problem.


<font color=darkgray>
* Sorting
* Sorting
** Comparison Sort. Comparison sort algorithm class. Know that comparison sort cannot do better than n ln n. Proof in a separate article.
** Comparison Sort. Comparison sort algorithm class. Know that comparison sort cannot do better than n ln n. Proof in a separate article.
** Non-comparison Sort
** Non-comparison Sort
** Sorting algorithms characteristics (in-place, stability)
** Sorting algorithms characteristics (in-place, stability)
</font>

Revision as of 03:48, 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.

  • Sorting
    • Comparison Sort. Comparison sort algorithm class. Know that comparison sort cannot do better than n ln n. Proof in a separate article.
    • Non-comparison Sort
    • Sorting algorithms characteristics (in-place, stability)