tempmailon Stack Overflow • Recommends
On “Best Case for Bubble Sort”
There are multiple ways to write the bubble sort algorithm, it seems like over time the algorithm has gotten better, and more efficient. The first bubble sort algorithm I learned is below. The algorithm below Best and Worst Case is O(n^2).
BUBBLESORT(A)
1 for i = 1 to A.length - 1
2 for j = A.length downto i + 1
3 if Aj < Aj - 1
4 exchange Aj with Aj - 1
The algorithm that Wikipedia uses (below) seems to be an improvement using a flag to tell if the elements have been swapped or not, which allows the bubble sort algorithm best case to be O(n) instead of O(n^2)
procedure bubbleSort( A : list of sortable items )
n = length(A)
repeat
swapped = false
for i = 1 to n-1 inclusiv…