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 − comparisons; overall, a
1
sort makes a total n − full passes with
of 1

decreasing comparisons.

Worked Example
Starting list: numList = [8, 7, 1 3, 1 , -9, 4]
(n = 6, so 5 passes)

List
Comparisons made
Pass aft
(adjacent pairs)
er
pas
s

(8,7)→swap, (8,1 3)→no [7, 8, 1 ,

1 change, (1 3,1 )→swap, (1 -9, 4,
3,-9)→swap,
1 3]
(1 3,4)→swap

(7,8)→no change, (8,1 )→swap, [7, 1 , -

2 (8,-9)→swap, (8,4)→swap 9,
4, 8, 1
3]
(7,1 )→swap, (7,-9)→swap, [1 , -9,
3 (7,4)→swap 4,
7, 8, 1
3]
[-9, 1 ,
4 (1 ,-9)→swap, (1 ,4)→no change
4,
7, 8, 1
3]
 List
Comparisons made
Pass aft
(adjacent pairs)
er
pas
s

(-9,1 )→no change (already in [-9, 1 ,

5 order) 4,
7, 8, 1
3]

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(numLi
st, n) Step 1: SET
i = 0
Step SET j = 0
3: WHILE j < n-i-1, REPEAT
Step STEPS 5
4:
IF
to 7 numList[j]
numList[j+1] THEN
Step 6:

swap(numList[j],
numList[j+1])

Python Implementation (Program 5-1 )

 def
bubble_sort(lis
t1): n = #
len(list1)
for i in # -i-
range(n): 1
number of
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

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
Fals each pass;
if it stays False after a full passe(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 instead of > .
+1]

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 n − passes.
1
takes

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, 1 3, 1 , -9, 4]

List
Minimum
Pass found Swap aft
in unsorted er
part pas
s

[-9, 7,
swap with
1 -9 (index 4) 1 3, 1 , 8,
index 0
4]

[-9, 1 ,
swap with
2 1 (index 3) 1 3, 7, 8,
index 1
4]

swap with [-9, 1 , 4,

3 4 (index 5)
index 2 7, 8, 1 3]

already in [-9, 1 , 4,
4 7 (index 3)
place 7, 8, 1 3]

already in [-9, 1 , 4,
5 8 (index 4)
place 7, 8, 1 3]

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

(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
Step 3 toSET
11 min = i
3: SET j = i+1
Step WHILE j < n, REPEAT
4: STEPS 6 to
Step
5: IF
numList[min] numList[j]
THEN
Step 7: SET min
= j Step 8: SET j = j+1
Step 9: IF min != i
THEN
Step 10:

swap(numList[i],

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
forthrough all list
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] =
 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, 1 3, 1 , -9, 4]

List after
Pass Element being inserted
pass

7 → compared with 8, [7, 8, 1 3, 1

1 ,
shifts left
-9, 4]
1 3 → already bigger than [7, 8, 1 3, 1
2 8, no change ,
-9, 4]
[1 , 7, 8, 1
3 1 → shifts past 1 3, 8, 7 3,
-9, 4]
[-9, 1 , 7, 8,
4 -9 → shifts past 1 3, 8, 7, 1
1 3, 4]

4 → shifts past 1 3, 8, 7; [-9, 1 , 4, 7,

5 stops after 1 8, 1 3]

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

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 SET j = j-1
7: numList[j+1] = #
Step temp SET i = insert
8:
i+1

Python Implementation (Program 5-3)

def
insertion_sort(list
3): n = len(list3) #
for i in range(n):
traverse through all
elements temp =
list3[i]
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)):

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 Complexit Example
structur y
e
A single
Constant No
O(1 ) arithmetic
time loop at
operation
all

One
Linear single Traversing
O(n)
time loop a list once
(1 to
n)

A loop
Bubble,
neste
Quadratic Selection,
d O(n²)
time Insertion
inside
sort
anothe
r 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 minimu eleme
Core idea
out-of- m, swap nt into
order pairs to 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
Stable sort? Yes can Yes
reorder
equal
elements)
Best O ( n ) with
O(n²)
case early-stop O(n)
always
(already optimizatio
sorted) n

Worst/
Average O(n²) O(n²) O(n²)
case
Repeated Arranging
Bubbles
Everyday ly picking playing
rising to
analogy the cards in
the top
smallest hand
item

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,
[1, 4,
3, 11, 10, 17, 23,
21,
5] 7, 4,
Pass 2 (min=3):
21, [1, 3, 4, 10, 17, 23,
5] 7, 11,
Pass 3 (min=4):
21, [1, 3, 4, 5, 17, 23,
5] 7, 11,
Pass 4 (min=5):
21,
10]
→ After 4 passes: [1 , 3, 4, 5, 1 7, 23, 7, 1 1 , 21
, 1 0] (first four positions locked in sorted
order)
Activity — Insertion sort, 3 passes[7,
on 11,
3,
10, 17, 23, 1, 4,
21, 5] :
Pass 1 (insert 1 1 ):[7, 11, 3, 10, 17,
23, 1,
4, 21, (no change)
5]
Pass 2 (insert 3):[3, 7, 11, 10, 17, 23,
1, 4,
21,
5]
Pass 3 (insert 1 0):[3, 7, 10, 11, 17,
23, 1,
4, 21,
5]
→ After 3 passes: [3, 7, 1 0, 1 1 , 1 7, 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.