Time Complexity of Elementary Sorts (Bubble vs. Selection)

Bubble, selection, and insertion sort all run in Theta(n^2) on a random array; what distinguishes them is whether their cost depends on the input — selection sort is always Theta(n^2), bubble and insertion can drop to Theta(n) on sorted data.