Question 9: Consider the following array: #(47 27 68 52 18 53) a. b. Sort the array in increasing order by using Insertion sort. In your answer, trace the algorithm by showing the new array after each swapping between elements. Explain and express the worst-case time complexity of the Insertion sort in terms of the size of the input. At last, show this time complexity with big O notation.
(Q9) This is a Data Structures problem and the
Insertion Sort is used to sort an array of n elements. It works by repeatedly taking one element at a time and placing it in its correct position among the previously sorted elements. In the worst case, where the array is in reverse order, it will require n^2 comparisons and swaps, leading to a time complexity of O(n^2). For the given array #(47 27 68 52 18 53), the sorting process proceeds step by step, comparing and swapping elements, ultimately resulting in the sorted array #(18 27 47 52 53 68). This simple sorting algorithm is efficient for small datasets but becomes impractical for larger datasets due to its quadratic time complexity.
Step by step
Solved in 4 steps
