CSE310 Lecture 06: Quick-SortTopics of this lectureQuick SortExample: Sort people by their agesQuick Sort AlgorithmHow is the partition module implemented?Algorithm for PartitioningExampleComplexity of Quick-SortAverage Complexity of Quick-SortStable Sorting and Non-Stable SortingSummaryReadings and [email protected] Lecture 06:CSE310 Lecture 06:Quick-SortQuick-SortGuoliang (Larry) XueDepartment of CSEArizona State Universityhttp://optimization.asu.edu/[email protected] of this lectureTopics of this lectureDivide and ConquerDivideConquerCombineQuick SortDescriptionExampleWorst-case time complexityAverage-case time [email protected]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 sortCombine: no work is needed, because it sorts in place.Quick SortQuick [email protected]: Sort people by their agesExample: Sort people by their agesage25peopleage ≤ 25peopleage > 25age23peopleage ≤ 23age30peopleage >30peopleage >23peopleage ≤ [email protected] (A, p,r) // different from the textif p < r thenk := Partition(A, p, r)Quicksort (A, p, k-1)Quicksort (A, k+1, 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] ApkrQuick Sort AlgorithmQuick Sort [email protected], 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.How is the How is the partit ionpartit ion module implemented? module [email protected](A, p, r)1 x := A[r]2 i := p-13 for j:=p to r-1 do4 If A[j] ≤ x then5 i := i+16 exchange A[i] and A[j]7exchange A[i+1] and A[r]8return i+1Algorithm for PartitioningAlgorithm for [email protected] the example on page 172 of the [email protected] partitioning: if the list is already sorted:The right sublist: 0, and left sublist: n - 1 elements)()1()2()()1()( nnnTnnTnT )(2)1()()(211nnnkknknkThe complexity depends on the partition.Best-case partitioning: divide into 2 equal sublistsotherwisennTnifnT)()2/(21)1()(T(n) = (nlgn)Complexity of Quick-SortComplexity of [email protected] Complexity of Quick-SortAverage Complexity of Quick-SortPartition into (q-1)-to-(n-q) split. All permutations are equally likely.q = 1, …, nT(n)=n+1+2(T(0)+T(1)+…+T(n-1))/nnT(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)/nT(n)=(n+1)2(1+1/2+1/3+…+1/(n+1)) = (n log n)[email protected] Sorting and Non-Stable SortingStable Sorting and Non-Stable SortingA 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 [email protected]Algorithm Design: Divide and ConquerAlgorithm: QuicksortAnalysis: Average-case [email protected] and ExercisesReadings and ExercisesThe 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
View Full Document
Unlocking...