|
Sorting
Input: <a1, a2, a3, ...,an> (n items)
Output: <a'1, a'2, a'3,...,
a'n> A permutation of the input list ' a'1
£ a'2 £ a'3 £ ... £ a'n
Sorting is often a sub problem within larger data processing functions. For example in Searching for a data record:
Sorting is often done on a key, either by:
- Moving the satellite data as well as the key
- Using pointers from the sorted keys, back to the satellite data
We assume we only need the details of sorting things like keys, ignoring details like the makeup of the satellite data.
| Algorithm |
In Place? |
T(n) |
| Insertion Sort |
Yes |
O (n2) |
| Merge Sort |
No |
Q (n lg n) |
| Heap Sort |
Yes |
Q (n lg n) |
| Quick Sort |
Yes |
O (n2) - worst Q (n lg n) Avg. |
All of these are comparison sorts. We shall use the decision-tree model to study them.
The best comparison based sort is W (n lg n).
How do we beat comparison sort based algorithms?
We will find counting sort and radix sort in certain circumstances can sort in linear time.
Bucket
sort, which requires some knowledge of the inputs, also sorts in linear time.
We will use sorting to find algorithms for order statistics:
- Median
- ith order statistic ai'
We find algorithms that are W (n lg n) and O (n) |
