Interview Prep - Bubble Sort

Time and Space Complexity

Remember merge sort? We tried to do it in real life but we ran out of space in the classroom.

Merge sort is a fast algorithm; it has low time complexity. We ran out of space because although merge sort is very efficient in terms of time, it isn't very efficient in terms of space.

Today we'll look at bubble sort, a simple algorithm that has high time complexity.

Bubble sort also has low space complexity; it will use less memory than merge sort for a given input.

One Step at a Time

Bubble sort works by comparing every element to its neighbor. Large numbers quickly "bubble up" to the top of the array. After enough iterations, all elements are sorted. Take a look at this video for a more thorough explanation: youtube.com/watch?v=8Kp-8OGwphY

Algorithm Design (Cont.)

Time and space complexity go hand in hand. As one increases, the other must decrease. Keep these rules in mind when thinking about algorithms and code in general.

Revisiting Big-O

Big-O is the mathematical representation of an algorithm's complexity.