Question 5 Soalan 51 (a) Consider the following list of number. (Pertimbangkan senarai nombor berikut. [15,5,4,18,12,19,14,10,8,20] (C5,CO3,PO2) (i) Construct the trace of insertion sort to rearrange the numbers into ascending order. (Bina jejak isihan penyisipan untuk menyusun nombor-nombor berkenaan ke dalam bentuk susunan menaik. (6 Marks/Markah) (C2,CO3,P01) (ii) Explain why insertion sort is a stable sort. (Jelaskan kenapa isihan penyisipan ialah isihan yang stabil.] (2 Marks/Markah) (C4,CO3,PO2) (iii) Analyse the best and average time complexity for insertion sort. (Analisa kompleksiti terbaik dan masa purata kompleksiti untuk isihan penyisipan.) (2 Marks/Markah) (b) Consider the following list of number. (Pertimbangkan senarai nombor berikut. L = [3,5,6,8,11,12,14,15,17,18] (C5,CO3,PO2) (i) Construct the trace of interpolation search to find the set of keys (14,20). (Bina jejak carian interpolasi untuk mencari satu ser kunci {14,20).] (6 Marks/Markah) (C2,CO3,PO1) (ii) Compare the interpolation search with the binary search. (Bandingkan carian interpolasi dengan carian penduaan. (2 Marks/Markah) (C4,CO3,PO2) (iii) Analyse the best and average time complexity for interpolation search. ( Analisa kompleksiti terbaik dan masa purata kompleksiti untuk carian interpolasi.) (2 Marks/Markah)