CSE310 Lecture 06 Quick Sort Guoliang Larry Xue Department of CSE Arizona State University http optimization asu edu xue Guoliang Xue asu edu Topics of this lecture Divide and Conquer Divide Conquer Combine Quick Sort Description Example Worst case time complexity Average case time complexity 2 Guoliang Xue asu edu Quick Sort Divide Divide the sequence into 2 subsequences such that each element in the 1st subsequence is less than each element in the 2nd subsequence Conquer Sort each subsequence recursively using quick sort Combine no work is needed because it sorts in place 3 Guoliang Xue asu edu Example Sort people by their ages people age 25 people age 23 age 25 age people 23 age 234 people age 25 people age people age Guoliang Xue asu edu 30 30 age 30 Quick Sort Algorithm Quicksort A p r different from the text if p r then p k Partition A p r Quicksort A p k 1 A Quicksort A k 1 r k r The crux of the algorithm is the partition module it rearranges the list so that the element A k pivot is in its final place in the list all the elements in A p A k 1 are less than or equal to A k all the elements in A k 1 A r are greater than A k 5 Guoliang Xue asu edu How is the partition module implemented Ideally we can rearrange the list so that half elements go to left and half elements go to right of i In practice 1 Choose A r as the pivot element to go to the correct place in the list 2 If p k i then A k A r 3 If i 1 k j 1 then A k A r 4 Scan from left to right and do O 1 work at each position 6 Guoliang Xue asu edu Algorithm for Partitioning Partition A p r 1 x A r 2 i p 1 3 for j p to r 1 do 4 If A j x then 5 i i 1 6 exchange A i and A j 7exchange A i 1 and A r 8return i 1 7 Guoliang Xue asu edu Example Show the example on page 172 of the textbook 8 Guoliang Xue asu edu Complexity of Quick Sort The complexity depends on the partition Best case partitioning divide into 2 equal sublists 1 if n 1 T n 2T n 2 n otherwise T n nlgn Worst case partitioning if the list is already sorted The right sublist 0 and left sublist n 1 elements T n T n 1 n T n 2 n 1 n n n 1 2 k k n 2 k 1 k 1 n n 9 Guoliang Xue asu edu Average Complexity of Quick Sort Partition into q 1 to n q split All permutations are equally likely q 1 n T n n 1 2 T 0 T 1 T n 1 n nT n n n 1 2 T 0 T 1 T n 1 n 1 T n 1 n 1 n 2 T 0 T 1 T n 2 nT n n 1 T n 1 2n 2T n 1 nT n 2n n 1 T n 1 T n n 1 2 n 1 T n 1 n T n n 1 2 1 1 2 1 3 1 n 1 n log n 10 Guoliang Xue asu edu Stable Sorting and Non Stable Sorting A sorting algorithm is stable if A i A j implies the relative order of the two elements will not change during the sorting process Insertion sort is stable Quick sort is not stable 11 Guoliang Xue asu edu Summary Algorithm Design Divide and Conquer Algorithm Quicksort Analysis Average case analysis 12 Guoliang Xue asu edu Readings and Exercises The materials covered in this lecture can be found in Sections 7 1 7 4 Exercise 7 4 1 and 7 4 2 Study the Hoare partition on page 185 Lecture 07 will be on mergesort 13 Guoliang Xue asu edu
View Full Document
Unlocking...