Question

A. What is the time complexity of Insertion Sort? B. Explain why Insertion Sort has the time complexity you listed above in Part A. C. Show the steps followed by the Quicksort algorithm given below in pseudocode when sorting the following array. Algorithm Quicksort (A, left, right) if (left < right) pivot Point + [(left+right)/2] // note central pivot it left - 1 j right + 1 do do iti + 1 while (i < A.size) and (A[i] = A[pivotPoint]) do jj-1 while (j > i) and (A[il > A[pivot Point]) if (i <j) then swap (A[i], A[j]) while (i <3) if (i < pivot Point) then j ti swap (A[pivot Point), A[j]) Quicksort (A, left, j-1) Quicksort (A, j+1, right) endif Sort the following Array. Draw one figure for each call to Quicksort. You may omit calls where left right. value 76 24 49 68 40 30 89 88 11 59 index 0 - 2 3 4 5 6 8 9 D. Suppose you have the following hash table, implemented using linear probing. The hash function we are using is the identity function, h(x) = x 0 1 2 3 4 9 18 12 3 14 4 21 7 8 In which order could the elements have been added to the hash table? Assume that the hash table has never been resized, and no elements have been deleted yet.

Answer 1

solution : A Insertion Sort time complexity = 0 (02). B Insertion Soot Algorithm n-size array A { O1 2 3 Insertion Sort (An) for iti to n-1 { value f Alij n-T je while (jso ff A[j-1] > value) A] A- { 3 A[j] = value } in worst case T(p) : 1+2+3+ (n-1) n(n-1) T(m) = n²n So that Tin) = 0 (0²) Aus D Ch Cac) +i)% Table-size. Order :- 9,18, 12,3,14, 4, 21 Linear Poobing :- W(x Table size = 9 hi 9)=9°/09 = 0 h(18) - 18/9 = 0 (collision) h(12) = 12449 = 3 h(3) = 3%9-3 (collision) h (14) - 14049 - 5 h(4) = 4%9= 4 c collision) h(21) - 91%9-3 (collision) (0+1)% = 1 (3+1)%9 4 (4+2)64-9 = 6 (3+4 % 97-

PAGE NO DATE: 1 207 Vivo Alcamera Shot on Y12 le ole 24 Applye Griven Quick Sort pivot Point Algorithm 0 +9 761241 49 681(40)| 30 89 88 11 59 Pluct point = Z 2 3 4. 7. 8 9 1 f left night t 1112230 681 49 89 88476|59| 44-6. 0+2=1 5 6 8 9 pivot Point - 0 +2 O 2 4 7 . null list 301 (68 49 (59 88 76 4+8=6 0 2 6 149 168(8876 6 7 6+8 2 = 7 8 y con 68 76 7 empty 76 4124130 40 49 59 687688 Sosted Array,