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

###### You're Reading a Preview

Unlock to view full version