Bubble Sort

#Sorting#Computer-Science#CS251 Bubbles the largest values to the right (top) of the array

Pseudocode §

BubbleSort(A:array of size n)
	repeat <- true
	while (repeat)
		repeat <- false
		for (i = 0, i < n-1, 1)
			if (A[i] > A[i+1])
				swap(A, i, i+1)
				repeat <- true
			endif
		endfor
	endwhile
	return A
end BubbleSort

Details §

• Is stable
• Is in place, has a space complexity $\in \Theta (n)$
• Time Complexity
  • If the array is sorted
    • # Compares = $T(n)=n-1\in \Theta (n)$
    • # Swaps = $T(n)=0\in \Theta (1)$
  • If the array is sorted in opposite order?
    • # Compares = $T(n)=n^2-n\in \Theta (n^2)$
    • # Swaps = $T(n)=\frac{1}{2}{n}^2-\frac{1}{2}n\in \Theta (n^2)$

Best Case $\in \Theta (n)$ §

Worst Case $\in \Theta (n^2)$ §