Sort an array of numbers in increasing order. Bubble sort only ever compares and swaps two neighbours.
DSA Animator › DSA Revision › Sorting Algorithms › Bubble Sort
Remember: each pass bubbles the largest remaining value to the end. The swapped flag makes the best case linear. The video solves Bubble Sort (LeetCode 912, Easy) with the Adjacent Swaps pattern from the Sorting Algorithms topic, and you can replay every step in the interactive Bubble Sort animation.
Sort an array of numbers in increasing order. Bubble sort only ever compares and swaps two neighbours.
For 5, 2, 8, 1, 9, 3, the sorted result is 1, 2, 3, 5, 8, 9.
Bubble sort is the simplest sort to understand. It is too slow for big inputs, but it teaches how swaps move elements.
Walk from left to right, comparing each pair of neighbours. If the left one is bigger, swap them. After one pass, the largest value has bubbled to the end, where it stays. Repeat on the shorter unsorted part. If a pass makes no swap at all, the array is already sorted, so stop early.
Pass 1 compares 5 and 2 and swaps them, then keeps carrying the bigger value right. 9 bubbles all the way to the end, giving 2, 5, 1, 8, 3, 9. Pass 2 moves 8 to its place, giving 2, 1, 5, 3, 8, 9. Pass 3 swaps 2 and 1, and 5 and 3, and the array is 1, 2, 3, 5, 8, 9. Pass 4 makes no swap, so we stop early. The array is sorted.
In code, the outer loop counts passes. The inner loop compares a of j with a of j plus 1, up to the end of the unsorted part. Swap when they are out of order, and remember that a swap happened. Break when a pass makes no swap. It's O of n squared in general, but O of n on sorted input.
Remember: each pass bubbles the largest remaining value to the end. The swapped flag makes the best case linear.