Sorting algorithms: bubble sort

Sorting means arranging elements by some rule, for example in ascending or descending order. In ordered data a required element is found much faster, and lists are easier to read. There are many sorting methods; the simplest and clearest is bubble sort. In Python, an array is represented by a list (list).

The idea of bubble sort is this: compare two neighboring elements and swap them if they are in the wrong order. After one pass through the array from start to end, the largest element “floats” to the end, like a bubble in water. In the next pass the last element is no longer checked because it is already in place, so the checked part shrinks by one each time.

Let the array be 5 2 4 1. After pass 1 it becomes 2 4 1 5, after pass 2 it is 2 1 4 5, and after pass 3 it is 1 2 4 5. In Python, neighbors are compared with if a[j] > a[j + 1] and swapped with a[j], a[j + 1] = a[j + 1], a[j]; these actions repeat inside two nested for loops. If a pass makes no swaps at all, the array is already sorted and the process can stop.

Sorting n elements takes about n(n − 1)/2 comparisons, so the time grows in proportion to n². For 1000 elements that is about 500 thousand comparisons, and for 10,000 elements about 50 million. So bubble sort is good for learning but inefficient for big data. In practice, Python’s ready-made sorted() and list.sort() are used: they rely on a much faster algorithm (Timsort).

Key takeaways

• Sorting arranges elements in ascending or descending order.
• Bubble sort compares neighboring elements and swaps those that are in the wrong order.
• With each pass the largest remaining element moves to its place at the end.
• A pass with no swaps means the array is sorted, so the process can stop.
• About n(n − 1)/2 comparisons are needed, so the method is slow on large arrays.