Class Notes (1,100,000)
US (490,000)
Cornell (1,000)
CS (100)
CS 2110 (30)
Gries (30)
Lecture 11

CS 2110 Lecture Notes - Lecture 11: Sorting Algorithm, Insertion Sort, Postcondition

Department
Computer Science
Course Code
CS 2110
Professor
Gries
Lecture
11

This preview shows half of the first page. to view the full 3 pages of the document.
Lecture 11 - Sorting
oInsertionSort
Precondition: all are unsorted
Postcondition: all are sorted
Invariant: [0, i-1] sorted and [i, b.length()] unsorted
Each iteration pushes value of b[i] to sorted position and i = i+1
for (int i = 0; i<b.length ; i = i+1) {
//push b[i] down to sorted position in b[0..i]
Best Case: takes O(n) time
Worst case: takes O(n^2) time
oSelectionSort
Precondition and Post are same for Insertion sort
Pre: All are unsorted
Post: All are sorted
What’s our new invariant
Why new? Can’t be same invariant for different algorithm silly!
For b[0...i-1]
Sorted
AND every element in this array part is less than or equal
to b[i]
For b[i...b.length-1]
Everything in here is greater than or equal to b[i-1]
So what’s in our loop?
for (int i = 0; i<b.length; i = i+1) {
int m = index of minimum of b[i…];
Swap b[i] and b[m];
}
Once again, this will always take time proportional to n^2, where
n=b.length
oQuicksort
First use a partition algorithm
Precondition
b[h] contains some value x
b[h+1...k] is unknown
x serves as our pivot
Postcondition
b[h...j-1] <= x
b[j] = x
b[j+1...k] >= x
Invariant
b[h...j-1] <= x
b[j] = x
b[j+1...t] = ?
b[t+1...k] >= x
Implementation
j = h; t= k;
find more resources at oneclass.com
find more resources at oneclass.com