Sorting Algorithms: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
Line 11: Line 11:
The numbers we wish to sort are also known as '''keys'''.  
The numbers we wish to sort are also known as '''keys'''.  


<span id='Comparison_Sort'></span>A sorting algorithm may compare keys, and in this case it is said to be a '''key comparison algorithm'''. It can be demonstrated that a key comparison algorithm cannot perform better than n lg n.  
<span id='Comparison_Sort'></span>A sorting algorithm may compare keys, and in this case it is said to be a '''key comparison algorithm'''. It can be demonstrated that a key comparison algorithm [[Comparison_Sorting_Algorithms_Complexity|cannot perform better than n lg n]].  


<font color=darkgray>
<font color=darkgray>

Revision as of 21: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. 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.

A sorting algorithm may compare keys, and in this case it is said to be a key comparison algorithm. It can be demonstrated that a key comparison algorithm cannot perform better than n lg n.

Non-comparison sort.

Sorting algorithms characteristics:

  • in-place
  • stability

Sorting Algorithms