Chapter 5: Sorting

CBSE Unit: NOT explicitly in current CBSE syllabus (2025-26), but bubble sort/insertion sort may appear Status: Supplementary, sorting is a fundamental CS concept, likely to be added Priority: PREPARE, bubble sort especially is frequently asked even in current papers

---

Key Concepts

5.1 What is Sorting?

• Process of arranging elements in a particular order (ascending/descending), Enables efficient searching (binary search requires sorted data), Three sorting algorithms covered: Bubble Sort, Selection Sort, Insertion Sort
• All three are comparison-based, in-place sorting algorithms with O(n^2) worst-case time complexity

---

5.2 Bubble Sort

Concept, Compare adjacent elements, swap if out of order, After each pass, largest unsorted element "bubbles up" to its correct position, Total passes: n-1 for n elements, Each pass reduces the comparison range by 1 (last elements already sorted)

Algorithm

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

Python Implementation (Ascending Order)

def bubble_sort(list1):
    n = len(list1)
    for i in range(n):                    # number of passes
        for j in range(0, n - i - 1):     # compare adjacent
            if list1[j] > list1[j + 1]:
                list1[j], list1[j + 1] = list1[j + 1], list1[j]

numList = [8, 7, 13, 1, -9, 4]
bubble_sort(numList)
print(numList)  # [-9, 1, 4, 7, 8, 13]

Python Implementation (Descending Order)

def bubble_sort_desc(list1):
    n = len(list1)
    for i in range(n):
        for j in range(0, n - i - 1):
            if list1[j] < list1[j + 1]:   # flip comparison: < instead of >
                list1[j], list1[j + 1] = list1[j + 1], list1[j]

numList = [8, 7, 13, 1, -9, 4]
bubble_sort_desc(numList)
print(numList)  # [13, 8, 7, 4, 1, -9]

Step-by-Step Dry Run Trace: Bubble Sort

Input: [8, 7, 13, 1, -9, 4] (n = 6)

Pass 1 (i=0): Compare from index 0 to 4

j	Compare	Action	List After
0	8 > 7? Yes	Swap	[7, 8, 13, 1, -9, 4]
1	8 > 13? No	No swap	[7, 8, 13, 1, -9, 4]
2	13 > 1? Yes	Swap	[7, 8, 1, 13, -9, 4]
3	13 > -9? Yes	Swap	[7, 8, 1, -9, 13, 4]
4	13 > 4? Yes	Swap	[7, 8, 1, -9, 4, 13]

After Pass 1: [7, 8, 1, -9, 4, 13] (13 is in final position)

Pass 2 (i=1): Compare from index 0 to 3

j	Compare	Action	List After
0	7 > 8? No	No swap	[7, 8, 1, -9, 4, 13]
1	8 > 1? Yes	Swap	[7, 1, 8, -9, 4, 13]
2	8 > -9? Yes	Swap	[7, 1, -9, 8, 4, 13]
3	8 > 4? Yes	Swap	[7, 1, -9, 4, 8, 13]

After Pass 2: [7, 1, -9, 4, 8, 13] (8 is in final position)

Pass 3 (i=2): Compare from index 0 to 2

j	Compare	Action	List After
0	7 > 1? Yes	Swap	[1, 7, -9, 4, 8, 13]
1	7 > -9? Yes	Swap	[1, -9, 7, 4, 8, 13]
2	7 > 4? Yes	Swap	[1, -9, 4, 7, 8, 13]

After Pass 3: [1, -9, 4, 7, 8, 13] (7 is in final position)

Pass 4 (i=3): Compare from index 0 to 1

j	Compare	Action	List After
0	1 > -9? Yes	Swap	[-9, 1, 4, 7, 8, 13]
1	1 > 4? No	No swap	[-9, 1, 4, 7, 8, 13]

After Pass 4: [-9, 1, 4, 7, 8, 13] (4 is in final position)

Pass 5 (i=4): Compare from index 0 to 0

j	Compare	Action	List After
0	-9 > 1? No	No swap	[-9, 1, 4, 7, 8, 13]

Final sorted list: [-9, 1, 4, 7, 8, 13]

Time Complexity

• Worst case: O(n^2), list is reverse sorted
• Best case: O(n), list is already sorted (with optimization)
• Optimization: if no swaps in a pass, list is sorted, stop early

