Introduction to Sorting To sort a collection of data is to place it in order.
We will deal primarily with algorithms that solve the General Sorting
In this problem, we are given:
A sequence.
Items are all of the same type.
There are no other restrictions on the items in the sequence.
A comparison function.
Given two sequence items, determine which should come first.
Using this function is the only way we can make such a determination.
We return:
A sorted sequence with the same items as the original sequence.
We will analyze sorting algorithms according to five criteria:
Efficiency
What is the (worst-case) order of the algorithm?
Is the algorithm much faster on average than its worst-case performance?
Requirements on Data
Does the algorithm need random-access data? Does it work well with Linked Lists?
What operations does the algorithm require the data to have?
Of course, we always need “compare”. What else?
Space Usage
Can the algorithm sort in-place?
An in-place algorithm is one that does not require extra buffers to hold a large number of data items.
How much additional storage is used?
Every algorithm uses at least a little.
Stability
Is the algorithm stable?
A sorting algorithm is stable if it does not reverse the order of equivalent items.
Performance on Nearly Sorted Data
Is the algorithm faster when given sorted (or nearly sorted) data?
All items close to where they should be, or a limited number of items out of order.
There is no known sorting algorithm that has all the properties we would like one to have.
We will examine a number of sorting algorithms. Generally, these fall into two categories: O(n2) and O(n log n).
Quadratic [O(n2)] Algorithms
Bubble Sort
Selection Sort
Insertion Sort
Quicksort
Treesort (later in semester)
Log-Linear [O(n log n)] Algorithms
Merge Sort
Heap Sort (mostly later in semester)
Introsort (not in text)
Special-Purpose Algorithm
Radix Sort