Class Notes (839,479)
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

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

Unlock Document

Unlock to view full version

Unlock Document
Me

OR

Join OneClass

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

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Just a few more details

So we can recommend you notes for your school.