Sorting Algorithms: Difference between revisions
No edit summary |
|||
| Line 10: | Line 10: | ||
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'''. | ||
Sorting algorithms characteristics: | Sorting algorithms characteristics: | ||
| Line 25: | Line 17: | ||
=Sorting Algorithms= | =Sorting Algorithms= | ||
==Key Comparison Algorithms== | ==<span id='Comparison_Sort'></span>Key Comparison Sorting Algorithms== | ||
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). | |||
* [[Insertion Sort#Overview|Insertion sort]] | * [[Insertion Sort#Overview|Insertion sort]] | ||
| Line 32: | Line 26: | ||
* [[Heap Sort#Overview|Heap sort]] | * [[Heap Sort#Overview|Heap sort]] | ||
* [[Quick Sort#Overview|Quick sort]] | * [[Quick Sort#Overview|Quick sort]] | ||
==<span id='Non-Comparison_Sort'></span>Non-Comparison Sorting Algorithms== | |||
* [[Counting Sort|counting sort]] | |||
Revision as of 00:41, 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.
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
Key Comparison Sorting Algorithms
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).