Sorting Algorithms

Prerequisites: Lists, loops, functions

---

1. Bubble Sort

Concept, Compare adjacent elements and swap them if they are in the wrong order., After each pass, the largest unsorted element "bubbles up" to its correct position at the end., Repeat until no swaps are needed.

Algorithm

For i = 0 to n-2:
 For j = 0 to n-2-i:
 If arr[j] > arr[j+1]:
 Swap arr[j] and arr[j+1]

Code

def bubble_sort(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

Dry Run Trace

Input: [64, 34, 25, 12, 22]

Pass 1 (i=0):
 Compare 64, 34 -> Swap -> [34, 64, 25, 12, 22]
 Compare 64, 25 -> Swap -> [34, 25, 64, 12, 22]
 Compare 64, 12 -> Swap -> [34, 25, 12, 64, 22]
 Compare 64, 22 -> Swap -> [34, 25, 12, 22, 64] <- 64 in place

Pass 2 (i=1):
 Compare 34, 25 -> Swap -> [25, 34, 12, 22, 64]
 Compare 34, 12 -> Swap -> [25, 12, 34, 22, 64]
 Compare 34, 22 -> Swap -> [25, 12, 22, 34, 64] <- 34 in place

Pass 3 (i=2):
 Compare 25, 12 -> Swap -> [12, 25, 22, 34, 64]
 Compare 25, 22 -> Swap -> [12, 22, 25, 34, 64] <- 25 in place

Pass 4 (i=3):
 Compare 12, 22 -> No swap -> [12, 22, 25, 34, 64] <- 22 in place

Sorted: [12, 22, 25, 34, 64]

Complexity

• Time: O(n^2) in all cases (worst, average, best without optimization)
• Space: O(1), in-place sorting
• Stable: Yes (equal elements maintain their relative order)

---

2. Optimized Bubble Sort

Concept

If no swaps occur during a pass, the array is already sorted, stop early.

Code

def bubble_sort_optimized(arr):
 n = len(arr)
 for i in range(n - 1):
 swapped = False
 for j in range(n - 1 - i):
 if arr[j] > arr[j + 1]:
 arr[j], arr[j + 1] = arr[j + 1], arr[j]
 swapped = True
 if not swapped:
 break # Array is sorted, no need to continue
 return arr

Benefit

• Best case (already sorted): O(n), only one pass with no swaps., Worst and average case remain O(n^2).

Trace for Already Sorted Input

Input: [10, 20, 30, 40, 50]

Pass 1 (i=0):
 Compare 10, 20 -> No swap
 Compare 20, 30 -> No swap
 Compare 30, 40 -> No swap
 Compare 40, 50 -> No swap
 swapped = False -> BREAK!

Only 1 pass needed. Best case: O(n).

---

3. Selection Sort

Concept, Find the minimum element in the unsorted portion., Swap it with the first element of the unsorted portion., The sorted portion grows by one element after each pass.

Algorithm

For i = 0 to n-2:
 Find index of minimum element from i to n-1
 Swap arr[i] with arr[min_index]

Code

def selection_sort(arr):
 n = len(arr)
 for i in range(n - 1):
 min_idx = i
 for j in range(i + 1, n):
 if arr[j] < arr[min_idx]:
 min_idx = j
 if min_idx != i:
 arr[i], arr[min_idx] = arr[min_idx], arr[i]
 return arr

Dry Run Trace

Input: [64, 25, 12, 22, 11]

Pass 1 (i=0):
 Find min in [64, 25, 12, 22, 11] -> min=11 at index 4
 Swap arr[0] and arr[4]: [11, 25, 12, 22, 64]

Pass 2 (i=1):
 Find min in [25, 12, 22, 64] -> min=12 at index 2
 Swap arr[1] and arr[2]: [11, 12, 25, 22, 64]

Pass 3 (i=2):
 Find min in [25, 22, 64] -> min=22 at index 3
 Swap arr[2] and arr[3]: [11, 12, 22, 25, 64]

Pass 4 (i=3):
 Find min in [25, 64] -> min=25 at index 3
 No swap needed: [11, 12, 22, 25, 64]

Sorted: [11, 12, 22, 25, 64]

Complexity

• Time: O(n^2) in all cases (always scans for minimum)
• Space: O(1), in-place sorting
• Stable: No (can change relative order of equal elements)
• Swaps: At most n-1 swaps (fewer swaps than bubble sort)

---

4. Insertion Sort

Concept, Build the sorted array one element at a time., Take the next element and insert it in its correct position in the already-sorted portion., Like sorting playing cards in your hand.

Algorithm

For i = 1 to n-1:
 key = arr[i]
 j = i - 1
 While j >= 0 and arr[j] > key:
 arr[j+1] = arr[j] (shift right)
 j = j - 1
 arr[j+1] = key (insert)

Code

def insertion_sort(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

Dry Run Trace

Input: [64, 34, 25, 12, 22]

Initial: [64, 34, 25, 12, 22]

Pass 1 (i=1, key=34):
 Compare 64 > 34 -> Shift 64 right -> [64, 64, 25, 12, 22]
 Insert 34 at position 0 -> [34, 64, 25, 12, 22]

Pass 2 (i=2, key=25):
 Compare 64 > 25 -> Shift 64 right -> [34, 64, 64, 12, 22]
 Compare 34 > 25 -> Shift 34 right -> [34, 34, 64, 12, 22]
 Insert 25 at position 0 -> [25, 34, 64, 12, 22]

Pass 3 (i=3, key=12):
 Compare 64 > 12 -> Shift 64 right -> [25, 34, 64, 64, 22]
 Compare 34 > 12 -> Shift 34 right -> [25, 34, 34, 64, 22]
 Compare 25 > 12 -> Shift 25 right -> [25, 25, 34, 64, 22]
 Insert 12 at position 0 -> [12, 25, 34, 64, 22]

Pass 4 (i=4, key=22):
 Compare 64 > 22 -> Shift 64 right -> [12, 25, 34, 64, 64]
 Compare 34 > 22 -> Shift 34 right -> [12, 25, 34, 34, 64]
 Compare 25 > 22 -> Shift 25 right -> [12, 25, 25, 34, 64]
 12 <= 22 -> STOP
 Insert 22 at position 1 -> [12, 22, 25, 34, 64]

Sorted: [12, 22, 25, 34, 64]

Complexity

• Best case (already sorted): O(n), each element compared once
• Worst case (reverse sorted): O(n^2)
• Average case: O(n^2)
• Space: O(1), in-place sorting
• Stable: Yes, Best for nearly sorted data or small datasets

---

5. Comparison of Sorting Algorithms

Feature	Bubble Sort	Selection Sort	Insertion Sort
Best case	O(n) (optimized)	O(n^2)	O(n)
Worst case	O(n^2)	O(n^2)	O(n^2)
Average case	O(n^2)	O(n^2)	O(n^2)
Space	O(1)	O(1)	O(1)
Stable	Yes	No	Yes
Swaps	Many	At most n-1	Many (shifts)
Best for	Detecting sorted data	Minimizing swaps	Nearly sorted data
Method	Adjacent comparison	Find minimum	Insert in position

---

6. Python's Built-in Sorting

sort, In-place

arr = [64, 34, 25, 12, 22]
arr.sort
print(arr) # [12, 22, 25, 34, 64]

arr.sort(reverse=True)
print(arr) # [64, 34, 25, 22, 12]

sorted, Returns New List

arr = [64, 34, 25, 12, 22]
new_arr = sorted(arr)
print(new_arr) # [12, 22, 25, 34, 64]
print(arr) # [64, 34, 25, 12, 22] (original unchanged)

desc_arr = sorted(arr, reverse=True)
print(desc_arr) # [64, 34, 25, 22, 12]

TimSort

Python's built-in sort uses TimSort - a hybrid of merge sort and insertion sort., Time complexity: O(n log n) average and worst case, Much faster than bubble, selection, or insertion sort for large data

---

Practice Programs

Program 1: Bubble Sort Implementation

def bubble_sort(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]
 print(f"After pass {i+1}: {arr}")
 return arr

# Test
data = [64, 34, 25, 12, 22]
print("Original:", data)
result = bubble_sort(data)
print("Sorted: ", result)

# Output:
# Original: [64, 34, 25, 12, 22]
# After pass 1: [34, 25, 12, 22, 64]
# After pass 2: [25, 12, 22, 34, 64]
# After pass 3: [12, 22, 25, 34, 64]
# After pass 4: [12, 22, 25, 34, 64]
# Sorted: [12, 22, 25, 34, 64]

Program 2: Optimized Bubble Sort (Stop If No Swaps)

def bubble_sort_optimized(arr):
 n = len(arr)
 total_passes = 0

 for i in range(n - 1):
 swapped = False
 for j in range(n - 1 - i):
 if arr[j] > arr[j + 1]:
 arr[j], arr[j + 1] = arr[j + 1], arr[j]
 swapped = True
 total_passes += 1
 print(f"Pass {total_passes}: {arr} (Swapped: {swapped})")
 if not swapped:
 print("No swaps - array is sorted. Stopping early!")
 break

 print(f"Total passes: {total_passes}")
 return arr

# Test 1: Unsorted data
print("Test 1: Unsorted")
data1 = [5, 1, 4, 2, 8]
bubble_sort_optimized(data1)

# Output:
# Test 1: Unsorted
# Pass 1: [1, 4, 2, 5, 8] (Swapped: True)
# Pass 2: [1, 2, 4, 5, 8] (Swapped: True)
# Pass 3: [1, 2, 4, 5, 8] (Swapped: False)
# No swaps - array is sorted. Stopping early!
# Total passes: 3

# Test 2: Already sorted data
print("\nTest 2: Already sorted")
data2 = [1, 2, 3, 4, 5]
bubble_sort_optimized(data2)

# Output:
# Test 2: Already sorted
# Pass 1: [1, 2, 3, 4, 5] (Swapped: False)
# No swaps - array is sorted. Stopping early!
# Total passes: 1

Program 3: Selection Sort Implementation

def selection_sort(arr):
 n = len(arr)
 for i in range(n - 1):
 min_idx = i
 for j in range(i + 1, n):
 if arr[j] < arr[min_idx]:
 min_idx = j

 if min_idx != i:
 arr[i], arr[min_idx] = arr[min_idx], arr[i]
 print(f"Pass {i+1}: Swapped {arr[min_idx]} and {arr[i]} -> {arr}")
 else:
 print(f"Pass {i+1}: No swap needed -> {arr}")

 return arr

# Test
data = [64, 25, 12, 22, 11]
print("Original:", data)
result = selection_sort(data)
print("Sorted: ", result)

# Output:
# Original: [64, 25, 12, 22, 11]
# Pass 1: Swapped 64 and 11 -> [11, 25, 12, 22, 64]
# Pass 2: Swapped 25 and 12 -> [11, 12, 25, 22, 64]
# Pass 3: Swapped 25 and 22 -> [11, 12, 22, 25, 64]
# Pass 4: No swap needed -> [11, 12, 22, 25, 64]
# Sorted: [11, 12, 22, 25, 64]

Program 4: Insertion Sort Implementation

def insertion_sort(arr):
 n = len(arr)
 for i in range(1, n):
 key = arr[i]
 j = i - 1
 print(f"Pass {i}: key = {key}")

 while j >= 0 and arr[j] > key:
 arr[j + 1] = arr[j]
 j -= 1

 arr[j + 1] = key
 print(f" Inserted {key} at index {j+1} -> {arr}")

 return arr

# Test
data = [64, 34, 25, 12, 22]
print("Original:", data)
result = insertion_sort(data)
print("Sorted: ", result)

# Output:
# Original: [64, 34, 25, 12, 22]
# Pass 1: key = 34
# Inserted 34 at index 0 -> [34, 64, 25, 12, 22]
# Pass 2: key = 25
# Inserted 25 at index 0 -> [25, 34, 64, 12, 22]
# Pass 3: key = 12
# Inserted 12 at index 0 -> [12, 25, 34, 64, 22]
# Pass 4: key = 22
# Inserted 22 at index 1 -> [12, 22, 25, 34, 64]
# Sorted: [12, 22, 25, 34, 64]

Program 5: Sort in Descending Order (All Three)

# Bubble Sort - Descending
def bubble_sort_desc(arr):
 n = len(arr)
 for i in range(n - 1):
 for j in range(n - 1 - i):
 if arr[j] < arr[j + 1]: # Changed > to <
 arr[j], arr[j + 1] = arr[j + 1], arr[j]
 return arr

# Selection Sort - Descending
def selection_sort_desc(arr):
 n = len(arr)
 for i in range(n - 1):
 max_idx = i # Find maximum instead of minimum
 for j in range(i + 1, n):
 if arr[j] > arr[max_idx]: # Changed < to >
 max_idx = j
 if max_idx != i:
 arr[i], arr[max_idx] = arr[max_idx], arr[i]
 return arr

# Insertion Sort - Descending
def insertion_sort_desc(arr):
 n = len(arr)
 for i in range(1, n):
 key = arr[i]
 j = i - 1
 while j >= 0 and arr[j] < key: # Changed > to <
 arr[j + 1] = arr[j]
 j -= 1
 arr[j + 1] = key
 return arr

# Test all three
data = [12, 22, 25, 34, 64]

print("Bubble Sort (Desc): ", bubble_sort_desc(data[:]))
print("Selection Sort (Desc):", selection_sort_desc(data[:]))
print("Insertion Sort (Desc):", insertion_sort_desc(data[:]))

# Output:
# Bubble Sort (Desc): [64, 34, 25, 22, 12]
# Selection Sort (Desc): [64, 34, 25, 22, 12]
# Insertion Sort (Desc): [64, 34, 25, 22, 12]

Program 6: Count Comparisons and Swaps

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

def selection_sort_count(arr):
 n = len(arr)
 comparisons = 0
 swaps = 0
 for i in range(n - 1):
 min_idx = i
 for j in range(i + 1, n):
 comparisons += 1
 if arr[j] < arr[min_idx]:
 min_idx = j
 if min_idx != i:
 arr[i], arr[min_idx] = arr[min_idx], arr[i]
 swaps += 1
 return arr, comparisons, swaps

def insertion_sort_count(arr):
 n = len(arr)
 comparisons = 0
 shifts = 0
 for i in range(1, n):
 key = arr[i]
 j = i - 1
 while j >= 0:
 comparisons += 1
 if arr[j] > key:
 arr[j + 1] = arr[j]
 shifts += 1
 j -= 1
 else:
 break
 
 arr[j + 1] = key
 return arr, comparisons, shifts

# Test with same data
data = [64, 34, 25, 12, 22]

result_b, comp_b, swap_b = bubble_sort_count(data[:])
result_s, comp_s, swap_s = selection_sort_count(data[:])
result_i, comp_i, shift_i = insertion_sort_count(data[:])

print(f"Data: {[64, 34, 25, 12, 22]}")
print
print(f"{'Algorithm':<20}{'Comparisons':<15}{'Swaps/Shifts':<15}{'Result'}")
print("=" * 70)
print(f"{'Bubble Sort':<20}{comp_b:<15}{swap_b:<15}{result_b}")
print(f"{'Selection Sort':<20}{comp_s:<15}{swap_s:<15}{result_s}")
print(f"{'Insertion Sort':<20}{comp_i:<15}{shift_i:<15}{result_i}")

# Output:
# Data: [64, 34, 25, 12, 22]
#
# Algorithm Comparisons Swaps/Shifts Result
# ======================================================================
# Bubble Sort 10 8 [12, 22, 25, 34, 64]
# Selection Sort 10 3 [12, 22, 25, 34, 64]
# Insertion Sort 10 8 [12, 22, 25, 34, 64]

---

Common Mistakes

Mistake	Correct Approach
Bubble sort inner loop going to n-1	Inner loop: range(n - 1 - i) to skip sorted elements
Selection sort swapping inside inner loop	Only swap AFTER finding the minimum
Insertion sort starting from index 0	Start from index 1 (first element is trivially sorted)
Confusing > and < for ascending vs descending	> for ascending, < for descending
Forgetting the -1 in range for passes	n elements need n-1 passes
Modifying original list accidentally	Use arr[:] to pass a copy for testing

---

$1$2 Quick Tips

1. Tracing is the most common question type: Given an array, show the state after each pass. Practice tracing all three algorithms.
2. Code writing: Be able to write any of the three algorithms from memory. Bubble sort is most commonly asked.
3. Comparison question: Know best/worst/average time complexity and stability of all three.
4. Bubble sort optimization (flag-based early termination) is a popular 3-mark question.
5. Selection sort has the fewest swaps (at most n-1), this is a common MCQ.
6. Insertion sort is best for nearly sorted data, know why (fewer shifts needed).
7. Descending order: Just change the comparison operator, commonly asked as a modification question.
8. Time complexity: All three are O(n^2) in the worst case. Python's built-in sort is O(n log n).
9. Remember the analogy: Bubble = bubbling up, Selection = selecting minimum, Insertion = inserting cards.