Question

Use the algorithms SELECT, PARTITION, and CHOOSEPIVOTELEMENT to find the 6th smallest element of A = [12, 92, 64, 68, 54, 37, 57, 95, 56, 91, 32, 1, 30, 14, 35, 49, 66, 59, 76, 58). Show the results of each step of SELECT, PARTITION, and CHOOSEPIVOTELEMENT. You do not need to show the results of the recursive calls to SELECT to find the median of medians; for those calls, just show what the call would be and what the result would be.

Answer 1

I have completed this problem Please give thumbs up if you like it

Step 1

Algorithm

Step 2 Using Algorithm above shows all passes

Algorithm - Selection procedure Find kth smallest Element Selection Procedure CA, B qik) if C P == q) return Calp]); else m= Partition CA,P, q) if (mile=k) return cack]) else ifckcm) Selection Procedure CA, P, M-1,k) else Selection Procedure (Amtl, q, k) Ist last Partition CA, i, j) ♡ X = ADJ; P = 1; for (q=itti asjjq++) d if(x >=a[qa) d p=bhi Sw abcarp), acq]) A swab Cacid; 00P]); return p}

Given Array A = [12, 92, 64,68,54, 37, 57,95, 59, 91, 32, L, 30,14, 35, 49,66,59, 76, 58 5 6 7 8 9 10 11 12 13 19 3 17 18 2 14 IS 16 니 Abably selection procedur K= 6,12 is Pivot 91 3 17 18 19 4 2 5 lo ㅋ U/ ) A=[t (12) 92 64 68 54 37 57 95 59 32 30 14 35 49 66 59 76 58 6 8 9 12 13 14 IS 16 m=1, mtl & k', so, Apply selection Procedure right side , 92=Pivot & A=[112 6.4 68 54 37 57 58 91 32 66 si 76 58(92) 95 30 14 35 49 T8 19 3 u S 6 m=18, mtl tk, so again apply SP bw 2 and 17 64 = Pivot 16 17 7 14 IS 10 8 [2 13 10 9 2 A =[+ 12 54 37 57 59 32 30 14 35 49 69 58 (64) 68 91.66 76 92 95 8 9 19 7 10 12 14 IS 16 17 18 6 I 3 4. S m=13, MH #6, So , again apbly SP 6/W 6/W 82 and 12, 54=Pivot

4 A=[+ 12 37 32 30 14 35 49 (54) 57 56 59 58 64 68 91 66 76 92 95] 2 3 4 5 6 7 8 10 9 12 13 14 IS 16 17 18 19 m=8mti tk, so, Abbly Sp where pivot =37 A=[ 12 32 30 14 35 13749 54 57 66 59 58 64 68 91 66 76 92 95 2 3 4 S 8 q IS 18 19 m=6, mt 1 tk, so, Apply sp where Pivot = 32 6 7 10 11 12 13 14 16 17 2 3 4 S G 6 A=[ 12 30 14 32 35 37 49 S4 57 66 59 58 64 68 91 66 76 92 95 6 7. 8 q 10 11 12 13 14 is 16 17 18 la m=4 mt! #k, so, 7th timp Abbly selection Procedure m=5 S mtl=k satisfied Hence 35 element is 6th smallest element. will given -