Question

- Please show all work and explain, I will thumbs up if done correctly -  

           Boolean isSorted;

for i = 1 to A:length -1

            isSorted = true;

            for j = A:length downto i + 1

                  if A[j] < A[ j - 1]

exchange A[j] with A[j -1]

isSorted = false;

                        if (isSorted) break;

1. What is the best case running time of the above algorithm?
2. What is the worst case running time of the above algorithm?
3. How can we modify the above algorithm to have a good best-case running time? (i.e. Terminate the algorithm as soon as the list is sorted.)

Answer 1

`Hey,

Note: Brother if you have any queries related the answer please do comment. I would be very happy to resolve all your queries.

The best case would be when the elements are already sorted. So, it would be O(n) since only second loop will work and then it will break

The worst case will be when the elements are reverse sorted. So, it will have O(n^2) since both loop will work in a nested way.

Please note the algorithm given in the question is already running in O(n) for best case which can't decreased further since we need atleast 1 loop to check if array is sorted.

Kindly revert for any queries

Thanks.