Sorting Algorithms: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
Line 16: Line 16:
* <span id='In-place'></span>'''in-place'''
* <span id='In-place'></span>'''in-place'''
* <span id='Stability'><span>'''stability'''
* <span id='Stability'><span>'''stability'''
=Sorting Algorithms=
* [[Insertion Sort#Overview|insertion sort]]
* [[Merge Sort#Overview|merge sort]]

Revision as of 04:11, 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 ln n. Proof in a separate article.

Non-comparison sort.

Sorting algorithms characteristics:

  • in-place
  • stability

Sorting Algorithms