?

Algorithms & Data Structures

Free Version

Upgrade subject to access all content

Moderate

Bubble Sort: Reducing Run-time

ALGOR-HNEADY

Alex and Ellie are discussing a new algorithm they learned today called bubble sort. Ellie claims that she found a very simple modification to the bubble sort algorithm that will speed it up slightly. She shows Alex the pseudocode for her algorithm below:

bubblesort(list A) : 
    begin_index = 1
    end_index = length(A)-1;
    while begin_index <= end_index : 
        new_begin_index = end_index
        new_end_index = begin_index
        for i = begin_index to end_index :
            if A[i] > A[i + 1]
                swap A[i] and A[i + 1]
            new_end_index=i
           end if
       end for
       // decrease end_index b/c the elements after new_end_index are sorted
       end_index = new_end_index - 1

        for i = end_index to begin_index  step -1:
            if A[i] > A[i + 1]
                swap A[i] and A[i + 1]
            new_begin_index=i
            end if
        end for
        // increase begin_index b/c the elements before new_begin_index are sorted
        begin_index = new_begin_index + 1
    end while

Will this return the correctly sorted array in fewer steps than the original bubble sort algorithm?

Select ALL that apply.

A

No; the run-time effectively doubles due to the presence of the two inner for loops in the while loop.

B

Yes; by updating begin_index and end_index in each iteration, the size of the bounds on the inner loops is reduced.

C

Yes; bubble sort can only move elements backward by one index in an iteration, whereas by alternating between forward and backward passes over the list, the modified version can move an element any number of steps in either direction.

D

Yes; under this modification, bubble sort becomes a divide-and-conquer algorithm. Its running-time is reduced from $\mathcal{O}(n^2)$ to $\mathcal{O(n \log n)}$.