(a) Suppose that the Bubble Sort algorithm runs on the array (5, 4, 3, 2,1). Wha
ID: 3905047 • Letter: #
Question
(a) Suppose that the Bubble Sort algorithm runs on the array (5, 4, 3, 2,1). What will be the content of the array after the first iteration of the outer loop? After 4 marks 4. the second one? (b) Consider a general situation where the Bubble Sort algorithm runs on the array (n, n - 1,.. .,2, 1) for arbitrary n. Given i such that 1 i 3 n, what is the content of the array after i iterations of the outer loop of the Bubble Sort? (8 marks) (c) Show that the Insertion Sort algorithm takes O(n) time on any sorted array Hint: How much time does the inner loop take if the array is already sorted? (8 marks)Explanation / Answer
a) 5 4 3 2 1
4 3 2 1 5 (After the first iteration of th outer loop)
b) After the itertion of ith loop
[(n-i),(n-i-1),(n-i-2)....i,i+1...(n-i+1)]
c) In the case of insertion sort there are two parts one is sorted and another
is unsorted. Then element from the unsorted part moves in the sorted part
with suitable movements(order maintained in the sorted part). So we start
with the first element so that is any way sorted and then we choose an element
form the unsorted part (2..n). Noe if initially the whole array is sorted,
then no movement in the sorted part will be happening and we will be just
picking the elements in the unsorted part and again placing them at the same
place. This will happen for n elements so the complexity is O(n)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.