Optimized Bubble Sort

def bubble_sort_optimized(list1):
    n = len(list1)
    for i in range(n):
        swapped = False
        for j in range(0, n - i - 1):
            if list1[j] > list1[j + 1]:
                list1[j], list1[j + 1] = list1[j + 1], list1[j]
                swapped = True
        if not swapped:    # no swaps = already sorted
            break

Example where optimization helps: Input: [1, 2, 3, 4, 5] (already sorted), Pass 1: 0 swaps -> swapped = False -> break immediately, Only 1 pass instead of 4 -> O(n) instead of O(n^2)

---

5.3 Selection Sort

Concept, Find the minimum element in unsorted portion, swap with the leftmost unsorted element, Divides list into: sorted (left) and unsorted (right) portions, Total passes: n-1

• Key characteristic: minimum number of swaps (exactly n-1 swaps maximum)

Algorithm

For i = 0 to n-2:
    Find index of minimum element in list[i:n]
    Swap list[i] with list[min_index]

Python Implementation (Ascending Order)

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

numList = [8, 7, 13, 1, -9, 4]
selection_sort(numList)
print(numList)  # [-9, 1, 4, 7, 8, 13]

Python Implementation (Descending Order)

def selection_sort_desc(list1):
    n = len(list1)
    for i in range(n - 1):
        max_idx = i
        for j in range(i + 1, n):
            if list1[j] > list1[max_idx]:    # find MAXIMUM instead
                max_idx = j
        list1[i], list1[max_idx] = list1[max_idx], list1[i]

numList = [8, 7, 13, 1, -9, 4]
selection_sort_desc(numList)
print(numList)  # [13, 8, 7, 4, 1, -9]

Step-by-Step Dry Run Trace: Selection Sort

Input: [8, 7, 13, 1, -9, 4] (n = 6)

Pass 1 (i=0): Find minimum in list[0:6]

j	list[j]	min_idx	list[min_idx]	Action
1	7	1	7	7 < 8, update min_idx to 1
2	13	1	7	13 > 7, no change
3	1	3	1	1 < 7, update min_idx to 3
4	-9	4	-9	-9 < 1, update min_idx to 4
5	4	4	-9	4 > -9, no change

Swap list[0] with list[4]: [8, 7, 13, 1, -9, 4] -> [-9, 7, 13, 1, 8, 4] Sorted so far: [-9 | 7, 13, 1, 8, 4]

Pass 2 (i=1): Find minimum in list[1:6]

j	list[j]	min_idx	list[min_idx]
2	13	1	7
3	1	3	1
4	8	3	1
5	4	3	1

Swap list[1] with list[3]: [-9, 7, 13, 1, 8, 4] -> [-9, 1, 13, 7, 8, 4] Sorted so far: [-9, 1 | 13, 7, 8, 4]

Pass 3 (i=2): Find minimum in list[2:6]

j	list[j]	min_idx	list[min_idx]
3	7	3	7
4	8	3	7
5	4	5	4

Swap list[2] with list[5]: [-9, 1, 13, 7, 8, 4] -> [-9, 1, 4, 7, 8, 13] Sorted so far: [-9, 1, 4 | 7, 8, 13]

Pass 4 (i=3): Find minimum in list[3:6]

Min = 7 at index 3. Swap list[3] with list[3] (no actual change). Sorted so far: [-9, 1, 4, 7 | 8, 13]

Pass 5 (i=4): Find minimum in list[4:6]

Min = 8 at index 4. Swap list[4] with list[4] (no actual change).

Final sorted list: [-9, 1, 4, 7, 8, 13]

Total swaps: 3 (much fewer than bubble sort!)

Time Complexity

• All cases: O(n^2), always scans entire unsorted portion
• No best case optimization - unlike bubble sort, selection sort always makes the same number of comparisons
• Advantage: minimum number of swaps (at most n-1)

Selection Sort vs Bubble Sort

Aspect	Bubble Sort	Selection Sort
# Swaps	Can be many (up to n^2/2)	At most n-1
Best case	O(n) with optimization	O(n^2) always
When to prefer	Nearly sorted data	When swaps are expensive

---

5.4 Insertion Sort

Concept, Builds sorted list one element at a time, Takes each element and inserts it at the correct position in the sorted portion, Like sorting playing cards in your hand, Starts from index 1 (first element is considered "already sorted")

