CP164 Midterm: - Sorting
Notes - Sorting
Suppose we have an array A of keys. Sort the keys so that they are in ascending order,
i.e. A[i] <= A[i+1] for all i, 0 <=i<n-2
We assume that any two keys, K1 and K2 can be compared and that one of the following is
true:
K1 < K2
K1 == K2
K1 > K2
Why should we study sorting?
• Sorting is essential to many applications.
• There are a large number of good algorithms for solving the problem, so it is a good
problem to look at for comparing algorithms.
Sorting algorithms can be implemented for both arrays and linked structures. We will work
on both.
Some Sorting Algorithms
• Bubble Sort
• Insertion Sort
• Tree Sort
• Selection Sort
• Shell Sort
• Merge Sort
• Quick Sort
• Heap Sort
We will examine a number of these algorithms in depth.
Insertion Sort
The Main Idea: take the unsorted keys one at a time and insert them into a list that is
sorted. Example:
Sort
68
89
45
10
20
Document Summary
Suppose we have an array a of keys. Sort the keys so that they are in ascending order, i. e. a[i] <= a[i+1] for all i, 0 <=i
