To sort 排序 is to put items in order. Bubble sort 冒泡排序 repeatedly swaps 交换 neighbours that are in the wrong order.
def bubble_sort(a):
a = a[:] # work on a copy
for i in range(len(a)):
for j in range(len(a) - 1 - i):
if a[j] > a[j + 1]:
a[j], a[j + 1] = a[j + 1], a[j]
return a
print(bubble_sort([5, 2, 4, 1])) # [1, 2, 4, 5]
Each pass 遍 carries the largest remaining item to the end. If a pass makes no swaps, the list is already sorted and the sort can stop early. Printing the list after each pass shows this, and it is how exam questions ask you to trace a sort:
def bubble_sort_trace(items):
n = len(items)
for p in range(n - 1):
swapped = False
for i in range(n - 1 - p): # the last p items are already in place
if items[i] > items[i + 1]:
items[i], items[i + 1] = items[i + 1], items[i]
swapped = True
print("after pass", p + 1, items)
if not swapped:
break
bubble_sort_trace([5, 1, 4, 2])
# after pass 1 [1, 4, 2, 5]
# after pass 2 [1, 2, 4, 5]
# after pass 3 [1, 2, 4, 5]
Insertion sort 插入排序 builds a sorted part one item at a time, sliding each new item back into its place:
def insertion_sort(a):
a = a[:] # work on a copy
for i in range(1, len(a)):
key = a[i]
j = i - 1
while j >= 0 and a[j] > key: # shift bigger values right
a[j + 1] = a[j]
j -= 1
a[j + 1] = key # drop key into the gap
return a
print(insertion_sort([5, 2, 4, 1])) # [1, 2, 4, 5]
- In real code, use Python's built-in
sorted():
print(sorted([5, 2, 4, 1])) # [1, 2, 4, 5]
Practice
Write each answer on paper first, then open the model answer, compare, and press Run.
1. Which search looks at fewer items? Find 23 in
[2, 5, 8, 12, 16, 23, 38, 56, 72, 91]. Write down the items a binary search looks at, and
count how many a linear search looks at.
Model answer
items = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target = 23
lo, hi = 0, len(items) - 1
looked = []
while lo <= hi:
mid = (lo + hi) // 2
looked.append(items[mid])
if items[mid] == target:
break
elif items[mid] < target:
lo = mid + 1
else:
hi = mid - 1
print("binary looks at", looked) # [16, 56, 23]
print("linear looks at", items.index(target) + 1, "items") # 6
Binary search: mid = 4 is 16, too small, so lo = 5; mid = 7 is 56, too big, so
hi = 6; mid = 5 is 23, found. Three items against six, and the gap grows with the size of
the list.
2. Biggest first. Change bubble sort so that it sorts [3, 8, 1, 6] from largest to
smallest.
Model answer
def bubble_sort_desc(a):
a = a[:]
n = len(a)
for p in range(n - 1):
for i in range(n - 1 - p):
if a[i] < a[i + 1]: # was >: now the smaller one moves right
a[i], a[i + 1] = a[i + 1], a[i]
return a
print(bubble_sort_desc([3, 8, 1, 6])) # [8, 6, 3, 1]
Only the comparison changes. With <, each pass carries the smallest value to the end.
3. Stop early. Bubble sort often finishes before its last pass. Add a flag so it stops
after a pass with no swaps, and print how many passes [1, 2, 4, 3] needs.
Model answer
def bubble_sort_early(a):
a = a[:]
passes = 0
swapped = True
while swapped:
swapped = False
passes = passes + 1
for i in range(len(a) - 1):
if a[i] > a[i + 1]:
a[i], a[i + 1] = a[i + 1], a[i]
swapped = True
return a, passes
print(bubble_sort_early([1, 2, 4, 3])) # ([1, 2, 3, 4], 2)
Pass 1 swaps 4 and 3; pass 2 makes no swap, which proves the list is sorted, so the loop ends.
A full bubble sort would make 3 passes. Exam questions often ask for this flag.