Algorithm

For i = 1 to n-1:
    key = list[i]
    j = i - 1
    While j >= 0 and list[j] > key:
        list[j+1] = list[j]    # shift right
        j = j - 1
    list[j+1] = key

Python Implementation (Ascending Order)

def insertion_sort(list1):
    for i in range(1, len(list1)):
        key = list1[i]
        j = i - 1
        while j >= 0 and list1[j] > key:
            list1[j + 1] = list1[j]
            j -= 1
        list1[j + 1] = key

numList = [8, 7, 13, 1, -9, 4]
insertion_sort(numList)
print(numList)  # [-9, 1, 4, 7, 8, 13]

Python Implementation (Descending Order)

def insertion_sort_desc(list1):
    for i in range(1, len(list1)):
        key = list1[i]
        j = i - 1
        while j >= 0 and list1[j] < key:   # flip: < instead of >
            list1[j + 1] = list1[j]
            j -= 1
        list1[j + 1] = key

numList = [8, 7, 13, 1, -9, 4]
insertion_sort_desc(numList)
print(numList)  # [13, 8, 7, 4, 1, -9]

Step-by-Step Dry Run Trace: Insertion Sort

Input: [8, 7, 13, 1, -9, 4] (n = 6)

Pass 1 (i=1): key = 7, sorted portion = [8]

j	list[j]	list[j] > key?	Action
0	8	8 > 7? Yes	Shift 8 right: [8, 8, 13, 1, -9, 4]
-1	-	Exit loop	Place key at j+1=0

List: [7, 8, 13, 1, -9, 4] (sorted portion: [7, 8])

Pass 2 (i=2): key = 13, sorted portion = [7, 8]

j	list[j]	list[j] > key?	Action
1	8	8 > 13? No	Exit loop

List: [7, 8, 13, 1, -9, 4] (13 already in place, sorted portion: [7, 8, 13])

Pass 3 (i=3): key = 1, sorted portion = [7, 8, 13]

j	list[j]	list[j] > key?	Action
2	13	13 > 1? Yes	Shift: [7, 8, 13, 13, -9, 4]
1	8	8 > 1? Yes	Shift: [7, 8, 8, 13, -9, 4]
0	7	7 > 1? Yes	Shift: [7, 7, 8, 13, -9, 4]
-1	-	Exit loop	Place key at j+1=0

List: [1, 7, 8, 13, -9, 4] (sorted portion: [1, 7, 8, 13])

Pass 4 (i=4): key = -9, sorted portion = [1, 7, 8, 13]

j	list[j]	list[j] > key?	Action
3	13	Yes	Shift: [1, 7, 8, 13, 13, 4]
2	8	Yes	Shift: [1, 7, 8, 8, 13, 4]
1	7	Yes	Shift: [1, 7, 7, 8, 13, 4]
0	1	Yes	Shift: [1, 1, 7, 8, 13, 4]
-1	-	Exit loop	Place key at j+1=0

List: [-9, 1, 7, 8, 13, 4] (sorted portion: [-9, 1, 7, 8, 13])

Pass 5 (i=5): key = 4, sorted portion = [-9, 1, 7, 8, 13]

j	list[j]	list[j] > key?	Action
4	13	Yes	Shift: [-9, 1, 7, 8, 13, 13]
3	8	Yes	Shift: [-9, 1, 7, 8, 8, 13]
2	7	Yes	Shift: [-9, 1, 7, 7, 8, 13]
1	1	1 > 4? No	Exit loop

Place key at j+1=2: [-9, 1, 4, 7, 8, 13]

Final sorted list: [-9, 1, 4, 7, 8, 13]

Time Complexity

• Worst case: O(n^2), list is reverse sorted (maximum shifts)
• Best case: O(n), list is already sorted (inner loop never executes)
• Good for: nearly sorted data and small datasets

---

Sorting Strings

All three algorithms work with strings too (Python compares strings lexicographically):

def bubble_sort(lst):
    n = len(lst)
    for i in range(n):
        for j in range(0, n - i - 1):
            if lst[j] > lst[j + 1]:
                lst[j], lst[j + 1] = lst[j + 1], lst[j]

names = ["Priya", "Aarav", "Zara", "Kabir", "Meera"]
bubble_sort(names)
print(names)  # ['Aarav', 'Kabir', 'Meera', 'Priya', 'Zara']

