Chapter 5 Divide and Conquer PDF

Chapter 5 Divide and conquer Solve using Substitution method Two inefficiencies of Merge Sort Not in place (It uses another array b[]) Copy between a[] and b[] needed Space and time for stack due to recursion For small set sizes, most of time consumed by re...

Chapter 5 Divide and conquer Solve using Substitution method Two inefficiencies of Merge Sort Not in place (It uses another array b[]) Copy between a[] and b[] needed Space and time for stack due to recursion For small set sizes, most of time consumed by recursion instead of sorting Quicksort A[p…j-1] ≤ A[j} ≤ A[j+1…q] Sort an array A[p…q] Divide Partition the array A into 2 subarrays A[p..j-1] and A[j+1..q], such that each element of A[p..j] is smaller than or equal to each element in A[j+1..q] Need to find index q to partition the array Conquer Recursively sort A[p..j-1] and A[j+1..q] using Quicksort Combine Trivial: the arrays are sorted in place No additional work is required to combine them The entire array is now sorted  QUICKSORT Procedure Quicksort (p , q) // sorts the elements A(p)………,A(q) which reside // // in the global array A(1:n) into ascending order // // A(n+1) is considered to be defined // // and must be ≥ all elements in A(p:q);A(n+1)= +∞ // Integer p, q; global n, A (1: n) If p < q then  // divide P into two subproblems j= PARTITION (a,p ,q+1) //j is the position of the partitioning element //solve the subproblem Quicksort (p , j-1) ; Quicksort (j+1 , q); // There is no need for combining solutions  end Quicksort Procedure Partition(a,m,p) // Within A(m),A(m+1),...,A(p-1)the elements are // // rearranged in such a way that if initially t=A(m) // // then after completion A(q)=t for some q between m and p-1 // // A(k)≤t for m ≤ k