算法设计(分治法-快速排序)_48287.ppt

2007-2008-01《Design and Analysis of Algorithms》SCUEC Review of last class Divide and Conquer technique The merge sort algorithm and its best-case, worst-case and average-case analysis Goals of the Lecture At the end of this lecture, you should Master the idea of quick sort algorithm Master the best-case, worst-case and average-case analysis of quick sort algorithm Understand the difference between merge sort and quick sort Quicksort Another sort algorithm example to reveal the essence of divide-and-conquer technique Its idea can be described as follows: Divide: Partition the array A[p..r] into two sub arrays A[p..q] and A[q+1..r] Invariant: All elements in A[p..q] are less than all elements in A[q+1..r] Conquer: Sort the two sub arrays recursively Merge: Unlike merge sort, no combining step, two sub arrays form an already-sorted array Quicksort Algorithm ALGORITHM QuickSort(A, l, r) //Sorts a subarray by quicksort //Input: A subarray A[l…r] of A[0…n-1], defined by its // left and right indices l and r //Output: Subarray A[l…r] sorted in nondecreasing order if l r s ← Partition(A, l, r) //s is a split position QuickSort(A, l, s-1) QuickSort(A, s+1, r) end if Partition Clearly, all the action takes place in the divide step should be the followings: Select a pivot and rearranges the array in place End result: Two sub arrays been separated by the pivot The elements in one sub array are smaller than the pivot The elements in another are larger than the pivot Returns the index of the “pivot” element separating the two sub arrays How do you suppose we implement this? Partition In Words Given an array A[0,…,n-1], we can partition the array like these: (1) Initial: select an element to act as the “pivot” (which?), let i and j indicate the index of second left and right elements which will be used to compare with the pivot. (2) Scan from left: Increase i until A[i] greater than and equal to the pivot. (3) Scan from right: Decr