re OA Question 1. Explain merge sort problem using divide and conquer technique. Give an ample ex Quick Sort Quick sort is a sorting algorithm that uses the divide and conquer srs method division is dynamically carried out. The three steps of quick sort ar « * Divide : Split the array into two sub arrays that each element in the le is less than or equal the middle element and each element in the right greater than the middle element. The splitting of the array into two sub based on pivot element. All the elements that are less than pivot should sub array and all the elements that are more than pivot should be in rs i | Elements that are Pivot element Elements that are less than pivot greater than pivot Fig. 3.8.1 Quick sort method * Conquer : Recursively sort the two sub arrays. a lis * Combine : Combine all the sorted elements in a group to form * elements.J -- 8 ‘Conquer Algorithm “Anaysis and Design of Algorithms 345 Dri ere \ lements, but in In merge sort the division of array is based on the positions of array el i quick sort this division is based on actual value of the element. Consider an array A[i] where i is ranging from 0 ton ~ 1 then we can formulate the division of array elements as Let us understand this algorithm with the help of some example. AIO}... Afm=1},Afm],Afm+1]...Afn—1] Saye |) Se These elements are Mid These elements are less than Afr} ‘greater than Alm] Step 1: Low High 50 | 30 70 i/ Pivot” j We will now split the array in two parts. | The left sublist will contain the elements less than Pivot (i. 50) and right sublist contains ‘ty | elements greater than Pivot. by - ae | We will increment i. If Afi] < Pivot, we will continue to increment it until the element pointed by {_1is greater than A[Low]. Pivot i j Increment i as A[i] < A [Low]. TECHNICAL PUBLICATIONS® - An up thrust for knowledgeDivide and Conauar Algorithm ree cei have left sublist Pivot is shifted Now we have right sublist en 1 wil Al ond ats pee ye © wills start comparing Ali] with Allow! or © AlPivot). sl TECHNICAL PuBLicATiIONs® ~ An up thrust for knowledget element as pivot. From second elemer compare all the elements with pivot value (ie “ All nents less than pivot will occupy left sublist and all elements greater than pivot will occupy right sublist, Thus pivot will occupy its proper position Se ae Left sublist_ Right sublist The above procedure will be repeated for each sublists recursive] and newer sub-sub lists will be generated. ll eee ” TECHNICAL PUBLICATIONS” - An up thrust for knowledgeIf ALi] < Pivot, incrementi tf PAU) > Pivot, decrement j ~ Swap(Afi, All) ia ‘Swap(A\i), All) (75) Swap(Al], Pivot) 5 105 60/90 75 items smaller J greater than 50° Pivot than 50 TECHNICAL PUBLICATIONS® - An up thrust for knowledgeAnalysis and Design of Algorithms 3-62 Did and Conuer Ag —_—_ewrs OE CA Art Pass 2a (left sublist) 45/40/20 30 ee ad Pivot 45| 40/20/30)». Swap(A(], Pivot) vy | 30) 40| 20 | 45) Pass 2b (Right sublist) }00] 80 70 105 60 90 7 ‘400 75 70 105 60 90 80 i j 400 75 70 80 60 90 105 ji Swap(Ali), Pivot) Pivot "90/75 70/80 60 100105 Thus continuing in this fashion, by sorting each sub-sublists finally we get the sorté list as 20/30 40/45 50 60 70 75 80 90 100 105 Write the Quick sort algorithm. Track the same on data set 47 Solution : Arrange the elements in an array. Step 1: Pivot i j If A [i] < A [pivot], increment i. If A [j] > Alpivot], decrement j TECHNICAL PUBLICATIONS® An up thrust for knowledge| Exchange Af] & A[Pivot] Left sublist Right sublist ‘Swap Ai] and AG) q] stp A [Pivot] Sat ‘Swap A (Pivot) and A {] Pivot j Thus two sublists are Step 3 : Now sorting sub-sublist, Pivot i TECHNICAL PUBLICATIONS® - An up thrust for knowledgeNow swap A [i] 7] and Atl Swap A[]] and A [Pivot} TECHNICAL PUBLICATIONS® - An up thrust for knowledgeDivide and Conquer Algorithm step 2: Now sorting two sublists using quick sort technique. s{o}4je Pivot i) Pivot 1 j ‘Swap Al} and A(Pivot} sia laie Pivot i j ‘Swap Ali] and Af] Pivot i—ei—ei=—j [ET Tel? Pivot joi ‘Swap A[Pivot] and Aj] | a]e[s[ele <7 Left Right sublist sublist Step 3: We will sort two sublists obtained in step 2. Step 4: We will combine all the sublists obtained in step 2 and step 3. Pivot ij Pivot il No swapping No swapping The resultant list will be ea Milustrate the working of quick sort on input __ instance 25, 29, 30, 35, 42, 47, 50, 52, 60. Comment on nature of input ie, best average case. GTU This is a sorted list Goon worst case or cee! TECHNICAL PUBLICATIONS® - An up thrust for knowledgeAnalysis and Design of Algorithms 9-56 DWM and Conan el “Aen Solution ; As all the elements of given list are already sorted, applying qu; ~ positioning pivot as the extreme left or right element will cause to work auc sory mode. Hence time complexity for worst case is O(n). Similarly the average a « se case time complexity ie, O(n logn) can be achieved if we select pivot ele, a random position of list. se Algorithm The quick sort algorithm is performed using following two important functions Quick and partition. Let us see them- Algorithm Quick(A(0...n-1],lowhigh) ; //Problem Description : This algorithm performs sorting of fom )then : (//split the array into two sub arrays m © partition(A[low...high])// m is mid of the array Quick(Aflow...m-1)) Quick(A[mid +1...high]) In above algorithm call to partition algorithm is given. The partition pe arrangement of the elements in ascending order. The recursive quick routine dividing the list in two sub lists. The pseudo code for Partition is as given below - Algorithm Partition (Allow...high]) //Problem Description: This algorithm partitions the //subarray using the first element as pivot element /ftaput: A subarray A with low as left most index of the //axray and high as the rightmost index of the array. //Output: The partitioning of array A is done and pivot //occupies its proper position. And the rightmost index of /{the list is retumed pivot — Aflow] i Clow jchigh+1 while(i<=}) do while(A(j]> =pivot) do Te if(i<=}) then swap(Ali],Alj])//swaps Ali] and Ali) TECHNICAL PUBLICATIONS” - An up thrust for knowled: —Cla) = 2C(n/2)+n fn) € nt adel a= 2and b =2. from case 2 we get a = b4 ie. 2 = 2!, we get Tin) ie. C(n) = O(n4log n) : C(n) = O(nlogn) complexity of quick sort is @(n log > n). TECHNICAL PUBLICATIONS® - An up thrust for knowiedgeWe can obtain the best case time complexity of quick sort using substitution metho as well. Consider equation (1) once again C(n) = C (n/2) + C(n/2) +n Cn) = 2C (n/2)+n We assume n = 2K since each time the list is divided into two equal halves. The equation becomes, Ck) = 2c (2k /2)42k = 2c (2k-1)42k Now substitute C (2K- 1) = 20 (2k-2) 4 gk-1 We get C(2‘) Bee eke) skal pak (ak) = 22 2k-2) 4 2.2k-1 4 ok meDaG(OkE2) poke, 2k Carp) G2 ka a) ear k TECHNICAL PUBLICATIONS® - An up thrust for knowledgelogon [By taking logarithm on both sides] n-O+logon-n Cin) n-0+ loga:n : it is proved that best case time complexity of quick sort is @(n log n). Worst case (sorted array) ‘The worst case for quick sort occurs when the pivot is a minimum or maximum of all the elements in the list. This can be graphically represented as TECHNICAL PUBLICATIONS® - An up thrust for knowledge(1) + C(n = 2) + n CQ) +Ci@-3) +n TECHNICAL PUBLICATIONS® - An up thrust+Cavg(n- 2)] (n= 1)* (n—-1) = 2Cayg (n-1) + (2n- 1) ( =) + (n= 1)< (n+ 1) * Cayg (n- 1) + 2n (n= 1)+2n = (m+1)* Cavg (a- 1)+C’n Adding and canceling these equations nN © A Erle , in) < Ain) + Ey we get ie NAN = 2) + <= ea ee Lee l = AQ) < Calpe pt ttt Cavg(n) = (+1) + An) ie. (n+ 1) * A(n) < C"(n+1) logn A(l) < A()+ S + Cayg(n) = © (n log n) TECHNICAL PUBLICATIONS® - An up thrust for knowledgeEER REA a Are naneee oo ae ee 8 2 3 : § & 3 = = 2 g eo S 3 § 3 & afor knowledgelj 37, 11, 10% | following data : 36, “Example 3.8.4; Trace the quick sort algorithm for the 72, 65, 98, 88, 78. + Is quick sort a stable sorting method ? Justify | Example 3.8. Example 3.8.6 : Search the element 'y’ from the list s, e, 4% & h. Show each step. TECHNICAL PUBLICATIONS® - An up thrust for knowledge