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'''.  In practice, it is rarely the case when the keys exist in isolation. Usually they are part of a larger structure called '''record''', which also contains '''satellite data'''.  
The numbers we wish to sort are also known as '''keys'''.  In practice, it is rarely the case when the keys exist in isolation. Usually they are part of a larger structure called '''record''', which also contains '''satellite data'''.  


<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]].  
<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]]. The worst-case running time of comparison sort algorithms is Ω(n lgn).


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

Revision as of 00:38, 10 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. In practice, it is rarely the case when the keys exist in isolation. Usually they are part of a larger structure called record, which also contains satellite data.

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. The worst-case running time of comparison sort algorithms is Ω(n lgn).

Non-comparison sort.

Sorting algorithms characteristics:

  • in place: a sorting algorithm is said to sort the input numbers "in place" if it rearranges the numbers within the input array, while at most a constant number of elements are stored outside the array at any time.
  • stability

Sorting Algorithms