Sorting is one of the most common operations in computing. Search engines rank results, databases order records, and applications display names alphabetically — all of these rely on sorting. Understanding how sorting algorithms work helps you appreciate why some approaches are faster than others.
Why Sorting Matters
Once a list is sorted, many other operations become much more efficient. Searching a sorted list, for example, can use binary search instead of checking every element. Merging two sorted lists is also far quicker than merging two unsorted ones. Sorting is often a crucial first step in solving bigger problems.
Bubble Sort
Bubble sort is one of the simplest algorithms to understand. It repeatedly steps through the list, compares pairs of adjacent elements, and swaps them if they are in the wrong order. Larger values gradually "bubble up" to the end.
Example with the list [5, 3, 8, 1]:
- Pass 1: Compare 5 and 3 — swap. Compare 5 and 8 — no swap. Compare 8 and 1 — swap. List: [3, 5, 1, 8]
- Pass 2: Compare 3 and 5 — no swap. Compare 5 and 1 — swap. List: [3, 1, 5, 8]
- Pass 3: Compare 3 and 1 — swap. List: [1, 3, 5, 8]
- Sorted!
def bubble_sort(lst):
n = len(lst)
for i in range(n):
for j in range(0, n - i - 1):
if lst[j] > lst[j + 1]:
lst[j], lst[j + 1] = lst[j + 1], lst[j]
return lst
Bubble sort has a time complexity of O(n squared) in the worst case, meaning it becomes very slow on large lists. It is useful for teaching but rarely used in real applications.
Selection Sort
Selection sort works differently. It divides the list into a sorted part (initially empty) and an unsorted part. On each pass it finds the smallest element in the unsorted part and moves it to the end of the sorted part.
Example with the list [5, 3, 8, 1]:
- Pass 1: Smallest in [5,3,8,1] is 1. Swap with first element. List: [1, 3, 8, 5]
- Pass 2: Smallest in [3,8,5] is 3. Already in place. List: [1, 3, 8, 5]
- Pass 3: Smallest in [8,5] is 5. Swap with 8. List: [1, 3, 5, 8]
- Sorted!
def selection_sort(lst):
n = len(lst)
for i in range(n):
min_index = i
for j in range(i + 1, n):
if lst[j] < lst[min_index]:
min_index = j
lst[i], lst[min_index] = lst[min_index], lst[i]
return lst
Selection sort also has O(n squared) complexity, but it makes fewer swaps than bubble sort. This can be an advantage when swapping is expensive, such as when writing to slow storage.
Comparing the Two
| Feature | Bubble Sort | Selection Sort |
|---|---|---|
| Number of comparisons | O(n squared) | O(n squared) |
| Number of swaps | Up to O(n squared) | At most O(n) |
| Stable sort? | Yes | No |
| Ease of understanding | Very easy | Easy |
A stable sort preserves the original order of elements that are equal — important when sorting records by one field while maintaining order from a previous sort.
Neither bubble sort nor selection sort is suitable for large datasets in professional software. Real applications use more efficient algorithms such as merge sort or quicksort, which have O(n log n) average-case complexity.
Practice Problems
Trace through one full pass of bubble sort on the list [4, 2, 7, 1]. What does the list look like after that pass?
Show answer
How many passes does selection sort need to fully sort a list of 5 elements?