{"id":47,"date":"2018-07-19T04:59:43","date_gmt":"2018-07-19T04:59:43","guid":{"rendered":"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/?post_type=chapter&#038;p=47"},"modified":"2018-07-25T06:24:19","modified_gmt":"2018-07-25T06:24:19","slug":"divide-and-conquer-technique","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/chapter\/divide-and-conquer-technique\/","title":{"rendered":"Divide and Conquer Technique"},"content":{"raw":"&nbsp;\r\n<p style=\"text-align: center\"><strong>Module 10:<\/strong><\/p>\r\n<p style=\"text-align: center\"><strong>Divide and Conquer Technique<\/strong><\/p>\r\n&nbsp;\r\n<p class=\"hanging-indent\" style=\"text-align: justify\">This module 10 introduces the concept of popular design technique called divide and conquer technique.<\/p>\r\n<p class=\"hanging-indent\" style=\"text-align: justify\">The Learning objectives of this module are as follows:<\/p>\r\n\r\n<ul>\r\n \t<li style=\"text-align: justify\">To understand the concept of Divide and Conquer<\/li>\r\n \t<li style=\"text-align: justify\">To understand applications of Divide and Conquer technique<\/li>\r\n \t<li style=\"text-align: justify\">To know about Merge Sort algorithm<\/li>\r\n \t<li style=\"text-align: justify\">To understand Quicksort Algorithm<\/li>\r\n<\/ul>\r\n<strong>What is a divide and Conquer Design Technique?<\/strong>\r\n<p style=\"text-align: justify\">Divide and conquer is an effective algorithm design technique. This design technique is used to solve variety of problems. In this module, we will discuss about applying divide and conquer technique for sorting problems. In this design paradigm, the problem is divided into subproblems. The subproblems are divided further if necessary. Then the subproblems are solved recursively or iteratively and the results of the subproblems are combined to get the final solution of the given problem.<\/p>\r\nThese are the important components of Divide and Conquer strategy:\r\n<ol>\r\n \t<li>Divide: In this stage the given problem is divided into small problems. The smaller problems are similar to the original problem. But these smaller problems have reduced size, i.e., with less number of instances compared to original problem. If the subproblems are big, then the subproblems are divided further. This division process is continued till the obtained subproblems are smaller that can be solved in a straight forward manner.<\/li>\r\n \t<li>Conquer: The subproblems can be solved either recursively or non-recursively in a straight forward<span style=\"text-align: initial;font-size: 1em\"> manner.<\/span><\/li>\r\n \t<li>Combine: The solutions of the sub-problems can be combined to get the global result of the problems.<\/li>\r\n<\/ol>\r\n<p class=\"hanging-indent\"><strong>Advantages of Divide and Conquer Paradigm<\/strong><\/p>\r\n\r\n<ol>\r\n \t<li>The advantages of divide and conquer approach is that it is perhaps most commonly applied design technique and its application always leads to effective algorithms.<\/li>\r\n \t<li>It can be used to solve general problems.<\/li>\r\n \t<li>Divide and conquer paradigm is suitable for problems that are inherently parallel in nature.<\/li>\r\n<\/ol>\r\n<strong>Disadvantages of Divide and Conquer<\/strong>\r\n<ol>\r\n \t<li>The disadvantage of divide and conquer paradigm is that if division process is not carried in a proper manner, the unequal division of problem instances can result in inefficient implementation.<\/li>\r\n<\/ol>\r\nLet us discuss about one of the most popular algorithm that is based on divide and conquer, i.e., merge sort.\r\n\r\n&nbsp;\r\n<p class=\"hanging-indent\"><strong>Merge Sort<\/strong><\/p>\r\n<p style=\"text-align: justify\">Divide and conquer is the strategy used in merge sort. Merge sort was designed by the popular Hungarian mathematician John van Neumann. The procedure for merge sort is given informally as follows:<\/p>\r\n\r\n<ol>\r\n \t<li style=\"text-align: justify\">Divide: Divide the <em>n<\/em>-element sequence to be sorted into two subsequences of <em>n\/2<\/em> elements each.<\/li>\r\n \t<li style=\"text-align: justify\">Conquer: Sort the two subsequences recursively using merge sort in a recursive or non-recursive manner.<\/li>\r\n \t<li style=\"text-align: justify\">Combine: Merge the two sorted subsequences to produce the sorted answer.<\/li>\r\n<\/ol>\r\n<strong>Informal algorithm:<\/strong>\r\n<p class=\"hanging-indent\">Informally merge sort procedure is as follows:<\/p>\r\n\r\n<ol>\r\n \t<li>Divide the array A into subarrays L and R of size n\/2.<\/li>\r\n \t<li>Recursively sort the subarray L gives L sorted subarray<\/li>\r\n \t<li>Recursively sort\u00a0 the subarray R gives R sorted subarray<\/li>\r\n \t<li>Combine L and R sorted subarrays give final sorted array A<\/li>\r\n<\/ol>\r\nThe formal algorithm based on [3] is given as follows:\r\n\r\n&nbsp;\r\n\r\n<strong><em>MergeSort <\/em><\/strong><strong>(<em>A<\/em>,<em> p<\/em>,<em> r<\/em>)<\/strong>\u00a0\u00a0\u00a0 <strong>\/\/ <\/strong>sort <em>A<\/em>[<em>p..r<\/em>] by divide &amp; conquer\r\n\r\n&nbsp;\r\n\r\n1\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <strong>if <\/strong><em>p<\/em> &lt; <em>r<\/em>\r\n\r\n2\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <strong>then <\/strong><em>q<\/em> \u00ac \u00eb(<em>p<\/em>+<em>r<\/em>)\/2\u00fb\r\n\r\n3\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <em>MergeSort <\/em>(<em>A<\/em>,<em> p<\/em>,<em> q<\/em>)\r\n\r\n4\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <em>MergeSort <\/em>(<em>A<\/em>,<em> q<\/em>+1,<em> r<\/em>)\r\n\r\n5\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <em>Merge <\/em>(<em>A<\/em>,<em> p<\/em>,<em> q<\/em>,<em> r<\/em>) \/\/ merges<em> A<\/em>[<em>p..q<\/em>] with<em> A<\/em>[<em>q+1..r<\/em>]\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">It can be observed that given array A has p and r as lowest and highest indices. The mid-point p is computed so that the given array is divided into two subarrays. Then the merge sort procedure is called so that the array is recursively divided. Then the procedure uses merge to combine the sorted subarrays, The formal algorithm based on [3] for merging the subarray is given as follows:<\/p>\r\n&nbsp;\r\n\r\n<strong>Merge(<em>A<\/em>, <em>p<\/em>, <em>q<\/em>, <em>r<\/em>)<\/strong>\r\n\r\n&nbsp;\r\n\r\n1\u00a0\u00a0\u00a0 <em>n<\/em>1 \u00ac<em> q <\/em>\u2013<em> p <\/em>+ 1\r\n\r\n2\u00a0\u00a0\u00a0 <em>n<\/em>2 \u00ac<em> r <\/em>\u2013<em> q<\/em>\r\n\r\n3\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <strong>for <\/strong><em>i<\/em> \u00ac 1<strong> to <\/strong><em>n<\/em>1\r\n\r\n4\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <strong>do <\/strong><em>L<\/em>[<em>i<\/em>] \u00ac <em>A<\/em>[<em>p<\/em> + <em>i<\/em> \u2013 1]\r\n\r\n5\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <strong>for <\/strong><em>j<\/em> \u00ac 1<strong> to <\/strong><em>n<\/em>2\r\n\r\n6\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <strong>do <\/strong><em>R<\/em>[<em>j<\/em>] \u00ac <em>A<\/em>[<em>q<\/em> + <em>j<\/em>]\r\n\r\n7\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <em>L<\/em>[<em>n<\/em><em>1<\/em>+1] \u00ac \u00a5\r\n\r\n8\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <em>R<\/em>[<em>n<\/em><em>2<\/em>+1] \u00ac \u00a5\r\n\r\n9\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <em>i <\/em>\u00ac 1\r\n\r\n10\u00a0\u00a0\u00a0 <em>j <\/em>\u00ac 1\r\n\r\n11\u00a0\u00a0\u00a0 <strong>for <\/strong><em>k<\/em> \u00ac<em>p<\/em><strong> to <\/strong><em>r<\/em>\r\n\r\n12\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <strong>do if <\/strong><em>L<\/em>[<em>i<\/em>] \u00a3 <em>R<\/em>[<em>j<\/em>]\r\n\r\n13\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <strong>then <\/strong><em>A<\/em>[<em>k<\/em>] \u00ac <em>L<\/em>[<em>i<\/em>]\r\n\r\n14\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <em>i <\/em>\u00ac<em> i <\/em>+ 1\r\n\r\n15\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <strong>else <\/strong><em>A<\/em>[<em>k<\/em>] \u00ac <em>R<\/em>[<em>j<\/em>]\r\n\r\n16\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <em>j <\/em>\u00ac<em> j <\/em>+ 1\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">It can be observed that the elements of A is divided into the subarray L and R. Then the elements of L and R are compared and the smaller element is copied to the array A. If the subarray is exhausted, then the remaining elements of the other subarray is copied to\u00a0 array A. \u00a5 is given as sentinel so that comparison is not done for each and every time for the end of subarray.\u00a0 The following Example 1 illustrates the function of merge sort:<\/p>\r\n&nbsp;\r\n\r\n<strong>Example 1<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Use merge sort and sort the array of numbers {18,26,32,6,43,15,9,1,22,26,19,55,37,43,99,2}<\/p>\r\n&nbsp;\r\n<p class=\"hanging-indent\"><strong>Solution<\/strong><\/p>\r\n<p style=\"text-align: justify\"><span style=\"text-align: initial;font-size: 1em\">As said earlier, the first phase of merge sort is to divide the array into two parts using the middle element. The sub-arrays are divided further till one gets an array that cannot be\u00a0<\/span><span style=\"font-size: 1em;text-align: justify\">divided further. This division process is shown as below in Fig. 1<\/span><\/p>\r\n<img class=\"aligncenter size-full wp-image-211\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic1.png\" alt=\"\" width=\"976\" height=\"544\" \/>\r\n<p style=\"text-align: center\"><strong>Fig 1: Division process<\/strong><\/p>\r\n&nbsp;\r\n<p class=\"hanging-indent\">Then, the elements are merged is illustrated for L shown below in Fig. 2.<\/p>\r\n&nbsp;\r\n\r\n<img class=\"aligncenter size-full wp-image-212\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic2.png\" alt=\"\" width=\"742\" height=\"717\" \/>\r\n\r\n&nbsp;\r\n<p style=\"text-align: center\"><strong>Fig.2: Division Process of left Subarray<\/strong><\/p>\r\n<p class=\"hanging-indent\">The merge process of left subarray is shown below in Fig. 3<\/p>\r\n&nbsp;\r\n\r\n<img class=\"aligncenter size-full wp-image-213\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic3.png\" alt=\"\" width=\"742\" height=\"587\" \/>\r\n\r\n&nbsp;\r\n<p style=\"text-align: center\"><strong>Fig.3: Division Process of left Subarray <\/strong><\/p>\r\n<p class=\"hanging-indent\">Similarly this is repeated for right subarray as well.<\/p>\r\n&nbsp;\r\n<p class=\"hanging-indent\"><strong>Complexity analysis:<\/strong><\/p>\r\n<p style=\"text-align: justify\">If T(n) is the running time <strong><em>T<\/em><\/strong><strong>(<em>n<\/em>)<\/strong> of Merge Sort, then division process for computing the middle takes\u00a0 Q(1), the conquering step , i.e, solving 2 subproblems takes 2<em>T<\/em>(<em>n<\/em>\/2) and combining step, i.e., merging <em>n<\/em> elements takes Q(<em>n<\/em>). In short, the recurrence equation for merge sort is given as follows:<\/p>\r\n<img class=\"aligncenter size-full wp-image-214\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic4.png\" alt=\"\" width=\"277\" height=\"105\" \/>\r\n<p class=\"hanging-indent\">Or in short,<\/p>\r\n<em>T<\/em>(<em>n<\/em>) <em>= <\/em>Q(1) <em>i<\/em>f <em>n = <\/em>1\r\n\r\n&nbsp;\r\n\r\n<em>T<\/em>(<em>n<\/em>)<em> = <\/em>2<em>T<\/em>(<em>n<\/em>\/2)<em> + <\/em>Q(<em>n<\/em>) if<em> n &gt; <\/em>1\r\n\r\n&nbsp;\r\n<p class=\"hanging-indent\">Solving this yields, the complexity of merge sort can be derived as :<\/p>\r\n&nbsp;\r\n\r\n\u00de <em>T<\/em>(<em>n<\/em>)<em> = <\/em>Q(<em>n <\/em>lg<em> n<\/em>)\r\n\r\n&nbsp;\r\n<p class=\"hanging-indent\"><strong>Quicksort<\/strong><\/p>\r\n<p style=\"text-align: justify\">C.A.R. Hoare in 1962 designed Quicksort in 1962. Quicksort uses divide and conquer as a strategy for sorting elements of an array. Merge sort divides the array into two equal parts. But Quick sort unlike merge sort does not divide the array into equal parts. Instead, uses a pivot element to divide the array into two equal parts.<\/p>\r\nThe steps of Quicksort is given below:\r\n\r\n&nbsp;\r\n<p class=\"hanging-indent\"><strong><em>Divide step:<\/em><\/strong><\/p>\r\n<p style=\"text-align: justify\"><em>Pick any element (<strong>pivot<\/strong>) p in S. <\/em>This is done using a partitioning algorithm. Then, the partitioning element, p<em>artition S<\/em> <em>\u2013<\/em> <em>{p} into two disjoint groups<\/em><\/p>\r\n&nbsp;\r\n\r\n<em>S1 = {x <\/em><em>\u00ce<\/em><em> S \u2013 {p} | x &lt;= <strong>p<\/strong>}<\/em>\r\n\r\n<em style=\"font-size: 1em\">S2 = {x <\/em><em style=\"font-size: 1em\">\u00ce<\/em><em style=\"font-size: 1em\"> S \u2013 {p} | x <\/em><strong style=\"font-size: 1em\"><em>\u00b3<\/em><\/strong><em style=\"font-size: 1em\"> p}<\/em>\r\n\r\n&nbsp;\r\n<p class=\"hanging-indent\" style=\"text-align: justify\"><em><strong>Conquer step:<\/strong> recursively sort S1 and S2<\/em><\/p>\r\n<p class=\"hanging-indent\" style=\"text-align: justify\"><em><strong>Combine step:<\/strong> the sorted S1 (by the time returned from recursion), followed by p, followed by the sorted S2 (i.e., nothing extra needs to be done)<\/em><\/p>\r\n&nbsp;\r\n<p class=\"hanging-indent\" style=\"text-align: justify\">The informal Quicksort algorithm is informally given as follows:<\/p>\r\n&nbsp;\r\n\r\n1. if left &lt; right:\r\n\r\n&nbsp;\r\n\r\n1.1. Partition a[left...right] such that:\r\n\r\n&nbsp;\r\n\r\nall a[left...p-1] are less than\u00a0\u00a0\u00a0\u00a0 a[p], and\r\n\r\n&nbsp;\r\n\r\nall a[p+1...right] are &gt;= a[p]\r\n\r\n&nbsp;\r\n\r\n1.2. Quicksort a[left...p-1]\r\n\r\n&nbsp;\r\n\r\n1.3. Quicksort a[p+1...right]\r\n\r\n&nbsp;\r\n\r\n2. Combine the subarrays and Terminate\r\n\r\n&nbsp;\r\n\r\nThe formal algorithm of quicksort based on [1] is given as follows:\r\n\r\n&nbsp;\r\n\r\n<strong>Algorithm quicksort(A, first, last )<\/strong>\r\n\r\n&nbsp;\r\n\r\n%%\u00a0\u00a0 Input: Unsorted array A [first..last]\r\n\r\n&nbsp;\r\n\r\n%%\u00a0\u00a0 Output: Sorted array A\r\n\r\n&nbsp;\r\n\r\nBegin\r\n\r\n&nbsp;\r\n\r\nif (first &lt; last) then\r\n\r\n&nbsp;\r\n\r\nv = partition(A,first,last) %% find the pivot element\r\n\r\n&nbsp;\r\n\r\nquicksort([A, first,v-1])\r\n\r\n&nbsp;\r\n\r\nquicksort([A,v+1, last])\r\n\r\n&nbsp;\r\n\r\nend if\r\n\r\n&nbsp;\r\n\r\nend\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">It can be observed that the important phase of a quicksort algorithm is the partitioning stage where the given array is divided into two parts using a \u2018partition\u2019 procedure. While in merge sort, the middle element can be found directly. In quicksort, finding the middle element is\u00a0<span style=\"text-align: initial;font-size: 1em\">not a <\/span>straight forward<span style=\"text-align: initial;font-size: 1em\"> process. It is done using partition algorithms.<\/span><\/p>\r\n&nbsp;\r\n<p class=\"hanging-indent\"><strong>Partitioning Algorithms<\/strong><\/p>\r\n<p style=\"text-align: justify\">Partitioning algorithms are used to divide the given array into two subarrays. It is complicated process in quicksort compared to the division process of merge sort. There are two partitioning algorithms. One is by Lomuto partitioning algorithm and another by Hoare.<\/p>\r\n&nbsp;\r\n\r\nLet us discuss about Lomuto algorithm.\r\n\r\n&nbsp;\r\n<p class=\"hanging-indent\"><strong><em>Lomuto Algorithm<\/em><\/strong><\/p>\r\n<p style=\"text-align: justify\">Lomuto is a one directional partition algorithm. It scans from left to right and checks for the elements. If the number is less than the pivotal elements, the numbers are swapped. The following example illustrates Lomuto algorithm.<\/p>\r\n&nbsp;\r\n<p class=\"hanging-indent\"><strong>Example 2:<\/strong><\/p>\r\nUse Lomuto procedure to partition the following given array:\r\n\r\n&nbsp;\r\n\r\n<img class=\"aligncenter size-full wp-image-215\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic5.png\" alt=\"\" width=\"644\" height=\"707\" \/>\r\n\r\n<img class=\"aligncenter size-full wp-image-216\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic6.png\" alt=\"\" width=\"683\" height=\"850\" \/>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">It can be observed that all the elements of the left of 60 are less than 60 and all the elements on the right hand side is greater than 60.<\/p>\r\n&nbsp;\r\n\r\nThe formal algorithm based on [1] is given as follows:\r\n\r\nALGORITHM LomutoPartition(A[l..r])\r\n\r\n\/\/Partition subarray by Lomuto\u2019s algo using first element as pivot\r\n\r\n\/\/Input: A subarray A[l..r] of array A[0..n-1], defined by its \/\/left and right indices l and r (l \u2264 r)\r\n\r\n\/\/Output: Partition of A[l..r] and the new position of the pivot p &lt;- A[l]\r\n\r\ns &lt;- l\r\n\r\nfor i &lt;- l+1 to r do\r\n\r\nif A[i] &lt; p\r\n\r\ns &lt;- s+1\r\n\r\nswap(A[s], A[i])\r\n\r\nswap(A[l], A[s])\r\n\r\nreturn s\r\n\r\n&nbsp;\r\n<p class=\"hanging-indent\"><strong>Hoare Algorithm<\/strong><\/p>\r\n<p style=\"text-align: justify\">Another useful partition algorithm is called Hoare partition algorithm. This algorithm has two scans. one scan is from left-to-right and another scan is from right-to-left. The left to-right scan (using pointer <em>i<\/em>) aims to skip the smaller elements compared to the pivot and stop when an element is \u00b3 the pivot. Then right-to left scan (using pointer <em>j<\/em>) starts with the last element and skips over the elements that are larger than of equal to the pivot element. If <em>i &lt; j,<\/em> in that case <em>A[i]<\/em> and <em>A[j]<\/em> are swapped and the process is continued with the increment of i and decrement of j pointers. If one encounters the situation <em>i &gt; j,<\/em> then the pivot element is swapped with <em>A[j].<\/em><\/p>\r\n&nbsp;\r\n\r\nThe Hoare partition algorithm is given informally as follows:\r\n<ul>\r\n \t<li style=\"text-align: justify\">Choose pivot element from the array A, generally the first element<\/li>\r\n \t<li style=\"text-align: justify\">Search from left to right looking for elements greater than pivot.<\/li>\r\n \t<li style=\"text-align: justify\">Search from right to left looking for elements smaller than pivot.<\/li>\r\n \t<li style=\"text-align: justify\">When two elements are found, exchange them.<\/li>\r\n \t<li style=\"text-align: justify\">When two elements cross, exchange pivot element such that it is in final place.<\/li>\r\n \t<li style=\"text-align: justify\">Return the pivot element\u00a0 Formally, the Hoare partition algorithm is given as follows:<\/li>\r\n<\/ul>\r\n<strong>Algorithm Hoare_partition (A,first,last)<\/strong>\r\n\r\n&nbsp;\r\n\r\n%%\u00a0\u00a0 Input: Array A with elements 1 to n. First = 1 and last = n %%Output: Sorted array A\r\n\r\nBegin\r\n\r\n%%\u00a0\u00a0 First Element is the initial pivot\r\n\r\npivot = A [first]\r\n\r\n%%\u00a0\u00a0 Initialize the pointers i = first+1\r\n\r\nj =last\r\n\r\nflag = false predicate = true\r\n\r\n<span style=\"text-align: initial;font-size: 1em\">While (predicate) do<\/span>\r\n\r\nwhile (i\u00a0\u00a0\u00a0 \u00a3 j ) and (A[i]\r\n\r\ni = i + 1\r\n\r\nEnd while\r\n\r\nwhile (j \u00b3 pivot and j \u00b3 j = j-1\r\n\r\nEnd while\r\n\r\nif (j &lt; i)\r\n\r\nbreak\r\n\r\nelse\r\n\r\nA[i] \u00abA[j]\r\n\r\nEnd if\r\n\r\nEnd while\r\n\r\nA[first] \u00ab A[j]\r\n\r\nreturn j\r\n\r\nEnd\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">It can be observed that the algorithm initializes two pointers i and j and initial pivot. The pointers are updated based on the conditions that are discussed above as an informal procedure.<\/p>\r\nThe following example illustrates the application of Hoare partition to a given array.\r\n\r\n&nbsp;\r\n\r\n<strong>Example 3 :<\/strong>\u00a0\u00a0\u00a0\u00a0\u00a0 <strong>Apply <\/strong>the Hoare portioning algorithm for the following array:\r\n\r\n&nbsp;\r\n\r\n26,33,35,28,19,12,23.\r\n\r\n&nbsp;\r\n\r\nTo apply Hoare partition algorithm, the following steps are used:\r\n\r\n&nbsp;\r\n\r\nStep 1: Start with all data in an array, and consider it unsorted\r\n\r\n&nbsp;\r\n\r\nStep 2: Step 1, select a pivot (it is arbitrary), Let it\u00a0 be first element\r\n\r\n<img class=\"aligncenter size-full wp-image-217\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic7.png\" alt=\"\" width=\"408\" height=\"92\" \/>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Step 2, start process of dividing data into LEFT and RIGHT groups. The LEFT group will have elements less than the pivot and the RIGHT group will have elements greater that the pivot.<\/p>\r\n<p style=\"text-align: justify\">Step 3: If left element belongs to LEFT group, then left = left + 1. If right index element, belongs to RIGHT, then right = right \u2013 1. Exchange the elements if they belong to the other group.<\/p>\r\n&nbsp;\r\n\r\nThe final steps are shown below:\r\n\r\n<img class=\"aligncenter size-full wp-image-218\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic8.png\" alt=\"\" width=\"773\" height=\"656\" \/>\r\n\r\n&nbsp;\r\n<p class=\"hanging-indent\"><strong>Complexity analysis of Quicksort<\/strong><\/p>\r\n<p style=\"text-align: justify\">Quicksort is an effective and popular algorithm and its complexity analysis is given below:<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\"><strong>Best Case Analysis: <\/strong>The best case quicksort is a scenario where the partition element is exactly in the middle of the array. The best case quicksort is when the pivot partitions the list evenly. The resulting partitions of a best case are well balanced. Thus, the recurrence equation is given below:<\/p>\r\n&nbsp;\r\n\r\n<img class=\"size-full wp-image-59 aligncenter\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/Untitled-21.png\" alt=\"\" width=\"196\" height=\"82\" \/>Using the master\u2019s theorem, the complexity of the best case turns out as <em>T<\/em> (<em>n<\/em> )\u00ce<em>q<\/em> (<em>n<\/em> log <em>n<\/em>)\r\n\r\n&nbsp;\r\n\r\nIt can also be derived as follows:\r\n\r\n<img class=\"aligncenter size-full wp-image-219\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic9.png\" alt=\"\" width=\"763\" height=\"446\" \/>\r\n<p style=\"text-align: justify\"><strong>Worst Case Analysis: <\/strong>In the worst case, it can be observed that the partitions are no longer better than a linear list. This happens because the first element is always the pivot element. Hence, there is no element in the left hand side.<\/p>\r\n&nbsp;\r\n\r\n<img class=\"aligncenter size-full wp-image-221\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic10-1.png\" alt=\"\" width=\"672\" height=\"414\" \/>\r\n<p style=\"text-align: justify\"><strong>Worst Case Analysis: <\/strong>In the worst case, it can be observed that the partitions are no longer better than a linear list. This happens because the first element is always the pivot element. Hence, there is no element in the left hand side.<\/p>\r\n&nbsp;\r\n\r\nThe overall size of the tree is given as\r\n\r\n<img class=\"aligncenter size-full wp-image-222\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic11.png\" alt=\"\" width=\"165\" height=\"117\" \/>\r\n\r\n&nbsp;\r\n\r\nThus, the worst case complexity of quicksort is\u00a0<em>q<\/em>(<em>n<\/em>2<span style=\"text-align: initial;font-size: 1em\">).<\/span>\r\n\r\n&nbsp;\r\n<p class=\"hanging-indent\" style=\"text-align: justify\">In short, one can conclude as part of this module 10 that<\/p>\r\n\r\n<ul>\r\n \t<li style=\"text-align: justify\">Divide and Conquer often leads to a better solution.<\/li>\r\n \t<li style=\"text-align: justify\">Merge sort uses divide and conquer technique and sorts the elements in O(nlogn) time.<\/li>\r\n \t<li style=\"text-align: justify\">Quicksort uses divide and conquer strategy and sorts the elements in o(nlogn) time.<\/li>\r\n \t<li style=\"text-align: justify\">Master Theorem is helpful in solving recurrence equations.<\/li>\r\n<\/ul>\r\n<strong>References:<\/strong>\r\n<ol>\r\n \t<li style=\"text-align: justify\"><em>S.Sridhar , Design and Analysis of Algorithms , Oxford University Press, 2014.<\/em><\/li>\r\n \t<li style=\"text-align: justify\"><em>A.Levitin, Introduction to the Design and Analysis of Algorithms, Pearson Education, New Delhi, 2012.<\/em><\/li>\r\n \t<li style=\"text-align: justify\"><em>T.H. <\/em>Cormen, C.E. Leiserson, and R.L. Rivest, Introduction to Algorithms, MIT Press, Cambridge, MA 1992.<\/li>\r\n<\/ol>","rendered":"<p>&nbsp;<\/p>\n<p style=\"text-align: center\"><strong>Module 10:<\/strong><\/p>\n<p style=\"text-align: center\"><strong>Divide and Conquer Technique<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\" style=\"text-align: justify\">This module 10 introduces the concept of popular design technique called divide and conquer technique.<\/p>\n<p class=\"hanging-indent\" style=\"text-align: justify\">The Learning objectives of this module are as follows:<\/p>\n<ul>\n<li style=\"text-align: justify\">To understand the concept of Divide and Conquer<\/li>\n<li style=\"text-align: justify\">To understand applications of Divide and Conquer technique<\/li>\n<li style=\"text-align: justify\">To know about Merge Sort algorithm<\/li>\n<li style=\"text-align: justify\">To understand Quicksort Algorithm<\/li>\n<\/ul>\n<p><strong>What is a divide and Conquer Design Technique?<\/strong><\/p>\n<p style=\"text-align: justify\">Divide and conquer is an effective algorithm design technique. This design technique is used to solve variety of problems. In this module, we will discuss about applying divide and conquer technique for sorting problems. In this design paradigm, the problem is divided into subproblems. The subproblems are divided further if necessary. Then the subproblems are solved recursively or iteratively and the results of the subproblems are combined to get the final solution of the given problem.<\/p>\n<p>These are the important components of Divide and Conquer strategy:<\/p>\n<ol>\n<li>Divide: In this stage the given problem is divided into small problems. The smaller problems are similar to the original problem. But these smaller problems have reduced size, i.e., with less number of instances compared to original problem. If the subproblems are big, then the subproblems are divided further. This division process is continued till the obtained subproblems are smaller that can be solved in a straight forward manner.<\/li>\n<li>Conquer: The subproblems can be solved either recursively or non-recursively in a straight forward<span style=\"text-align: initial;font-size: 1em\"> manner.<\/span><\/li>\n<li>Combine: The solutions of the sub-problems can be combined to get the global result of the problems.<\/li>\n<\/ol>\n<p class=\"hanging-indent\"><strong>Advantages of Divide and Conquer Paradigm<\/strong><\/p>\n<ol>\n<li>The advantages of divide and conquer approach is that it is perhaps most commonly applied design technique and its application always leads to effective algorithms.<\/li>\n<li>It can be used to solve general problems.<\/li>\n<li>Divide and conquer paradigm is suitable for problems that are inherently parallel in nature.<\/li>\n<\/ol>\n<p><strong>Disadvantages of Divide and Conquer<\/strong><\/p>\n<ol>\n<li>The disadvantage of divide and conquer paradigm is that if division process is not carried in a proper manner, the unequal division of problem instances can result in inefficient implementation.<\/li>\n<\/ol>\n<p>Let us discuss about one of the most popular algorithm that is based on divide and conquer, i.e., merge sort.<\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\"><strong>Merge Sort<\/strong><\/p>\n<p style=\"text-align: justify\">Divide and conquer is the strategy used in merge sort. Merge sort was designed by the popular Hungarian mathematician John van Neumann. The procedure for merge sort is given informally as follows:<\/p>\n<ol>\n<li style=\"text-align: justify\">Divide: Divide the <em>n<\/em>-element sequence to be sorted into two subsequences of <em>n\/2<\/em> elements each.<\/li>\n<li style=\"text-align: justify\">Conquer: Sort the two subsequences recursively using merge sort in a recursive or non-recursive manner.<\/li>\n<li style=\"text-align: justify\">Combine: Merge the two sorted subsequences to produce the sorted answer.<\/li>\n<\/ol>\n<p><strong>Informal algorithm:<\/strong><\/p>\n<p class=\"hanging-indent\">Informally merge sort procedure is as follows:<\/p>\n<ol>\n<li>Divide the array A into subarrays L and R of size n\/2.<\/li>\n<li>Recursively sort the subarray L gives L sorted subarray<\/li>\n<li>Recursively sort\u00a0 the subarray R gives R sorted subarray<\/li>\n<li>Combine L and R sorted subarrays give final sorted array A<\/li>\n<\/ol>\n<p>The formal algorithm based on [3] is given as follows:<\/p>\n<p>&nbsp;<\/p>\n<p><strong><em>MergeSort <\/em><\/strong><strong>(<em>A<\/em>,<em> p<\/em>,<em> r<\/em>)<\/strong>\u00a0\u00a0\u00a0 <strong>\/\/ <\/strong>sort <em>A<\/em>[<em>p..r<\/em>] by divide &amp; conquer<\/p>\n<p>&nbsp;<\/p>\n<p>1\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <strong>if <\/strong><em>p<\/em> &lt; <em>r<\/em><\/p>\n<p>2\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <strong>then <\/strong><em>q<\/em> \u00ac \u00eb(<em>p<\/em>+<em>r<\/em>)\/2\u00fb<\/p>\n<p>3\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <em>MergeSort <\/em>(<em>A<\/em>,<em> p<\/em>,<em> q<\/em>)<\/p>\n<p>4\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <em>MergeSort <\/em>(<em>A<\/em>,<em> q<\/em>+1,<em> r<\/em>)<\/p>\n<p>5\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <em>Merge <\/em>(<em>A<\/em>,<em> p<\/em>,<em> q<\/em>,<em> r<\/em>) \/\/ merges<em> A<\/em>[<em>p..q<\/em>] with<em> A<\/em>[<em>q+1..r<\/em>]<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">It can be observed that given array A has p and r as lowest and highest indices. The mid-point p is computed so that the given array is divided into two subarrays. Then the merge sort procedure is called so that the array is recursively divided. Then the procedure uses merge to combine the sorted subarrays, The formal algorithm based on [3] for merging the subarray is given as follows:<\/p>\n<p>&nbsp;<\/p>\n<p><strong>Merge(<em>A<\/em>, <em>p<\/em>, <em>q<\/em>, <em>r<\/em>)<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>1\u00a0\u00a0\u00a0 <em>n<\/em>1 \u00ac<em> q <\/em>\u2013<em> p <\/em>+ 1<\/p>\n<p>2\u00a0\u00a0\u00a0 <em>n<\/em>2 \u00ac<em> r <\/em>\u2013<em> q<\/em><\/p>\n<p>3\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <strong>for <\/strong><em>i<\/em> \u00ac 1<strong> to <\/strong><em>n<\/em>1<\/p>\n<p>4\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <strong>do <\/strong><em>L<\/em>[<em>i<\/em>] \u00ac <em>A<\/em>[<em>p<\/em> + <em>i<\/em> \u2013 1]<\/p>\n<p>5\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <strong>for <\/strong><em>j<\/em> \u00ac 1<strong> to <\/strong><em>n<\/em>2<\/p>\n<p>6\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <strong>do <\/strong><em>R<\/em>[<em>j<\/em>] \u00ac <em>A<\/em>[<em>q<\/em> + <em>j<\/em>]<\/p>\n<p>7\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <em>L<\/em>[<em>n<\/em><em>1<\/em>+1] \u00ac \u00a5<\/p>\n<p>8\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <em>R<\/em>[<em>n<\/em><em>2<\/em>+1] \u00ac \u00a5<\/p>\n<p>9\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <em>i <\/em>\u00ac 1<\/p>\n<p>10\u00a0\u00a0\u00a0 <em>j <\/em>\u00ac 1<\/p>\n<p>11\u00a0\u00a0\u00a0 <strong>for <\/strong><em>k<\/em> \u00ac<em>p<\/em><strong> to <\/strong><em>r<\/em><\/p>\n<p>12\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <strong>do if <\/strong><em>L<\/em>[<em>i<\/em>] \u00a3 <em>R<\/em>[<em>j<\/em>]<\/p>\n<p>13\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <strong>then <\/strong><em>A<\/em>[<em>k<\/em>] \u00ac <em>L<\/em>[<em>i<\/em>]<\/p>\n<p>14\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <em>i <\/em>\u00ac<em> i <\/em>+ 1<\/p>\n<p>15\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <strong>else <\/strong><em>A<\/em>[<em>k<\/em>] \u00ac <em>R<\/em>[<em>j<\/em>]<\/p>\n<p>16\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <em>j <\/em>\u00ac<em> j <\/em>+ 1<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">It can be observed that the elements of A is divided into the subarray L and R. Then the elements of L and R are compared and the smaller element is copied to the array A. If the subarray is exhausted, then the remaining elements of the other subarray is copied to\u00a0 array A. \u00a5 is given as sentinel so that comparison is not done for each and every time for the end of subarray.\u00a0 The following Example 1 illustrates the function of merge sort:<\/p>\n<p>&nbsp;<\/p>\n<p><strong>Example 1<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Use merge sort and sort the array of numbers {18,26,32,6,43,15,9,1,22,26,19,55,37,43,99,2}<\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\"><strong>Solution<\/strong><\/p>\n<p style=\"text-align: justify\"><span style=\"text-align: initial;font-size: 1em\">As said earlier, the first phase of merge sort is to divide the array into two parts using the middle element. The sub-arrays are divided further till one gets an array that cannot be\u00a0<\/span><span style=\"font-size: 1em;text-align: justify\">divided further. This division process is shown as below in Fig. 1<\/span><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-211\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic1.png\" alt=\"\" width=\"976\" height=\"544\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic1.png 976w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic1-300x167.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic1-768x428.png 768w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic1-65x36.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic1-225x125.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic1-350x195.png 350w\" sizes=\"auto, (max-width: 976px) 100vw, 976px\" \/><\/p>\n<p style=\"text-align: center\"><strong>Fig 1: Division process<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\">Then, the elements are merged is illustrated for L shown below in Fig. 2.<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-212\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic2.png\" alt=\"\" width=\"742\" height=\"717\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic2.png 742w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic2-300x290.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic2-65x63.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic2-225x217.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic2-350x338.png 350w\" sizes=\"auto, (max-width: 742px) 100vw, 742px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: center\"><strong>Fig.2: Division Process of left Subarray<\/strong><\/p>\n<p class=\"hanging-indent\">The merge process of left subarray is shown below in Fig. 3<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-213\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic3.png\" alt=\"\" width=\"742\" height=\"587\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic3.png 742w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic3-300x237.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic3-65x51.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic3-225x178.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic3-350x277.png 350w\" sizes=\"auto, (max-width: 742px) 100vw, 742px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: center\"><strong>Fig.3: Division Process of left Subarray <\/strong><\/p>\n<p class=\"hanging-indent\">Similarly this is repeated for right subarray as well.<\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\"><strong>Complexity analysis:<\/strong><\/p>\n<p style=\"text-align: justify\">If T(n) is the running time <strong><em>T<\/em><\/strong><strong>(<em>n<\/em>)<\/strong> of Merge Sort, then division process for computing the middle takes\u00a0 Q(1), the conquering step , i.e, solving 2 subproblems takes 2<em>T<\/em>(<em>n<\/em>\/2) and combining step, i.e., merging <em>n<\/em> elements takes Q(<em>n<\/em>). In short, the recurrence equation for merge sort is given as follows:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-214\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic4.png\" alt=\"\" width=\"277\" height=\"105\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic4.png 277w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic4-65x25.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic4-225x85.png 225w\" sizes=\"auto, (max-width: 277px) 100vw, 277px\" \/><\/p>\n<p class=\"hanging-indent\">Or in short,<\/p>\n<p><em>T<\/em>(<em>n<\/em>) <em>= <\/em>Q(1) <em>i<\/em>f <em>n = <\/em>1<\/p>\n<p>&nbsp;<\/p>\n<p><em>T<\/em>(<em>n<\/em>)<em> = <\/em>2<em>T<\/em>(<em>n<\/em>\/2)<em> + <\/em>Q(<em>n<\/em>) if<em> n &gt; <\/em>1<\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\">Solving this yields, the complexity of merge sort can be derived as :<\/p>\n<p>&nbsp;<\/p>\n<p>\u00de <em>T<\/em>(<em>n<\/em>)<em> = <\/em>Q(<em>n <\/em>lg<em> n<\/em>)<\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\"><strong>Quicksort<\/strong><\/p>\n<p style=\"text-align: justify\">C.A.R. Hoare in 1962 designed Quicksort in 1962. Quicksort uses divide and conquer as a strategy for sorting elements of an array. Merge sort divides the array into two equal parts. But Quick sort unlike merge sort does not divide the array into equal parts. Instead, uses a pivot element to divide the array into two equal parts.<\/p>\n<p>The steps of Quicksort is given below:<\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\"><strong><em>Divide step:<\/em><\/strong><\/p>\n<p style=\"text-align: justify\"><em>Pick any element (<strong>pivot<\/strong>) p in S. <\/em>This is done using a partitioning algorithm. Then, the partitioning element, p<em>artition S<\/em> <em>\u2013<\/em> <em>{p} into two disjoint groups<\/em><\/p>\n<p>&nbsp;<\/p>\n<p><em>S1 = {x <\/em><em>\u00ce<\/em><em> S \u2013 {p} | x &lt;= <strong>p<\/strong>}<\/em><\/p>\n<p><em style=\"font-size: 1em\">S2 = {x <\/em><em style=\"font-size: 1em\">\u00ce<\/em><em style=\"font-size: 1em\"> S \u2013 {p} | x <\/em><strong style=\"font-size: 1em\"><em>\u00b3<\/em><\/strong><em style=\"font-size: 1em\"> p}<\/em><\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\" style=\"text-align: justify\"><em><strong>Conquer step:<\/strong> recursively sort S1 and S2<\/em><\/p>\n<p class=\"hanging-indent\" style=\"text-align: justify\"><em><strong>Combine step:<\/strong> the sorted S1 (by the time returned from recursion), followed by p, followed by the sorted S2 (i.e., nothing extra needs to be done)<\/em><\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\" style=\"text-align: justify\">The informal Quicksort algorithm is informally given as follows:<\/p>\n<p>&nbsp;<\/p>\n<p>1. if left &lt; right:<\/p>\n<p>&nbsp;<\/p>\n<p>1.1. Partition a[left&#8230;right] such that:<\/p>\n<p>&nbsp;<\/p>\n<p>all a[left&#8230;p-1] are less than\u00a0\u00a0\u00a0\u00a0 a[p], and<\/p>\n<p>&nbsp;<\/p>\n<p>all a[p+1&#8230;right] are &gt;= a[p]<\/p>\n<p>&nbsp;<\/p>\n<p>1.2. Quicksort a[left&#8230;p-1]<\/p>\n<p>&nbsp;<\/p>\n<p>1.3. Quicksort a[p+1&#8230;right]<\/p>\n<p>&nbsp;<\/p>\n<p>2. Combine the subarrays and Terminate<\/p>\n<p>&nbsp;<\/p>\n<p>The formal algorithm of quicksort based on [1] is given as follows:<\/p>\n<p>&nbsp;<\/p>\n<p><strong>Algorithm quicksort(A, first, last )<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>%%\u00a0\u00a0 Input: Unsorted array A [first..last]<\/p>\n<p>&nbsp;<\/p>\n<p>%%\u00a0\u00a0 Output: Sorted array A<\/p>\n<p>&nbsp;<\/p>\n<p>Begin<\/p>\n<p>&nbsp;<\/p>\n<p>if (first &lt; last) then<\/p>\n<p>&nbsp;<\/p>\n<p>v = partition(A,first,last) %% find the pivot element<\/p>\n<p>&nbsp;<\/p>\n<p>quicksort([A, first,v-1])<\/p>\n<p>&nbsp;<\/p>\n<p>quicksort([A,v+1, last])<\/p>\n<p>&nbsp;<\/p>\n<p>end if<\/p>\n<p>&nbsp;<\/p>\n<p>end<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">It can be observed that the important phase of a quicksort algorithm is the partitioning stage where the given array is divided into two parts using a \u2018partition\u2019 procedure. While in merge sort, the middle element can be found directly. In quicksort, finding the middle element is\u00a0<span style=\"text-align: initial;font-size: 1em\">not a <\/span>straight forward<span style=\"text-align: initial;font-size: 1em\"> process. It is done using partition algorithms.<\/span><\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\"><strong>Partitioning Algorithms<\/strong><\/p>\n<p style=\"text-align: justify\">Partitioning algorithms are used to divide the given array into two subarrays. It is complicated process in quicksort compared to the division process of merge sort. There are two partitioning algorithms. One is by Lomuto partitioning algorithm and another by Hoare.<\/p>\n<p>&nbsp;<\/p>\n<p>Let us discuss about Lomuto algorithm.<\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\"><strong><em>Lomuto Algorithm<\/em><\/strong><\/p>\n<p style=\"text-align: justify\">Lomuto is a one directional partition algorithm. It scans from left to right and checks for the elements. If the number is less than the pivotal elements, the numbers are swapped. The following example illustrates Lomuto algorithm.<\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\"><strong>Example 2:<\/strong><\/p>\n<p>Use Lomuto procedure to partition the following given array:<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-215\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic5.png\" alt=\"\" width=\"644\" height=\"707\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic5.png 644w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic5-273x300.png 273w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic5-65x71.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic5-225x247.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic5-350x384.png 350w\" sizes=\"auto, (max-width: 644px) 100vw, 644px\" \/><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-216\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic6.png\" alt=\"\" width=\"683\" height=\"850\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic6.png 683w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic6-241x300.png 241w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic6-65x81.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic6-225x280.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic6-350x436.png 350w\" sizes=\"auto, (max-width: 683px) 100vw, 683px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">It can be observed that all the elements of the left of 60 are less than 60 and all the elements on the right hand side is greater than 60.<\/p>\n<p>&nbsp;<\/p>\n<p>The formal algorithm based on [1] is given as follows:<\/p>\n<p>ALGORITHM LomutoPartition(A[l..r])<\/p>\n<p>\/\/Partition subarray by Lomuto\u2019s algo using first element as pivot<\/p>\n<p>\/\/Input: A subarray A[l..r] of array A[0..n-1], defined by its \/\/left and right indices l and r (l \u2264 r)<\/p>\n<p>\/\/Output: Partition of A[l..r] and the new position of the pivot p &lt;- A[l]<\/p>\n<p>s &lt;- l<\/p>\n<p>for i &lt;- l+1 to r do<\/p>\n<p>if A[i] &lt; p<\/p>\n<p>s &lt;- s+1<\/p>\n<p>swap(A[s], A[i])<\/p>\n<p>swap(A[l], A[s])<\/p>\n<p>return s<\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\"><strong>Hoare Algorithm<\/strong><\/p>\n<p style=\"text-align: justify\">Another useful partition algorithm is called Hoare partition algorithm. This algorithm has two scans. one scan is from left-to-right and another scan is from right-to-left. The left to-right scan (using pointer <em>i<\/em>) aims to skip the smaller elements compared to the pivot and stop when an element is \u00b3 the pivot. Then right-to left scan (using pointer <em>j<\/em>) starts with the last element and skips over the elements that are larger than of equal to the pivot element. If <em>i &lt; j,<\/em> in that case <em>A[i]<\/em> and <em>A[j]<\/em> are swapped and the process is continued with the increment of i and decrement of j pointers. If one encounters the situation <em>i &gt; j,<\/em> then the pivot element is swapped with <em>A[j].<\/em><\/p>\n<p>&nbsp;<\/p>\n<p>The Hoare partition algorithm is given informally as follows:<\/p>\n<ul>\n<li style=\"text-align: justify\">Choose pivot element from the array A, generally the first element<\/li>\n<li style=\"text-align: justify\">Search from left to right looking for elements greater than pivot.<\/li>\n<li style=\"text-align: justify\">Search from right to left looking for elements smaller than pivot.<\/li>\n<li style=\"text-align: justify\">When two elements are found, exchange them.<\/li>\n<li style=\"text-align: justify\">When two elements cross, exchange pivot element such that it is in final place.<\/li>\n<li style=\"text-align: justify\">Return the pivot element\u00a0 Formally, the Hoare partition algorithm is given as follows:<\/li>\n<\/ul>\n<p><strong>Algorithm Hoare_partition (A,first,last)<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>%%\u00a0\u00a0 Input: Array A with elements 1 to n. First = 1 and last = n %%Output: Sorted array A<\/p>\n<p>Begin<\/p>\n<p>%%\u00a0\u00a0 First Element is the initial pivot<\/p>\n<p>pivot = A [first]<\/p>\n<p>%%\u00a0\u00a0 Initialize the pointers i = first+1<\/p>\n<p>j =last<\/p>\n<p>flag = false predicate = true<\/p>\n<p><span style=\"text-align: initial;font-size: 1em\">While (predicate) do<\/span><\/p>\n<p>while (i\u00a0\u00a0\u00a0 \u00a3 j ) and (A[i]<\/p>\n<p>i = i + 1<\/p>\n<p>End while<\/p>\n<p>while (j \u00b3 pivot and j \u00b3 j = j-1<\/p>\n<p>End while<\/p>\n<p>if (j &lt; i)<\/p>\n<p>break<\/p>\n<p>else<\/p>\n<p>A[i] \u00abA[j]<\/p>\n<p>End if<\/p>\n<p>End while<\/p>\n<p>A[first] \u00ab A[j]<\/p>\n<p>return j<\/p>\n<p>End<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">It can be observed that the algorithm initializes two pointers i and j and initial pivot. The pointers are updated based on the conditions that are discussed above as an informal procedure.<\/p>\n<p>The following example illustrates the application of Hoare partition to a given array.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>Example 3 :<\/strong>\u00a0\u00a0\u00a0\u00a0\u00a0 <strong>Apply <\/strong>the Hoare portioning algorithm for the following array:<\/p>\n<p>&nbsp;<\/p>\n<p>26,33,35,28,19,12,23.<\/p>\n<p>&nbsp;<\/p>\n<p>To apply Hoare partition algorithm, the following steps are used:<\/p>\n<p>&nbsp;<\/p>\n<p>Step 1: Start with all data in an array, and consider it unsorted<\/p>\n<p>&nbsp;<\/p>\n<p>Step 2: Step 1, select a pivot (it is arbitrary), Let it\u00a0 be first element<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-217\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic7.png\" alt=\"\" width=\"408\" height=\"92\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic7.png 408w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic7-300x68.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic7-65x15.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic7-225x51.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic7-350x79.png 350w\" sizes=\"auto, (max-width: 408px) 100vw, 408px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Step 2, start process of dividing data into LEFT and RIGHT groups. The LEFT group will have elements less than the pivot and the RIGHT group will have elements greater that the pivot.<\/p>\n<p style=\"text-align: justify\">Step 3: If left element belongs to LEFT group, then left = left + 1. If right index element, belongs to RIGHT, then right = right \u2013 1. Exchange the elements if they belong to the other group.<\/p>\n<p>&nbsp;<\/p>\n<p>The final steps are shown below:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-218\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic8.png\" alt=\"\" width=\"773\" height=\"656\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic8.png 773w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic8-300x255.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic8-768x652.png 768w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic8-65x55.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic8-225x191.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic8-350x297.png 350w\" sizes=\"auto, (max-width: 773px) 100vw, 773px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\"><strong>Complexity analysis of Quicksort<\/strong><\/p>\n<p style=\"text-align: justify\">Quicksort is an effective and popular algorithm and its complexity analysis is given below:<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\"><strong>Best Case Analysis: <\/strong>The best case quicksort is a scenario where the partition element is exactly in the middle of the array. The best case quicksort is when the pivot partitions the list evenly. The resulting partitions of a best case are well balanced. Thus, the recurrence equation is given below:<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-59 aligncenter\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/Untitled-21.png\" alt=\"\" width=\"196\" height=\"82\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/Untitled-21.png 196w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/Untitled-21-65x27.png 65w\" sizes=\"auto, (max-width: 196px) 100vw, 196px\" \/>Using the master\u2019s theorem, the complexity of the best case turns out as <em>T<\/em> (<em>n<\/em> )\u00ce<em>q<\/em> (<em>n<\/em> log <em>n<\/em>)<\/p>\n<p>&nbsp;<\/p>\n<p>It can also be derived as follows:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-219\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic9.png\" alt=\"\" width=\"763\" height=\"446\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic9.png 763w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic9-300x175.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic9-65x38.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic9-225x132.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic9-350x205.png 350w\" sizes=\"auto, (max-width: 763px) 100vw, 763px\" \/><\/p>\n<p style=\"text-align: justify\"><strong>Worst Case Analysis: <\/strong>In the worst case, it can be observed that the partitions are no longer better than a linear list. This happens because the first element is always the pivot element. Hence, there is no element in the left hand side.<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-221\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic10-1.png\" alt=\"\" width=\"672\" height=\"414\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic10-1.png 672w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic10-1-300x185.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic10-1-65x40.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic10-1-225x139.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic10-1-350x216.png 350w\" sizes=\"auto, (max-width: 672px) 100vw, 672px\" \/><\/p>\n<p style=\"text-align: justify\"><strong>Worst Case Analysis: <\/strong>In the worst case, it can be observed that the partitions are no longer better than a linear list. This happens because the first element is always the pivot element. Hence, there is no element in the left hand side.<\/p>\n<p>&nbsp;<\/p>\n<p>The overall size of the tree is given as<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-222\" src=\"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic11.png\" alt=\"\" width=\"165\" height=\"117\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic11.png 165w, https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-content\/uploads\/sites\/48\/2018\/07\/P05M10Pic11-65x46.png 65w\" sizes=\"auto, (max-width: 165px) 100vw, 165px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p>Thus, the worst case complexity of quicksort is\u00a0<em>q<\/em>(<em>n<\/em>2<span style=\"text-align: initial;font-size: 1em\">).<\/span><\/p>\n<p>&nbsp;<\/p>\n<p class=\"hanging-indent\" style=\"text-align: justify\">In short, one can conclude as part of this module 10 that<\/p>\n<ul>\n<li style=\"text-align: justify\">Divide and Conquer often leads to a better solution.<\/li>\n<li style=\"text-align: justify\">Merge sort uses divide and conquer technique and sorts the elements in O(nlogn) time.<\/li>\n<li style=\"text-align: justify\">Quicksort uses divide and conquer strategy and sorts the elements in o(nlogn) time.<\/li>\n<li style=\"text-align: justify\">Master Theorem is helpful in solving recurrence equations.<\/li>\n<\/ul>\n<p><strong>References:<\/strong><\/p>\n<ol>\n<li style=\"text-align: justify\"><em>S.Sridhar , Design and Analysis of Algorithms , Oxford University Press, 2014.<\/em><\/li>\n<li style=\"text-align: justify\"><em>A.Levitin, Introduction to the Design and Analysis of Algorithms, Pearson Education, New Delhi, 2012.<\/em><\/li>\n<li style=\"text-align: justify\"><em>T.H. <\/em>Cormen, C.E. Leiserson, and R.L. Rivest, Introduction to Algorithms, MIT Press, Cambridge, MA 1992.<\/li>\n<\/ol>\n","protected":false},"author":4,"menu_order":4,"template":"","meta":{"pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":["mr-s-sridhar"],"pb_section_license":""},"chapter-type":[],"contributor":[58],"license":[],"class_list":["post-47","chapter","type-chapter","status-publish","hentry","contributor-mr-s-sridhar"],"part":3,"_links":{"self":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/pressbooks\/v2\/chapters\/47","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/pressbooks\/v2\/chapters"}],"about":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/wp\/v2\/types\/chapter"}],"author":[{"embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/wp\/v2\/users\/4"}],"version-history":[{"count":6,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/pressbooks\/v2\/chapters\/47\/revisions"}],"predecessor-version":[{"id":224,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/pressbooks\/v2\/chapters\/47\/revisions\/224"}],"part":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/pressbooks\/v2\/parts\/3"}],"metadata":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/pressbooks\/v2\/chapters\/47\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/wp\/v2\/media?parent=47"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/pressbooks\/v2\/chapter-type?post=47"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/wp\/v2\/contributor?post=47"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/wp\/v2\/license?post=47"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}