Chapter7SortingAlgorithms

1、Chapter 7: Sorting AlgorithmsQuick SortMark Allen Weiss: Data Structures and Algorithm Analysis in JavaLydia Sinapova, Simpson College1Quick SortBasic IdeaCodeAnalysisAdvantages and DisadvantagesApplicationsComparison with Heap sort and Merge sortAnimation2Basic IdeaPick one element in the array, wh

2、ich will be the pivot. Make one pass through the array, called a partition step, re-arranging the entries so that: entries smaller than the pivot are to the left of the pivot. entries larger than the pivot are to the right 3Basic IdeaRecursively apply quicksort to the part of the array that is to th

3、e left of the pivot, and to the part on its right.No merge step, at the end all the elements are in the proper order4Choosing the PivotSome fixed element: e.g. the first, the last, the one in the middle.Bad choice - may turn to be the smallest or the largest element, then one of the partitions will

4、be emptyRandomly chosen (by random generator) - still a bad choice5Choosing the PivotThe median of the array (if the array has N numbers, the median is the N/2 largest number). This is difficult to compute - increases the complexity. 6Choosing the PivotThe median-of-three choice: take the first, the

5、 last and the middle element. Choose the median of these three elements. 7Find the Pivot Java Codeint median3 ( int a, int left, int right) int center = (left + right)/2; if (a left a center) swap (a left , a center); if (a center a right) swap (acenter, a right ); if (a left a center) swap (a left

6、, a center); swap(a center , a right-1 ); return a right-1 ;8Quick Sort Java CodeIf ( left + 10 = right) / do quick sort else insertionSort (a, left, right);9Quick Sort Java Code int i = left, j = right - 1; for ( ; ; ) while (a + i pivot) while ( pivot a - - j ) if (i j) swap (a i , a j ); else bre

7、ak; swap (a i , a right-1 ); quickSort ( a, left, i-1); quickSort (a, i+1, right); 10Implementation NotesCompare the two versions:A.while (a+i pivot) while (pivot a-j) if ( i j ) swap (ai, aj);else break;B. while (a i pivot) i+ ; while (pivot a j ) j- - ; if ( i 1 Telescoping:T(N-1) = T(N-2) + c(N-1

8、)T(N-2) = T(N-3) + c(N-2)T(N-3) = T(N-4) + c(N-3) .T(2) = T(1) + c.2 16Worst-Case AnalysisT(N) + T(N-1) + T(N-2) + + T(2) = T(N-1) + T(N-2) + + T(2) + T(1) + c(N) + c(N-1) + c(N-2) + + c.2T(N) = T(1) + c times (the sum of 2 thru N) = T(1) + c (N (N+1) / 2 -1) = O(N2)17Best-Case AnalysisThe pivot is

9、in the middleT(N) = 2T(N/2) + cNDivide by N:T(N) / N = T(N/2) / (N/2) + c18Best-Case AnalysisTelescoping:T(N) / N = T(N/2) / (N/2) + cT(N/2) / (N/2) = T(N/4) / (N/4) + cT(N/4) / (N/4) = T(N/8) / (N/8) + cT(2) / 2 = T(1) / (1) + c19Best-Case AnalysisAdd all equations:T(N) / N + T(N/2) / (N/2) + T(N/4

10、) / (N/4) + . + T(2) / 2 = = (N/2) / (N/2) + T(N/4) / (N/4) + + T(1) / (1) + c.logNAfter crossing the equal terms: T(N)/N = T(1) + c*LogNT(N) = N + N*c*LogN = O(NlogN)20Advantages and DisadvantagesAdvantages:One of the fastest algorithms on averageDoes not need additional memory (the sorting takes p

11、lace in the array - this is called in-place processing )Disadvantages:The worst-case complexity is O(N2)21ApplicationsCommercial applications QuickSort generally runs fast No additional memoryThe above advantages compensate for the rare occasions when it runs with O(N2)22ApplicationsNever use in app

12、lications which require a guarantee of response time:Life-critical (medical monitoring, life support in aircraft, space craft) Mission-critical (industrial monitoring and control in handling dangerous materials, control for aircraft, defense, etc) unless you assume the worst-case response timeWarning:23Comparison with Heap Sort O(NlogN) complexity quick sort runs faster, (does not support a heap tree)the speed of quick sort is not guaranteed 24Compa