Here is code of bubble sort. It's run time complexity is O(na). Change the code in a way so that its time complexity is O(n) for the best case scenario. Find the best case and change the code a little bit. And explain how you did it in a comment block of your code. def bubbleSort(arr): for i in range(len(arr)-1): for j in range(len(arr)-i-1): if arr[j] > arr[j+1]: swap( arr[j+1], arr[j] ) The first line of the input will contain N, which is the size of the array. Next line will contain the N number of elements. Output will contain the sorted elements. P.S: sample input and output may not be the preferred answer choice. Input 1: 5 32145 Input 2: 6 10 20 5 15 25 30 Output 1: 1 2 3 4 5 Output 2: 5 10 15 20 25 30