Chapter 5: Sorting — Complete
Study Notes
Computer Science, Class XII
Note: Your photos are from Chapter 5 (Sorting), not
Chapter 4 — the notes below are titled accordingly.
5.1 Introduction to Sorting
Sorting is the process of arranging the elements of a
collection into a particular order.
Numbers → ascending (increasing) or descending
(decreasing) order
Strings → alphabetical order (A–Z or Z–A), or by
length
Records → by any chosen key, e.g. a list of
students sorted by height, weight, or roll number
Why it matters: Sorted data is much faster to search.
A dictionary is sorted alphabetically so you don't have
to scan every page to find a word; exam seats are
arranged by roll number so students can find their seat
quickly. This is the whole point of sorting — it makes
searching and organising data efficient.
Real-world/computing examples of sorting in action:
Search engines ranking results
E-commerce sites sorting products by price/rating
Phone contact lists (alphabetical)
File explorers sorting by name, date, or size
Leaderboards in games, exam merit lists
Database indexing for fast lookups
Chapter roadmap: Introduction → Bubble Sort →
Selection Sort → Insertion Sort → Time Complexity of
Algorithms.
5.2 Bubble Sort
Concept
Bubble sort repeatedly steps through the list,
compares each pair of adjacent elements, and swaps
them if they are in the wrong order. Larger elements
gradually "bubble up" to the end of the list — hence the
name.
A list of n elements needs at most n − 1 passes.
In each pass, adjacent elements are compared and
swapped where needed; after each pass, the next-
largest unplaced element settles into its correct
position at the end.
Each successive pass has one fewer comparison
than the last, because the largest elements at the
end are already sorted and don't need to be re-
checked.
Pass 1 makes n − 1 comparisons; overall, a full
sort makes a total of n − 1 passes with
decreasing comparisons.
Worked Example
Starting list: numList = [8, 7, 13, 1, -9, 4] (n = 6, so 5
passes)
List
Comparisons made (adjacent
Pass after
pairs)
pass
(8,7)→swap, (8,13)→no change, [7, 8, 1,
1 (13,1)→swap, (13,-9)→swap, -9, 4,
(13,4)→swap 13]
(7,8)→no change, (8,1)→swap, [7, 1, -9,
2
(8,-9)→swap, (8,4)→swap 4, 8, 13]
(7,1)→swap, (7,-9)→swap, [1, -9, 4,
3
(7,4)→swap 7, 8, 13]
[-9, 1, 4,
4 (1,-9)→swap, (1,4)→no change
7, 8, 13]
List
Comparisons made (adjacent
Pass after
pairs)
pass
(-9,1)→no change (already in [-9, 1, 4,
5
order) 7, 8, 13]
Notice Pass 5 makes no swaps at all — the list was
already fully sorted after Pass 4! This leads to a very
common exam question (see "Optimization" below).
Legend used in the textbook figures: blue = elements
currently being compared/swapped; green = elements
already in their final sorted position.
Algorithm 5.1 — Bubble Sort (pseudocode)
BUBBLESORT(numList, n)
Step 1: SET i = 0
Step 2: WHILE i < n REPEAT STEPS 3 to 8
Step 3: SET j = 0
Step 4: WHILE j < n-i-1, REPEAT STEPS 5
to 7
Step 5: IF numList[j] >
numList[j+1] THEN
Step 6: swap(numList[j],
numList[j+1])
Step 7: SET j = j+1
Step 8: SET i = i+1
Python Implementation (Program 5-1)
def bubble_sort(list1):
n = len(list1)
for i in range(n): #
number of passes
for j in range(0, n-i-1): # -i-1
since last i elements are sorted
if list1[j] > list1[j+1]:
# swap element at jth
position with (j+1)th position
list1[j], list1[j+1] =
list1[j+1], list1[j]
numList = [8, 7, 13, 1, -9, 4]
bubble_sort(numList)
print("The sorted list is:")
for i in range(len(numList)):
print(numList[i], end=" ")
Output:
The sorted list is:
-9 1 4 7 8 13
💡 Optimization (common exam question)
Since Pass 5 above made zero swaps, the list was
clearly already sorted — continuing was wasted work.
You can improve the algorithm by adding a
flag / swapped variable that starts False each pass;
if it stays False after a full pass (no swaps occurred),
break out of the loop early since the list must already
be sorted. This turns the best case (already-sorted
input) into O(n) instead of always running O(n²).
For descending order
Simply flip the comparison: swap when numList[j] <
numList[j+1] instead of > .
5.3 Selection Sort
Concept
Selection sort divides the list into two parts: a sorted
sublist (built from the left) and an unsorted sublist
(the rest). In each pass:
1. Find the smallest element in the unsorted part.
2. Swap it with the leftmost element of the unsorted
part.
3. The sorted part grows by one element; the
unsorted part shrinks by one.
This repeats until the unsorted part has only one
element left (which is then automatically in place). A
list of n elements takes n − 1 passes.
Key difference from Bubble Sort: only one swap per
pass (at most), rather than many — selection sort
minimizes the number of swaps, but still makes the
same number of comparisons.
Worked Example
Starting list: numList = [8, 7, 13, 1, -9, 4]
List
Minimum found
Pass Swap after
in unsorted part
pass
[-9, 7,
swap with
1 -9 (index 4) 13, 1, 8,
index 0
4]
[-9, 1,
swap with
2 1 (index 3) 13, 7, 8,
index 1
4]
swap with [-9, 1, 4,
3 4 (index 5)
index 2 7, 8, 13]
already in [-9, 1, 4,
4 7 (index 3)
place 7, 8, 13]
already in [-9, 1, 4,
5 8 (index 4)
place 7, 8, 13]
Final sorted list: [-9, 1, 4, 7, 8, 13] ✅ (matches the
program output below)
Algorithm 5.2 — Selection Sort (pseudocode)
SELECTIONSORT(numList, n)
Step 1: SET i = 0
Step 2: WHILE i < n REPEAT STEPS 3 to 11
Step 3: SET min = i
Step 4: SET j = i+1
Step 5: WHILE j < n, REPEAT STEPS 6 to
8
Step 6: IF numList[j] <
numList[min] THEN
Step 7: SET min = j
Step 8: SET j = j+1
Step 9: IF min != i THEN
Step 10: swap(numList[i],
numList[min])
Step 11: SET i = i+1
Python Implementation (Program 5-2)
def selection_sort(list2):
flag = 0 # to
decide when to swap
n = len(list2)
for i in range(n): #
traverse through all list elements
min = i
for j in range(i + 1, len(list2)):
# left elements already sorted
if list2[j] < list2[min]:
# element at j is smaller
min = j
flag = 1
if flag == 1: # next
smallest element found
list2[min], list2[i] =
list2[i], list2[min]
numList = [8, 7, 13, 1, -9, 4]
selection_sort(numList)
print("The sorted list is:")
for i in range(len(numList)):
print(numList[i], end=" ")
Output:
The sorted list is:
-9 1 4 7 8 13
5.4 Insertion Sort
Concept
Like selection sort, insertion sort keeps a sorted part
and an unsorted part. But instead of searching for the
minimum, it takes the first element of the unsorted
part one at a time and inserts it into its correct
position within the sorted part — shifting larger
elements to the right to make room.
This is exactly how most people sort playing cards in
their hand: pick up one card at a time and slot it into
the correct place among the cards you're already
holding.
Worked Example
Starting list: numList = [8, 7, 13, 1, -9, 4]
List after
Pass Element being inserted
pass
7 → compared with 8, shifts [7, 8, 13, 1,
1
left -9, 4]
13 → already bigger than 8, [7, 8, 13, 1,
2
no change -9, 4]
[1, 7, 8, 13,
3 1 → shifts past 13, 8, 7
-9, 4]
[-9, 1, 7, 8,
4 -9 → shifts past 13, 8, 7, 1
13, 4]
4 → shifts past 13, 8, 7; [-9, 1, 4, 7,
5
stops after 1 8, 13]
Final sorted list: [-9, 1, 4, 7, 8, 13] ✅
Algorithm 5.3 — Insertion Sort (pseudocode)
INSERTIONSORT(numList, n)
Step 1: SET i = 1
Step 2: WHILE i < n REPEAT STEPS 3 to 9
Step 3: temp = numList[i]
Step 4: SET j = i-1
Step 5: WHILE j >= 0 and numList[j] >
temp, REPEAT STEPS 6 to 7
Step 6: numList[j+1] = numList[j]
Step 7: SET j = j-1
Step 8: numList[j+1] = temp # insert
Step 9: SET i = i+1
Python Implementation (Program 5-3)
def insertion_sort(list3):
n = len(list3)
for i in range(n): #
traverse through all elements
temp = list3[i]
j = i - 1
while j >= 0 and temp < list3[j]:
list3[j+1] = list3[j]
j = j - 1
list3[j+1] = temp
numList = [8, 7, 13, 1, -9, 4]
insertion_sort(numList)
print("The sorted list is:")
for i in range(len(numList)):
print(numList[i], end=" ")
Output:
The sorted list is:
-9 1 4 7 8 13
5.5 Time Complexity of Algorithms
Time complexity = the amount of time an algorithm
takes to process a given amount of data. For small
datasets, differences between algorithms barely
matter — but for huge, real-world datasets, they matter
a great deal. Computer scientists study time
complexity to know how an algorithm's performance
changes as input size grows, which helps decide the
right algorithm for a given situation.
Rules of thumb for estimating time complexity
Loop
Type Complexity Example
structure
A single
Constant No loop
O(1) arithmetic
time at all
operation
One
Linear single Traversing
O(n)
time loop (1 a list once
to n)
A loop
Bubble,
nested
Quadratic Selection,
inside O(n²)
time Insertion
another
sort
loop
If an algorithm has both a nested loop and a
separate single loop, complexity is estimated based
on the nested loop only (since it dominates).
Why all three sorts are O(n²)
Look at the Python programs above — each one has a
loop inside another loop (an outer pass-loop and an
inner comparison loop). Following the rule above, this
means:
Bubble Sort = Selection Sort = Insertion Sort → O(n²)
time complexity
Quick Comparison Table
Selection Insertion
Feature Bubble Sort
Sort Sort
Insert
Swap Pick each
adjacent minimum, element
Core idea
out-of-order swap to into
pairs front sorted
part
Passes
n−1 n−1 n−1
needed
Swaps per Can be At most 1 Multiple
pass many shifts
Selection Insertion
Feature Bubble Sort
Sort Sort
(not true
"swaps")
No (swap
can
Stable sort? Yes reorder Yes
equal
elements)
Best case O(n) with
O(n²)
(already early-stop O(n)
always
sorted) optimization
Worst/Average
O(n²) O(n²) O(n²)
case
Repeatedly Arranging
Bubbles
Everyday picking the playing
rising to the
analogy smallest cards in
top
item hand
Chapter Summary
Sorting = arranging a collection of elements into a
particular order.
Bubble sort: simplest technique; repeatedly swaps
adjacent out-of-order elements over n − 1 passes.
Selection sort: repeatedly selects the smallest
element from the unsorted part and swaps it into
place at the front of that part.
Insertion sort: builds a sorted part by taking each
new element and inserting it into its correct
position (like sorting playing cards).
Time complexity: describes how an algorithm's
running time grows as input size increases. All
three algorithms above are O(n²) due to their
nested loops.
Solved Practice (based on textbook
Activities)
Activity — Selection sort, 4 passes on [7, 11, 3,
10, 17, 23, 1, 4, 21, 5] :
Pass 1 (min=1): [1, 11, 3, 10, 17, 23, 7, 4,
21, 5]
Pass 2 (min=3): [1, 3, 11, 10, 17, 23, 7, 4,
21, 5]
Pass 3 (min=4): [1, 3, 4, 10, 17, 23, 7, 11,
21, 5]
Pass 4 (min=5): [1, 3, 4, 5, 17, 23, 7, 11,
21, 10]
→ After 4 passes: [1, 3, 4, 5, 17, 23, 7, 11, 21, 10] (first
four positions locked in sorted order)
Activity — Insertion sort, 3 passes on [7, 11, 3,
10, 17, 23, 1, 4, 21, 5] :
Pass 1 (insert 11): [7, 11, 3, 10, 17, 23, 1,
4, 21, 5] (no change)
Pass 2 (insert 3): [3, 7, 11, 10, 17, 23, 1, 4,
21, 5]
Pass 3 (insert 10): [3, 7, 10, 11, 17, 23, 1,
4, 21, 5]
→ After 3 passes: [3, 7, 10, 11, 17, 23, 1, 4, 21, 5] (first
four positions form the sorted sublist)
Activity — Bubble sort on [8, 7, 6, 5, 4] (a
reverse-sorted, worst-case list):
Pass 1: [7, 6, 5, 4, 8]
Pass 2: [6, 5, 4, 7, 8]
Pass 3: [5, 4, 6, 7, 8]
Pass 4: [4, 5, 6, 7, 8] ✅ sorted
Note: unlike the main worked example, every single
pass here performs a swap — there's no redundant
final pass, because a fully reverse-sorted list is bubble
sort's worst case.
Exam-Ready Q&A
Q: Why is bubble sort called "bubble" sort? Larger
elements "bubble up" to their correct position at
the end of the list with each pass.
Q: How many passes does each algorithm need
for n elements? n − 1, for all three.
Q: Which sort makes the fewest swaps? Selection
sort (at most 1 swap per pass).
Q: Which sorts are stable? Bubble sort and
insertion sort; selection sort is generally not.
Q: What's the time complexity of all three, and
why? O(n²) — each has a loop nested inside
another loop.
Q: How can bubble sort be optimized? Add a flag
to detect when a pass makes zero swaps, then
stop early — the list is already sorted.