CSC148H5 Lecture Notes - Lecture 32: University Of Toronto Mississauga, Quicksort, Merge Sort
27 Mar 2017
School
Department
Course
Professor
Document Summary
Csc148h5s - introduction to computer science (winter 2017) Lecture 32: quicksort and mergesort: recall our quicksort partition function: def partition(lst, left, right, pivot): Fill in the blank with a pivot that will cause 0 to be printed. To return a value of 0, i is never allowed to increase. i can never change. Every value has to be >= pivot for i not to change. Does it make the reverse-sorted case better or worse? from partition import partition def quicksort(lst, left, right): Merge sort is always o(n log n), even in the worst case. Recursively sorting the first half of the list. Recursively sorting the second half of the list. Merging the two halves into a newly sorted list. At each level of recursion, the merging takes a total of n steps, and there are log n levels before we get to the base case. Ther merging requires an auxiliary list (not required in merge sort)
