Class Notes (839,479)
Canada (511,349)
CSC108H1 (113)
Lecture

november 25 notes

2 Pages
123 Views

Department
Computer Science
Course Code
CSC108H1
Professor
Michelle Craig

This preview shows 80% of the first page. Sign up to view the full 2 pages of the document.
Description
 Bubble sort o Compare two adjacent items, arrange them in order relative to each other  Then move on to compare the next two adjacent items  Next irritation, last item ignored 1. def bubble_sort(L): 2. '''Sort the items in L in non-descending order.''' 3. 4. # Do one major pass/iteration through the the unsorted part of the list 5. # (the part from the beginning to i spots from the end). Sink the largest 6. # value in that part of the list to the end of that part of the list. 7. 8. for i in range(len(L)): 9. for j in range(len(L) - i - 1): 10. if L[j] > L[j + 1]: 11. L[j], L[j + 1] = L[j + 1], L[j] 12. return L  merge sort  splits list into two sorted lists; compare the top two items, the smaller/lager is placed in the final list o then compare the top two items again, the smaller/larger item is placed in the final list o to split list into two sorted lists, use merge sort o recursion  call same function within a function 1. def merge(left, right): 2. '''Return the list made by merging sorted lists left and right.''' 3. result = [] 4. i ,j = 0, 0 5. while i < len(left) and j < len(right): 6. if left[i] <= right[j]: 7. result.append(left[i]) 8. i = i + 1 9. else: 10. result.append(right[j]) 11. j = j + 1 12. 13. # One of the sublists has elements left over; the other is empty. Copying 14. # both does no harm, since the empty one will add nothing. 15. result += left[i:] 16.
More Less
Unlock Document

Only 80% 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

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