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.