DSA Bubble and Selection Sort
A sorting method is a fixed recipe for putting values in order. Bubble sort and selection sort are two early recipes worth learning.
One bubble pass
Bubble sort compares neighbouring values and swaps them when they are out of order. A swap exchanges two values, and one pass carries the largest value to the end.
values = [5, 2, 9, 1]
swaps = 0
for i in range(len(values) - 1):
if values[i] > values[i + 1]:
values[i], values[i + 1] = values[i + 1], values[i]
swaps += 1
print(values)
print("swaps:", swaps)One selection scan
Selection sort scans the part not yet placed for its smallest value. One scan finds the value that belongs at the front.
values = [5, 2, 9, 1]
smallest = 0
checks = 0
for i in range(1, len(values)):
checks += 1
if values[i] < values[smallest]:
smallest = i
print("smallest index:", smallest)
print("smallest value:", values[smallest])
print("checks:", checks)Bubble sort in full
A pass is one full sweep across the whole list. Each later pass can stop one step earlier, because the end is already placed.
def bubble(values):
data = values[:]
passes = 0
for end in range(len(data) - 1, 0, -1):
passes += 1
for i in range(end):
if data[i] > data[i + 1]:
data[i], data[i + 1] = data[i + 1], data[i]
return data, passes
print(bubble([4, 3, 2, 1]))Example
def bubble_sort(values):
data = values[:]
comparisons = 0
swaps = 0
for end in range(len(data) - 1, 0, -1):
for i in range(end):
comparisons += 1
if data[i] > data[i + 1]:
data[i], data[i + 1] = data[i + 1], data[i]
swaps += 1
return data, comparisons, swaps
def selection_sort(values):
data = values[:]
comparisons = 0
swaps = 0
for start in range(len(data) - 1):
smallest = start
for i in range(start + 1, len(data)):
comparisons += 1
if data[i] < data[smallest]:
smallest = i
if smallest != start:
data[start], data[smallest] = data[smallest], data[start]
swaps += 1
return data, comparisons, swaps
start = [5, 4, 3, 2, 1]
print("start:", start)
result, comparisons, swaps = bubble_sort(start)
print("bubble:", result, "comparisons:", comparisons, "swaps:", swaps)
result, comparisons, swaps = selection_sort(start)
print("selection:", result, "comparisons:", comparisons, "swaps:", swaps)Key points
- Simple sorts build the full order one pass at a time.
- Bubble sort can swap on almost every comparison it makes.
- Selection sort compares just as often but swaps far less.
In this example, both sorts run on the same reversed list of five values. A comparison is one check of which of two values is smaller. Bubble sort compares ten times and swaps on every single comparison. Selection sort also compares ten times, because it scans every remaining value each pass. Selection sort swaps only twice, when each smallest value moves to the front.
Try it Yourself
Edit the code, then press Run.
Running is simulated · Python Playground
Exercise
Selection sort runs on a list of five values, scanning every remaining value on each pass. How many comparisons does it make in total?