Q153: Tweaking the Bubble Sort II

Question #153: In the inner loop of bubble sort algorithm [refer Q55], let’s say we add a check to break the outer loop if there were no interchanges in the full run of the inner loop. Will the worst case of bubble sort improve?

Options:

1. There will be improvement in running time but not asymptotically.
2. Yes, from O(n²) to O(n log(n))
3. Yes, from O(n log(n)) to O(n)
4. Yes, from O(n²) to O(n)

Solution: The correct option is the first one. The worst case is when all of the elements are in the descending order and we need to sort them in ascending order. In this case, even for the last run of the outer loop, there will be one exchange, so it won’t benefit from the added check optimization.

You may also want to checkout Q56.

Q101: Time complexity of bubble sort

Question #101: What is the worst case time complexity of bubble sort algorithm?

Options:

1. O(n)
2. O(n²)
3. O(n log(n))
4. O(n² log(n))

Solution: The correct answer is 2nd one. The recursive equation is:

T(n) = T(n-1) + n

As in each iteration of bubble sort, 1 element is ‘bubbled’ to it’s correct position, and the task reduces to sorting out n-1 elements.

Q56: Tweaking the Bubble Sort

Question #56: In the inner loop of bubble sort algorithm [refer Q55], let’s say we add a check to break the outer loop if there were no interchanges in the full run of the inner loop. Will the best case of bubble sort improve?

Options:

1. There will be improvement in running time but not asymptotically.
2. Yes, from O(n²) to O(n log(n))
3. Yes, from O(n log(n)) to O(n)
4. Yes, from O(n²) to O(n)

Solution: The best case is when all of the elements are already sorted. In this case, at the end of inner loop for the first time, there will be no exchanges. Hence, the outer loop will terminate in just O(n). So, correct answer is 4th one.

Q55: Bubble Sort

The bubble sort works by iterating down an array to be sorted from the first element to the last, comparing each pair of elements and switching their positions if necessary. This process is repeated as many times as necessary, until the array is sorted.

Following is the basic code for bubble sort:

for(int x=0; x<n; x++)
{
    for(int y=0; y<n-1; y++)
    {
        if(array[y]>array[y+1])
        {

            int temp = array[y+1];
            array[y+1] = array[y];
            array[y] = temp;
       }
    }
}

Question #55: Let’s say we have the elements in the array as “2, 3, 1, 5, 4”. What will be the array as soon as ‘x’ in the above algorithm becomes 1?

Options:

1. 2, 1, 3, 4, 5
2. 1, 2, 3, 4, 5
3. 2, 1, 3, 5, 4
4. 2, 3, 1, 5, 4

Solution: The correct option is the first one. Steps will be:

2, 3 => 2, 3

3, 1 => 1, 3

3, 5 => 3, 5

5, 4 => 4, 5