Q.6. Explain selection sort with the help of an examp1e- sare & gre frcraws Bis at isa FATS! Ans. To sort a given list, one of the easiest way is by using sel sort, in selection sort, the successive elements are selected in order and placed into their proper positions. It begins by finding the least element in the list. A search is performed to locate the least element. When this least element is found, it is then interchanged with the first element in the list. Next search for the second smallest element among the remaining elements of the list is carried out. The process of searching for the elements with the next smallest value and placing it in its proper position continues until the whole list is sorted in some ection, order (ascending or descending).Complexity of the selection Sort i In the selection sort method during the first pass (n-1), elements are compared in order to locate the element with smallest key. There are (n-2) comparisons during second pass to locate the second smallest key and the whole process continues until all the element follows some order (either increasing or descreasing). From this discussion we have: : f(a) =(-1) +(n-2)+ (2-3) t.... 241 =1/2n (n- 1) In general, for the it pass of the sort, (ni) comparisons are needed inorder to locate the i** element with the smallest key. The total number ofcomparisons are therefore: Each pass interchanges maximum elements thus, the maximum number of interchanges for the sort are n—1. ¥ (0-1) = $n(n- ) tI =0(n’)Q.7. What is quick sort? Explain it with suitable example. faeaa We aan Slat 8? Sag aT SAT BMT FA AAT Ans. Quick sort is also known as “Partition Exchange Sort”. It is a very fast method of sorting. In this method of sorting, the given list is divided into smaller parts or sub lists and each sub list is sorted individually. Lastly combines the results of all sub lists find to the complete sorted list. In the process of dividing the original list first we take an element called Pivot then arrange all small element in left of pivot and all greater elements from pivot are arranged in the right of pivot. Example : Suppose a list of an array consist of 12 elements as: 45, 30, 10, 50, 75, 90, 40, 60, 95, 20, 80, 70© ga frawe Wie “orelerr erst ag” Ha | aH Ta, ser I aE ale | aw ag a fee caftén af ya fafa, fag Gat at R—SE a oraren Sagferat H ser qa tT TH THE AH srer—srerr wie frre Gre BI ofa Hel ate st fA Bae FO & foe, wh seg vio St fer 3H HI ag aah Bh aie’ at wiver F yea, TH UH Te, FA pivot Fea z, a aa va wet at G2 wet A pivot’ af sik srafera He F TT pivot aa3 wi aati F pivot & ae ak crafted wet El Sq : AM cife UH at 12 Ta a Te, A: \ 45, 30, 10, 50, 75, 90, 40, 60, 95, 20, 80, 70 Solution: Step 1 A % & | & A & A & By Ay 1 @® 0 0 5 7% 90 0 6 % 2 a0 (70) = — Scanning from right to left, the first number encountered that has value less than 45 is 20. Thus interchange both: ae 3 a Ga BG Geet der 20 Freed @, freer a 45 8 A tam: oa Ht seacaen 4 4° 5 % & & & ee OH @ 0 0 9 % 9 0 © % @ H 7 Ay Ay Scanning from left to right, the first element encountered that has value greater than 45 is 50, so exchange both of them. at a ot Br SEK, Ve 1a 50 fram @, fee AM 45 & AST tafe SHY args FEA a a a a & & & % % % Ay Ay a 3 10 @) 7% 9 40 6 25) 80 70 = ee Scanning from right to left, the first element encountered that has value less than 45 is 40. So replace both. ‘ ae} ad Ga HA, Vee Tel 40 Fram &, fea a 45 FH > 8 Rey Sri st ree —aeet BE a eT /™ 0 10 @ 7% .9 @ 0 % s 0 70 = =Scanning from left to right, the first element encounte; has value greater than 45 is 75, so exchange both of them, and 8 at Br STW We 75 Frere &, FSR AT 45 see 3, safee Ohi A sreat—aee fen orm 2 S A B® & & BR & AB ay a 2 30 0 9) @ |» % 0 50 B% i \sublist red that Tsublist Thus, 45 is placed in its proper position and the Process jg continued for the two sublist thus obtained, one sublist which has less value than 45 and the second, which has greater value than 45, We can sort the two sublists (20, 30, 10,40) and (90, 75,60, 95, 50.80, 70) by applying same method. FA: 45 THR TE SIM W Ta Vat Wa ae, Sie oq oa a sofa & fer sent wi, ue saat fared ar 45 8 aH eae aad fae AP 45 & saftey 21 eH Sri sagfert (20, 30, 10, 40) am (90, 75, 60, 95, 50, 80, 70) a até Gam fale amt & arr aR aH a1 f Taking I Sublist ( weet saqet & aA a) aa | 30 10 ial pa "Let 20 be placed at its proper position. Thus, while scanning from right-to-left the first element encountered that has value less than 20 is 10, so exchange both of them. HR 20 1 Ses FE BIW Tad Ul om: at Bat Sa aS SH Tee Tes 10. fem &, free aA 20 8 aa sa 2, safe Si A seT— ae aa tl a | a © » @ w Now, scanning from left to right the first element encountered that has value greater than 20 is 30, exchange both of them. a aa, ae @ at Sr HG TURE aa 30 Frere @, freer FA 20 afte ¢, SH a sqc—aea aa é1 a, 10 a @ 4 =: |@2Taking U Sublist (11 Sagat cA ay) ¢ 4 3 a, a, % ayy ay, 7% 60 9% 50 9 (0) — Let 90 be places at its Proper position. Thus, while scanning from right-to-left, the first element encountered that has value less | than 90 is 70, so exchange both of them. AMT 90 il Sag wet CIR Tae G1 sa: at a ad Ss wea & ch, <= 70 fram @, fia ar 90 8 am é, safe SH at aea—aeT a \ & % 8 & a a, a, @ 5 o & 0 » @ — ‘ Now, scanning from left to right, the first element encountered _| that has value greater value than 90 is 95, so exchange both of them. : Fa, AE S TE SHAW, Teen wes 95 freien @, farre A 90 8 afew (4 vafag Shi at orec—aca at 1 a A AY, 70 75 6 @) 50 8. @) =, — Now, scanning from left to right, the first element encountered that has value greater than 90 is 80, so exchange both of them: | aa, are 8 are ha H, Weer Tes 95 frre @, farsa AM 80 8 aie & rafay eri A oree—aee wet & a mH A Ay Ay 70 75 60 8 50, 90 95 At the end, 90 is placed as its proper position. Thus, the element efore 90 have smaller values and those which follow 90, has greater | Values, This is again split in to two lists, we can sort these siiblists by » *Pplying same method as: | TH, 90 a sak aa ea TH Te feat TT 8 ara: 90 H uea H Ta °0m da aa é aa 90 ar SrTATT HCA areH aT ATA ores Che Vi ae GL: {fete fe od @, oe et org Boo fe a TE A i“Taking New I Sublist (9 1 37qet # A aw): ‘ 4% 8 @;7% © 2 = In this, we have to places element 70 at its proper Positj scanning is to be done from right to left and the searching js tobe don forthe first smaller valued element. The first smaller valued elage’® so encountered is 50, so, exchanhing both of them results’into; ah, UH es 70 HH EH TE TAT Tae Gi Fae wea Te ay wet & fore eam aE @ aM a Tt Te A eH Set Bee aay aI We 50 fret 2, gafere Sri at a a ele se fea a & a 8 5 @ o 9 @) ce, = Now, scanning is to be done from left to rij greater valued element than 70, which is 75, s them as: Se 70% STATA SH AM TT Ta a wea HAY fore, aN a a wait sont 2, ae wet 75 @, safer oh Ht sea—oea at Seis ars 8 ©) © 0 © 4 a Now, scanning from right to left the first element encountered that has, value smaller than 70 is 60, so exchange results into: oe, ed & a SH TR yee aa GO fram S, fea AA 708 am @, gafem siee—aea FeIgER UOTE San a 50 ; Sy 078 | sublist {I sublist We can observe that the element in @,oa,,) are all already sorted. So we take the new sublist for Sorting using same mehod. Eo FICO HL TRA EPH Cay, a.) H, aH MEA A HE TEN EA TH aifen % fore wa FAR aT Hein ec ae Sue A aa Hl ao, a a 8° ion. §5 ght to obtain the first ‘0 we exchange both of4 N TN) = TNs TS +(N-1)+ a Z ar +(N-1) +t... . = 2i+Ni+K (where k is constant) 4 = N+Nlog,N+K But, we have N= 2i and i = log, N. So, T (N)= OWN log, N) Worst case Average case CD Q. 8. Explain heap sort along with algorithm. Ans. Heap is considered as a complete binary tree, with the Propery . that the value of each node is at least as large as the value of its children nodes: This implies that the root of the heap has the largest key-value. Heap is mainly of two types: i (1) Descending Heap: In descending heap or max heap the value of child or node is less than or equal to the value of root. (2) Ascending Heap: In ascending heap or min heap the value of child node is greater than or equal to the value of root. In heap sorting, we first set the root value or thedargest value of list and then start comparing and swaping of next element with root first and Next element. Example : Sort the Heap of the figure as shown belowStep 2 Solution : Step 1 Complexity of Heap Sort Since we are using a complete binary tree, then it should be noted that “k” level has “K—1” number of nodes. Conversly, if it has “n nodes then it has log,n levels. Thus, the depth of a complete binary tree of “n” nodes is [log,n].The worst case analysis of heap sortis easier then the average case. The worst case for the heap sort, perform the number of comparison which is given by the depth of the tree. The time complexity is given by: Step 3 Step 4 Hence, heap sort is of the complexity O(nlog,n). The average case for the heap sort is also O(nlog,n).. a ae nee note on bubble sort. Ans. Bubble ee agg! Bubble sort differ. eo well known and most po. sort instead of ‘om the selection sort in some res, oF finding the smallest element, in thi : performing an interchange two successive records are 10) immediately upon discovering that they are not in proper Se! order. : Bubble sort is sometimes called “Sorting by Exchange” as in ord to find the successive smallest elements, the whole method relies heavily on the exchange of adjacent elements. : This sorting technique will cause elements with small keys to move or “bubble—up”. The whole, process is continued in this manner and the first pass ends with the comparison and possible exchange of the elements A[1] and -A[0].The first pass—will “bubble—up—the smallest among the two to A[0] The second pass continues exactly is the same process with the only exception that it ends with the comparison and possible exchanges of A[2] and A[1]. Thus, the second pass will “bubble— up” the second smallest element to A[1]. Each successive pass continues in the same process. Algorithm for Bubble sorting sorting pular aesia pubble e list and|then terchanged quence or deroR wr, 5 . Input n elements of an array a. ‘Initialize i=0. Repeat through step 6 while (iaft+1) @) temp =a [j] Gi) afi] = afj+1] ii) afj+1] =temp. Display the sorted elemens of xit.Qs. Explain the insertion sort by takinga suitable example: Ans. In this type of sorting technique, the new element is inserte such that the preceeding elements follow some order, in this the elements are considered one at.a time. In insertion sort, sorting is performed by inserting an record into the correct position in the sorted portion. . . Suppose an array of A with n elements A[1], A[2],.-------- Alp] ae in memory. The insertion sort scans A from A[1 ] to A[n] inserting each element A[k] into its proper position in the previously sorted sub arrary A[1], A[2], A[k—1j. Pass 1 - A[]] by itself is trivially sorted. Pass 2 - ie i inserted either before or after A[1 ] so that A[1],A[2] is sorted. / Pass 3 — A[3] is inserted into its proper place in A[1], A[2] thatis ». beore‘A[1], between A[1] and A[2] or after A[2] so that A[1], A[2], A[3] is sorted. . Pass 4 - A[4] is inserted into its proper place in—A[1], A[2], A[3] so that —A[1],A[2],A[3],A[4] is sorted. Pass N - A[n] is inserted into its proper place in A[1], A[2], A[n-1] so that — A[1], A[2], .. A[n] is stored. This sorting algorithm is frequently used when n is small. Algorithm for Insertion Sort Let a be an array of n elements which we want to sort, temp be a temporary variable to interchange the two values, k be the total number of passes anid j be another control variable. 1. Setk=1. 2. Fork=1to(n-1) Set temp = alk] Setj=k-1 , poe temp < ali] and (j >= 0) perform the following steps. et a [j+1] = alj] nd of loop structure] Assign the value of temp to afj+1]. [End of for-loop structure] 3. ExitComplexity of Insertion Sort ih In the straight insertion sort method, the number f(n) of the comparisons can be easily comp uted. First of all, the worst case occurs when the given array (vector) “A” is in reverse order and inner loop must use the maximum number (i-1) comparisons, which shows: fa) =1+24+38........ +(n = 1) = (1/2n (n—1)) =O(n’) ¢ On an average, we can depict that, there will be approximately (-1)/2 comparisons in the inner loop. Accordingly, for the average case: 1 f(a) = 1/2 +272 + 3/2 =VA(n-1) =O (n’) When “n’ is large the insertion sort algorithm is very slow. Disadvantages of Insertion Sort Insertion sort has one major disadvantage. Even after most items have been sorted properly into the first part of the list, the insertion of a later item may require that many of them moved. All the moves made by insertion sort are moves of only one position at a time. Thus to move an item 20 positions up the list requires 20 separate moves. If the items are small, perhaps a key alone or if the items are in linked storage, then the many moves may not require excessive time. But if the items are very large, structure containing hundreds of components like personnel files or student transcripts and the structures must be kept in contiguous storage, then it would be far more efficient. When it is necessary to move an item. it could be moved immediatly to it’s final position. Selection sort accomplished this goal. Average Case Tan (nt) = O(n") Worst Case 1/2 (n-1) = O(n) Method Insertion Sort