( 2 + 2 + 1 + 6 + 20 ( + 3 + 7 ) marks ) One potential pitfall of quick - sort is that it does not necessarily perform well if there* are many...

ty........................................................

• Attachment 1
• Attachment 2
• Attachment 3

5 . ( 2 + 2 + 1 + 6 + 20 ( + 3 + 7 ) marks )One potential pitfall of quick - sort is that it does not necessarily perform well if there*are many repeated elements .( a ) Assume that you call quick - sort on an array of size ~. where all elements are thesame . Give an asymptotically tight bound on the run - time , presuming you alwaysuse the simple partition - algorithm . ( We repeat the pseudo - code below . )partition ( AP )A : array of size ~, p : integer s. t . 0 < p < ~.Create empty lists small and large .of A[P]for each element * in A [O , ... . p - 1] or Apt ] ... 2 - 1]if * < v append * to small*else append * to large*it size ( small )Overwrite A [O ... 1 - 1] by elements in small!Overwrite A[I] by UOverwrite A[it] ... ~ _ 1] by elements in largereturn ?`( b) Assume that you call quick- sort on an array of size ~. where all elements are thesame . Give an asymptotically tight bound on the run-time , presuming you use*Hoare's partition - algorithm from class ( listed below ) .partition ( AP )A : array of size n , p : integer s. t . 0 < p < ~1 .swap ( A [n - 1], A[P] )`2 .it - I, jan - 1, Ut A[n - ]]3 .loop4 .do it it I while i < ~ and Ali] < V5 .do j * j - 1 while j > O and A] > U6 .if i > ; then break ( goto 9 )else swap ( A [;] , A ] )100 -end loop9 .swap ( A [n2 - 1] , A [ 2] )10 .return i