Note on string comparison: Python compares strings character by character using ASCII/Unicode values.

• 'A' (65) < 'Z' (90) < 'a' (97) < 'z' (122), So "Zara" < "aarav" (uppercase comes before lowercase), To sort case-insensitively, use .lower() in comparison

---

Sorting with Custom Key (Bonus)

Sort a list of tuples by second element (marks):

students = [("Aarav", 85), ("Priya", 92), ("Kabir", 78), ("Zara", 95)]

# Using insertion sort
def sort_by_marks(lst):
    for i in range(1, len(lst)):
        key = lst[i]
        j = i - 1
        while j >= 0 and lst[j][1] > key[1]:  # compare by marks (index 1)
            lst[j + 1] = lst[j]
            j -= 1
        lst[j + 1] = key

sort_by_marks(students)
print(students)
# [('Kabir', 78), ('Aarav', 85), ('Priya', 92), ('Zara', 95)]

---

Comparison of Sorting Algorithms

Feature	Bubble Sort	Selection Sort	Insertion Sort
Approach	Compare adjacent, swap	Find min, swap to front	Insert in correct position
Best case	O(n) with optimization	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)
Stable?	Yes	No	Yes
In-place?	Yes	Yes	Yes
Best for	Nearly sorted data	When swaps are expensive	Nearly sorted, small data
# Swaps (worst)	O(n^2)	O(n), exactly n-1	O(n^2) shifts
# Comparisons (worst)	O(n^2)	O(n^2)	O(n^2)

What is stability? A sorting algorithm is stable if it preserves the relative order of equal elements. Example:

Input:  [(A, 3), (B, 1), (C, 3), (D, 2)]
Stable sort by number:  [(B, 1), (D, 2), (A, 3), (C, 3)]  <- A before C (original order)
Unstable sort:          [(B, 1), (D, 2), (C, 3), (A, 3)]  <- C before A (order changed)

Selection sort is unstable because it can swap non-adjacent elements.

---

Summary Table: Number of Operations

For the example [8, 7, 13, 1, -9, 4]:

Algorithm	Passes	Comparisons	Swaps/Shifts
Bubble Sort	5	15	11 swaps
Selection Sort	5	15	3 swaps
Insertion Sort	5	12	12 shifts

---

Practice Problems

1. Dry run bubble sort on [5, 3, 8, 1, 2]. Show the list after each pass.
2. Dry run selection sort on [29, 10, 14, 37, 13]. Show min_idx and swap at each step.
3. Dry run insertion sort on [12, 11, 13, 5, 6]. Show key and shifts at each step.
4. Write a Python function to sort a list of strings in descending order using selection sort.
5. How many passes are needed to sort [1, 2, 3, 4, 5] using optimized bubble sort? (Answer: 1)
6. Which sorting algorithm makes the fewest swaps? (Answer: Selection sort)
7. Can you modify bubble sort to detect if the list is already sorted? Write the code.
8. Sort the list [64, 25, 12, 22, 11] using all three algorithms. Compare the number of swaps.

---

Key Points Students Miss

1. Bubble sort, after pass i, the last i elements are in their final position
2. Selection sort, minimum swaps (exactly n-1), but always O(n^2) comparisons
3. Insertion sort, starts from index 1, not 0 (first element is "sorted" by itself)
4. For descending order: just flip the comparison (> becomes <)
5. All three are O(n^2) in worst case, inefficient for large datasets
6. Python's built-in sort() uses TimSort which is O(n log n), much faster
7. Selection sort is the only unstable sort among the three
8. Insertion sort uses shifts (not swaps), element slides into position
9. Optimized bubble sort has O(n) best case; standard bubble sort does not
10. In exam dry-run questions, show the list state after EACH pass - not just the final result

---

Board Exam Tips

1. For dry-run questions, create a clear table with columns for each variable, show values at EVERY step
2. Bubble sort is the most commonly asked, know it thoroughly with trace
3. When asked to "write a program to sort", you can use any of the three algorithms unless specified
4. For "difference between" questions, compare at least 4 points (approach, complexity, swaps, stability)
5. Remember: changing > to < in the comparison converts ascending sort to descending sort
6. If asked about efficiency, mention both time complexity AND space complexity (all three are O(1) extra space)