Sorting: Bubble, Selection, Insertion
What is sorting?
Sorting means arranging data in ascending or descending order – marks from highest to lowest, names alphabetically. Sorted data is much faster to search (binary search needs it).
Bubble sort
Compare adjacent elements and swap them if they are in the wrong order. After each pass the largest remaining element “bubbles” to its final place at the end.
def bubble_sort(a):
n = len(a)
for i in range(n - 1): # passes
swapped = False
for j in range(n - 1 - i): # last i items already in place
if a[j] > a[j + 1]:
a[j], a[j + 1] = a[j + 1], a[j]
swapped = True
print('Pass', i + 1, ':', a)
if not swapped: # already sorted -> stop early
break
nums = [8, 7, 13, 1, -9, 4]
bubble_sort(nums)Selection sort
Divide the list into a sorted left part and an unsorted right part. In each pass, select the smallest element of the unsorted part and swap it to the front of that part.
def selection_sort(a):
n = len(a)
for i in range(n - 1):
m = i # index of smallest so far
for j in range(i + 1, n):
if a[j] < a[m]:
m = j
a[i], a[m] = a[m], a[i] # put smallest at position i
print('Pass', i + 1, ':', a)
nums = [8, 7, 13, 1, -9, 4]
selection_sort(nums)Insertion sort
Like arranging playing cards in your hand: take the next element and insert it at the correct position in the already-sorted left part, shifting bigger items to the right.
def insertion_sort(a):
for i in range(1, len(a)):
key = a[i] # card to insert
j = i - 1
while j >= 0 and a[j] > key: # shift bigger items right
a[j + 1] = a[j]
j -= 1
a[j + 1] = key
print('Pass', i, ':', a)
nums = [8, 7, 13, 1, -9, 4]
insertion_sort(nums)Sorting strings / descending
def bubble_desc(names):
n = len(names)
for i in range(n - 1):
for j in range(n - 1 - i):
if names[j] < names[j + 1]: # > becomes < for descending
names[j], names[j + 1] = names[j + 1], names[j]
return names
print(bubble_desc(['Ravi', 'Asha', 'Neha', 'Kabir']))Time complexity
For n items, simple sorts compare about n×(n-1)/2 pairs, which grows like n². Doubling the data makes them about four times slower.
def count_bubble(a):
a = a[:]; comps = swaps = 0
for i in range(len(a) - 1):
for j in range(len(a) - 1 - i):
comps += 1
if a[j] > a[j + 1]:
a[j], a[j + 1] = a[j + 1], a[j]; swaps += 1
return comps, swaps
for data in [[1, 2, 3, 4, 5], [5, 4, 3, 2, 1], [3, 1, 4, 5, 2]]:
print(data, '-> comparisons, swaps =', count_bubble(data))Comparison
| Sort | Best | Average / Worst | Idea |
|---|---|---|---|
| Bubble | O(n) | O(n²) | Swap neighbours; largest bubbles to the end |
| Selection | O(n²) | O(n²) | Pick the smallest, put it in front |
| Insertion | O(n) | O(n²) | Insert each item into the sorted left part |
