CSC148H5 Lecture Notes - Lecture 31: University Of Toronto Mississauga, Quicksort, 5,6,7,8
27 Mar 2017
School
Department
Course
Professor
Document Summary
Csc148h5s - introduction to computer science (winter 2017) Lab today/tomorrow - reading comprehension test in first hour; optional 2nd hour. We look at a function to partition list lst[left:right+1] around pivot pivot. As we proceed through the list, we will maintain three consecutive slices. We"re goi(cid:374)g to keep i(cid:374)di(cid:272)es i a(cid:374)d j. Stuff to the left of i is less than the pivot. Stuff from i up to but not including j is greater or equal to the pivot. Stuff from j to the right is unprocessed. Incorrect code (but very close to being correct) from partition import partition def quicksort(lst, left, right): Sort lst[left:right+1] in nondecreasing order. if left < right: pivot = lst[right] i = partition(lst, left, right-1, pivot) quicksort(lst, left, i-1) quicksort(lst, i, right) Case that breaks this version of quicksort: [5, 4, 3, 2, 1] pivot is 1. Values >= 1: [5, 4, 3, 2, 1]
