Class Notes (922,247)
CA (542,775)
UTM (24,991)
CSC (155)
CSC148H5 (63)
Lecture 19

CSC148H5 Lecture 19: 03-21-16 Monday
Premium

1 Page
56 Views

Department
Computer Science
Course Code
CSC148H5
Professor
Sadia Sharmin

This preview shows half of the first page. Sign up to view the full page of the document.
Quick sort
O(n^2) but on average O(n lg)
-take right most element compare to all elements if smaller than element switch element with left most
element of the partition (partition seperates sorted list from unsorted)
Partition :
indicies i and j
5,6,1,3,8,4,7,9,2
2 is pivot
*after 1 pass with pivot 2
1 | 6,3,8,4,7,9,2
1,2, | 6,3,8,4,7,9
^ is i, 9 is new pivot
- stuff to the left of the i are less than the pivot
- stuff from i up to but not including j is the processed elements
-number past j is the pivot element
Partition code
def partition(lst,left,right,pivot):
'''
Rearrange lst so elements >= pivot follow elements < pivot;
return index of first element >= pivot
'''
i = left
j= left
while j <= right:
if lst[j] < pivot:
lst[i], lst[j] = lst[j], lst[i]
i += 1
j += 1
return i
6,2,12,6,10,15,2,13 (pivot 5)
2,2 | 12,6,10,15,6,13
Old Sort
selection sort
go through the list repeatedly switching the smallest one with the left-most side and then look
at the rest of the not sorted list
Insertion sort
take the first value in the list as your sorted list and then look through the unsorted list and
insert it into the correct area in the unsorted list
New Sorts
Quick sort
takes a pivot value and compares it with every value in the given list sorting the values less than
it to the left and more than it to the right and then runs the rest o
Merge sort
compare in pairs

Loved by over 2.2 million students

Over 90% improved by at least one letter grade.

Leah — University of Toronto

OneClass has been such a huge help in my studies at UofT especially since I am a transfer student. OneClass is the study buddy I never had before and definitely gives me the extra push to get from a B to an A!

Leah — University of Toronto
Saarim — University of Michigan

Balancing social life With academics can be difficult, that is why I'm so glad that OneClass is out there where I can find the top notes for all of my classes. Now I can be the all-star student I want to be.

Saarim — University of Michigan
Jenna — University of Wisconsin

As a college student living on a college budget, I love how easy it is to earn gift cards just by submitting my notes.

Jenna — University of Wisconsin
Anne — University of California

OneClass has allowed me to catch up with my most difficult course! #lifesaver

Anne — University of California
Description
Quick sort O(n^2) but on average O(n lg) -take right most element compare to all elements if smaller than element switch element with left most element of the partition (partition seperates sorted list from unsorted) Partition : indicies i and j 5,6,1,3,8,4,7,9,2 2 is pivot *after 1 pass with pivot 2 1 | 6,3,8,4,7,9,2 1,2, | 6,3,8,4,7,9 ^ is i, 9 is new pivot - stuff to the left of the i are less than the pivot - stuff from i up to but not including j is the processed elements -number past j is the pivot element Partition code def partition(lst,left,right,pivot): ''' Rearrange lst so elements >= pivot follow elements < pivot; return index of first element >= pivot ''' i = left j= left while j <= right:
More Less
Unlock Document


Only half of the first page are available for preview. Some parts have been intentionally blurred.

Unlock Document
You're Reading a Preview

Unlock to view full version

Unlock Document

Log In


OR

Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


OR

By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.


Submit