跳到主要内容

考前速记


Bubble Sort vs Insertion Sort — Side by Side​

Bubble SortInsertion Sort
Nested loops (both for)Outer for, inner while
Compare adjacent, swapShift right, insert key
Largest element bubbles to endSorted portion grows from left
Inner loop bound shrinks: n-1-iInner loop bound grows: j ≥ 0

Quick Templates​

Bubble Sort​

def bubbleSort(arr):
n = len(arr)
for i in range(n - 1):
for j in range(n - 1 - i):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr

Insertion Sort (Iterative)​

def insertionSort(arr):
n = len(arr)
for i in range(1, n):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr

Insertion Sort (Recursive)​

def insertionSortRec(arr, n):
if n <= 1:
return
insertionSortRec(arr, n - 1)
key = arr[n - 1]
j = n - 2
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key

Big O​

AlgorithmBestAverageWorstSpace
Bubble Sort(O(n))(O(n^2))(O(n^2))(O(1))
Insertion Sort(O(n))(O(n^2))(O(n^2))(O(1))

When to Use Which​

SituationRecommendation
Exam asks for bubble sort by nameUse bubble sort
Exam asks for insertion sort by nameUse insertion sort
Nearly-sorted dataInsertion sort (fast best case)
Need simple code for small arrayEither — bubble sort is simpler
Question asks for recursionInsertion sort recursive
Question asks iterative → recursive conversionConvert insertion sort (commonest)
Linked list sortingInsertion sort preferred

考前 Checklist​

  • Can I write bubble sort from memory? (nested loops, adjacent comparison, swap)
  • Can I write iterative insertion sort from memory? (i from 1, key, shift while loop, insert)
  • Can I write recursive insertion sort from memory? (base case, recursive call, insert last)
  • Do I know Big O for both? ((O(n^2)) worst, (O(n)) best)
  • Can I convert between iterative and recursive?
  • Do I know the difference between procedure (no return) and function (must return)?