Summary

Bubble Sort is an introductory algorithm that works by repeatedly stepping through the list, comparing adjacent elements and swapping them if they are in the wrong order. The pass through the list is repeated until the list is sorted. The algorithm gets its name because smaller elements "bubble" to the top of the list (beginning) while larger elements "sink" to the bottom (end) during each iteration.

How it Works

• Start with the first element at index $i=0$.

• Compare the current element with the next element ($i$ and $i+1$).

• If the current element is greater than the next element, swap them.

• Move to the next pair and repeat until the end of the list. After the first pass, the largest element is guaranteed to be in its correct final position.

• Repeat the process for the remaining unsorted elements ($N-1$, $N-2$, etc.).

• Optimization: If a pass completes with zero swaps, the array is already sorted, and the algorithm terminates early.