Algorithms Question

Answer question fully for thumbs up.

Question5 The two versions of the bubble sort algorithm are presented below. There are two nested loops in both versions. Notice that the ranges of j are different, while the instructions of the inner loop are the same (a) Show how algorithm bubbleSort1 operates by tracing it on the array, which consists of n 5 elements 5, 3,9,2,1. Tracing should be done by filling in the table (true or false) 00 A[0]>A1]? True (b) Determine the number of comparisons "AjAlj+1" performed by each algorit bubbleSortl and bubbleSort2, to sort an array of n numbers. (c) What is the time complexity of bubbleSort1 and bubbleSort2 in terms of big-O? Use the formal definition. (d) Algorithm bubbleSort2 performs less iterations in comparison with bubbleSort1. Explain which steps in bubbleSort1 are unnecessary and why ALGORITHM bubbleSort1 (A[0..n-1]) //Input: array AI0. .n-1 of n numbers //Output: array A sorted in ascending order for i 0 to n-1 for j 0 to n-2 temp A[j] A[j+1] temp ALGORITHM bubbleSort2 (A[0. .n-1]) //Input:array AIO. .n-1 of n numbers //Output: array A sorted in ascending order for i 0 to n-2 for j temp Aj] AL+1 temp Question5 The two versions of the bubble sort algorithm are presented below. There are two nested loops in both versions. Notice that the ranges of j are different, while the instructions of the inner loop are the same (a) Show how algorithm bubbleSort1 operates by tracing it on the array, which consists of n 5 elements 5, 3,9,2,1. Tracing should be done by filling in the table (true or false) 00 A[0]>A1]? True (b) Determine the number of comparisons "AjAlj+1" performed by each algorit bubbleSortl and bubbleSort2, to sort an array of n numbers. (c) What is the time complexity of bubbleSort1 and bubbleSort2 in terms of big-O? Use the formal definition. (d) Algorithm bubbleSort2 performs less iterations in comparison with bubbleSort1. Explain which steps in bubbleSort1 are unnecessary and why ALGORITHM bubbleSort1 (A[0..n-1]) //Input: array AI0. .n-1 of n numbers //Output: array A sorted in ascending order for i 0 to n-1 for j 0 to n-2 temp A[j] A[j+1] temp ALGORITHM bubbleSort2 (A[0. .n-1]) //Input:array AIO. .n-1 of n numbers //Output: array A sorted in ascending order for i 0 to n-2 for j temp Aj] AL+1 temp