For more information Visit:

[Link]
Contents

Disclaimer and Acknowledgement 1

Disclaimer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
Sources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
Kannada Edition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

LICENSE 2

Chapter 5: Sorting 3
CHAPTER BLUEPRINT PLAN FOR FINAL EXAM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
STUDENT NOTES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
5.2 Bubble Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
5.3 Selection Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
5.4 Insertion Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
5.5 Time Complexity of Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Question and Answer Bank . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
VERY SHORT ANSWERS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Multiple Choice Questions MCQs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Fill in the Blanks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
DESCRIPTIVE QUESTIONS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2 Marks Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3 Marks Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
5 Marks Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
Chapter End Exercise Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
Disclaimer and Acknowledgement

Disclaimer
This eBook is distributed solely for educational and study-support purposes, with no commercial intent. The content
provided herein is offered on an “as-is” basis, and the editors or publishers do not assume any responsibility for errors,
inaccuracies, or ambiguities arising from the translation.
Readers are advised to refer to official textbooks, notifications, and original sources for verification. The authors or con-
tributors shall not be held responsible for any direct or indirect consequences arising from the use of this study material.

Sources
This Material has been prepared using the following sources:
1. NCERT Textbook for Class XII – Computer Science: [Link]
2. NCERT Textbook for Class XI – Computer Science: [Link]

Kannada Edition
The translation provided in the Kannada version has been facilitated using the Google Cloud Translation API. Every
possible effort has been made to ensure technical accuracy. However, due to the automated nature of the translation process,
there may be instances of linguistic nuances, variations in terminology, or minor differences in meaning.

1
LICENSE

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivs 4.0 International License. To
view a copy of this license, visit [Link] or send a letter to Creative Commons,
PO Box 1866, Mountain View, CA 94042, USA.

Figure 1: Licence

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivs 4.0 International License.
Portions of this work may include material under separate copyright. These materials are not covered by this Creative
Commons license and are used by permission or under applicable copyright exceptions.
This book is licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 4.0 International License.

2
Chapter 5: Sorting

CHAPTER BLUEPRINT PLAN FOR FINAL EXAM

VSA 1 MARK SA 2 MARKS LA 3 MARKS ESSAY 5 MARKS TOTAL
2 NIL 1 1 10 MARKS

STUDENT NOTES
5.1 Introduction
• Sorting is the process of ordering or arranging a given collection of elements in some particular order.
• Elements can be sorted in ascending (increasing) or descending (decreasing) order.
• Strings can be sorted alphabetically (a-z or z-a) or by length.
• Real-world examples:
– Words in a dictionary are sorted alphabetically.
– Examination hall seats are ordered by roll number.
– Students can be sorted by height or weight.
• Sorting makes searching easier and faster. For example, searching in an unsorted dictionary would be tedious.
• Sorting is important in computer science; many algorithms have been developed and analyzed for performance.
• In this chapter: Bubble Sort, Selection Sort, Insertion Sort, and Time Complexity.

5.2 Bubble Sort

• A simple sorting technique.
• Sorts by repeatedly comparing adjacent elements and swapping them if they are in the wrong order.
• Each full iteration through the list is called a pass.
• For a list of n elements, Bubble Sort makes n-1 passes.
• In each pass, the largest unsorted element “bubbles up” to its correct position at the end.
• The sorted portion grows from the end of the list towards the beginning.
Algorithm 5.1: Bubble Sort
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

3
PUC COMPUTER SCIENCE STUDY MATERIAL January 2, 2026

Optimization: Stop early if no swaps occur in a pass (list is already sorted).

Example 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): # Last i elements are already sorted
if list1[j] > list1[j+1]:
# Swap
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

5.3 Selection Sort

• Divides the list into two parts: sorted (left) and unsorted (right).
• Initially, the sorted list is empty.
• In each pass, the smallest element from the unsorted list is selected and swapped with the leftmost element of the
unsorted list.
• The sorted list grows from the beginning.
• Makes n-1 passes.
Algorithm 5.2: Selection Sort
SELECTIONSORT(numList, n)
Step 1: SET i = 0
Step 2: WHILE i < n REPEAT STEPS 3 to 11
Step 3: SET min = i, flag = 0
Step 4: SET j = i+1
Step 5: WHILE j < n, REPEAT STEPS 6 to 10
Step 6: IF numList[j] < numList[min] THEN
Step 7: min = j
Step 8: flag = 1
Step 9: IF flag = 1 THEN
Step 10: swap(numList[i], numList[min])
Step 11: SET i = i+1

Example Program 5-2:

def selection_Sort(list2):
n = len(list2)
for i in range(n):
min_idx = i
flag = 0
for j in range(i+1, n):
if list2[j] < list2[min_idx]:
min_idx = j
flag = 1
if flag == 1:
list2[min_idx], list2[i] = list2[i], list2[min_idx]

numList = [8, 7, 13, 1, -9, 4]

selection_Sort(numList)

Primus PU College, Bangalore 560 035 4

January 2, 2026 PUC COMPUTER SCIENCE STUDY MATERIAL

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

• Divides the list into sorted and unsorted parts.
• In each pass, the first element of the unsorted list is taken and inserted into the correct position in the sorted list by
shifting elements.
• The sorted list is traversed from the end to find the insertion point.
• Efficient for small or nearly sorted lists.
Algorithm 5.3: Insertion Sort
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
Step 9: SET i = i+1

Example Program 5-3:

def insertion_Sort(list3):
n = len(list3)
for i in range(1, n):
temp = list3[i]
j = i-1
while j >= 0 and temp < list3[j]:
list3[j+1] = list3[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 measures the amount of time an algorithm takes to process data.
• Important for large datasets.
• Rules for estimating time complexity:
– No loop → Constant time: O(1)
– Single loop → Linear time: O(n)
– Nested loop → Quadratic time: O(n2 )

5 L R Mohammed Matheen
PUC COMPUTER SCIENCE STUDY MATERIAL January 2, 2026

– If both nested and single loops exist, complexity is dominated by the nested loop.
• Bubble Sort, Selection Sort, and Insertion Sort all have O(n2 ) time complexity due to nested loops.

Summary
• Sorting: Arranging elements in a specific order.
• Bubble Sort: Repeatedly swaps adjacent elements; O(n2 ).
• Selection Sort: Selects smallest element and swaps; O(n2 ).
• Insertion Sort: Inserts each element into its correct position; O(n2 ).
• Complexity Analysis: Evaluates algorithm performance as input size grows.

Question and Answer Bank

VERY SHORT ANSWERS
Multiple Choice Questions MCQs
1. What is sorting?
(a) Removing elements from a list
(b) Arranging elements in a particular order
(c) Searching for an element in a list
(d) Merging two lists
Answer:
(b) Arranging elements in a particular order
Ref: Section 5.1
2. Which of the following is a real-world example of sorting?
(a) Finding a word in an unsorted dictionary
(b) Arranging words in a dictionary alphabetically
(c) Deleting duplicate entries
(d) Counting the number of elements
Answer:
(b) Arranging words in a dictionary alphabetically
Ref: Section 5.1
3. In Bubble Sort, each full iteration through the list is called a ______.
(a) cycle
(b) pass
(c) round
(d) turn
Answer:
(b) pass
Ref: Section 5.2
4. For a list of n elements, how many passes does Bubble Sort make in the worst case?
(a) n
(b) n-1
(c) n+1

Primus PU College, Bangalore 560 035 6

January 2, 2026 PUC COMPUTER SCIENCE STUDY MATERIAL

(d) n/2
Answer:
(b) n-1
Ref: Section 5.2
5. In Bubble Sort, after each pass, the largest element moves to the ______.
(a) beginning
(b) middle
(c) end
(d) random position
Answer:
(c) end
Ref: Section 5.2
6. What is the time complexity of Bubble Sort?
(a) O(1)
(b) O(n)
(c) O(n2 )
(d) O(log n)
Answer:
(c) O(n2 )
Ref: Section 5.5
7. Selection Sort divides the list into ______ parts.
(a) two
(b) three
(c) four
(d) five
Answer:
(a) two
Ref: Section 5.3
8. In Selection Sort, the left part contains ______ elements.
(a) unsorted
(b) sorted
(c) random
(d) duplicate
Answer:
(b) sorted
Ref: Section 5.3
9. How many passes does Selection Sort make for n elements?
(a) n
(b) n-1
(c) n+1

7 L R Mohammed Matheen
PUC COMPUTER SCIENCE STUDY MATERIAL January 2, 2026

(d) n/2
Answer:
(b) n-1
Ref: Section 5.3
10. In Selection Sort, the smallest element is swapped with the ______ element of the unsorted list.
(a) rightmost
(b) middle
(c) leftmost
(d) last
Answer:
(c) leftmost
Ref: Section 5.3
11. What is the time complexity of Selection Sort?
(a) O(1)
(b) O(n)
(c) O(n2 )
(d) O(log n)
Answer:
(c) O(n2 )
Ref: Section 5.5
12. Insertion Sort is similar to arranging ______.
(a) books on a shelf
(b) cards in hand
(c) numbers in a lottery
(d) files in a cabinet
Answer:
(b) cards in hand
Ref: Section 5.4
13. In Insertion Sort, the list is divided into ______ parts.
(a) two
(b) three
(c) four
(d) five
Answer:
(a) two
Ref: Section 5.4
14. In Insertion Sort, the sorted list is traversed from the ______ to find the insertion point.
(a) beginning
(b) middle
(c) end

Primus PU College, Bangalore 560 035 8

January 2, 2026 PUC COMPUTER SCIENCE STUDY MATERIAL

(d) random position

Answer:
(c) end
Ref: Section 5.4
15. What is the time complexity of Insertion Sort?
(a) O(1)
(b) O(n)
(c) O(n2 )
(d) O(log n)
Answer:
(c) O(n2 )
Ref: Section 5.5
16. An algorithm with no loops has a time complexity of ______.
(a) O(1)
(b) O(n)
(c) O(n2 )
(d) O(log n)
Answer:
(a) O(1)
Ref: Section 5.5
17. An algorithm with a single loop has a time complexity of ______.
(a) O(1)
(b) O(n)
(c) O(n2 )
(d) O(log n)
Answer:
(b) O(n)
Ref: Section 5.5
18. An algorithm with nested loops has a time complexity of ______.
(a) O(1)
(b) O(n)
(c) O(n2 )
(d) O(log n)
Answer:
(c) O(n2 )
Ref: Section 5.5
19. Which sorting technique is known for “bubbling up” the largest element?
(a) Selection Sort
(b) Insertion Sort
(c) Bubble Sort

9 L R Mohammed Matheen
PUC COMPUTER SCIENCE STUDY MATERIAL January 2, 2026

(d) Merge Sort

Answer:
(c) Bubble Sort
Ref: Section 5.2
20. Which sorting technique selects the smallest element and swaps it?
(a) Bubble Sort
(b) Insertion Sort
(c) Selection Sort
(d) Quick Sort
Answer:
(c) Selection Sort
Ref: Section 5.3
21. Which sorting technique inserts an element into its correct position by shifting?
(a) Bubble Sort
(b) Selection Sort
(c) Insertion Sort
(d) Heap Sort
Answer:
(c) Insertion Sort
Ref: Section 5.4
22. Sorting a list in ascending order means arranging elements from ______.
(a) largest to smallest
(b) smallest to largest
(c) random order
(d) middle to ends
Answer:
(b) smallest to largest
Ref: Section 5.1
23. Sorting a list in descending order means arranging elements from ______.
(a) largest to smallest
(b) smallest to largest
(c) random order
(d) middle to ends
Answer:
(a) largest to smallest
Ref: Section 5.1
24. In Bubble Sort, if no swapping occurs in a pass, it means ______.
(a) list is empty
(b) list is sorted
(c) list is reversed

Primus PU College, Bangalore 560 035 10

January 2, 2026 PUC COMPUTER SCIENCE STUDY MATERIAL

(d) error occurred

Answer:
(b) list is sorted
Ref: Section 5.2
25. The process of finding how an algorithm performs as input grows is called ______.
(a) sorting
(b) searching
(c) complexity analysis
(d) optimization
Answer:
(c) complexity analysis
Ref: Section 5.5
26. Which sorting method is efficient for nearly sorted lists?
(a) Bubble Sort
(b) Selection Sort
(c) Insertion Sort
(d) All of the above
Answer:
(c) Insertion Sort
Ref: Section 5.4
27. In Selection Sort, after each pass, the size of the unsorted list ______.
(a) increases
(b) decreases
(c) remains same
(d) doubles
Answer:
(b) decreases
Ref: Section 5.3
28. In Insertion Sort, the element to be inserted is stored in a ______ variable.
(a) constant
(b) temporary
(c) global
(d) static
Answer:
(b) temporary
Ref: Section 5.4
29. Which sorting algorithm makes the minimum number of writes to memory?
(a) Bubble Sort
(b) Selection Sort
(c) Insertion Sort

11 L R Mohammed Matheen
PUC COMPUTER SCIENCE STUDY MATERIAL January 2, 2026

(d) All are equal

Answer:
(b) Selection Sort
Ref: Section 5.3
30. The number of swaps in Bubble Sort is ______ compared to Selection Sort.
(a) less
(b) more
(c) equal
(d) unpredictable
Answer:
(b) more
Ref: Section 5.2 & 5.3
31. Assertion (A): Bubble Sort has a time complexity of O(n2 ).
Reason (R): Bubble Sort uses nested loops to compare and swap adjacent elements.
(a) Both A and R are true and R is the correct explanation of A
(b) Both A and R are true but R is not the correct explanation of A
(c) A is true but R is false
(d) A is false but R is true
Answer:
(a) Both A and R are true and R is the correct explanation of A
Ref: Section 5.5
32. Assertion (A): Selection Sort is not adaptive.
Reason (R): Selection Sort always performs the same number of comparisons regardless of input order.
(a) Both A and R are true and R is the correct explanation of A
(b) Both A and R are true but R is not the correct explanation of A
(c) A is true but R is false
(d) A is false but R is true
Answer:
(a) Both A and R are true and R is the correct explanation of A
Ref: Section 5.3
33. Assertion (A): Insertion Sort is similar to arranging cards in hand.
Reason (R): In Insertion Sort, each new element is placed at its correct position by shifting others.
(a) Both A and R are true and R is the correct explanation of A
(b) Both A and R are true but R is not the correct explanation of A
(c) A is true but R is false
(d) A is false but R is true
Answer:
(a) Both A and R are true and R is the correct explanation of A
Ref: Section 5.4
34. Assertion (A): Sorting reduces the time required for searching.
Reason (R): A sorted list allows for efficient searching algorithms like binary search.
(a) Both A and R are true and R is the correct explanation of A

Primus PU College, Bangalore 560 035 12

January 2, 2026 PUC COMPUTER SCIENCE STUDY MATERIAL

(b) Both A and R are true but R is not the correct explanation of A
(c) A is true but R is false
(d) A is false but R is true
Answer:
(a) Both A and R are true and R is the correct explanation of A
Ref: Section 5.1
35. Which of the following is NOT a sorting algorithm discussed in the chapter?
(a) Bubble Sort
(b) Selection Sort
(c) Insertion Sort
(d) Quick Sort
Answer:
(d) Quick Sort
Ref: Chapter 5
36. In Bubble Sort, after the first pass, the largest element is at ______.
(a) position 0
(b) position n-1
(c) position n/2
(d) random position
Answer:
(b) position n-1
Ref: Section 5.2
37. In Selection Sort, the flag variable is used to ______.
(a) count passes
(b) check if swap is needed
(c) store temporary value
(d) terminate loop
Answer:
(b) check if swap is needed
Ref: Algorithm 5.2
38. In Insertion Sort, the while loop condition checks if ______.
(a) j > 0
(b) j >= 0 and temp < list[j]
(c) j < n
(d) temp > list[j]
Answer:
(b) j >= 0 and temp < list[j]
Ref: Algorithm 5.3
39. The term “overhead” in sorting refers to ______.
(a) extra time taken

13 L R Mohammed Matheen
PUC COMPUTER SCIENCE STUDY MATERIAL January 2, 2026

(b) memory used

(c) number of swaps
(d) input size
Answer:
(a) extra time taken
Ref: Section 5.1
40. Which sorting algorithm is described as the simplest?
(a) Selection Sort
(b) Insertion Sort
(c) Bubble Sort
(d) All are equally simple
Answer:
(c) Bubble Sort
Ref: Section 5.2
41. For a list already sorted in ascending order, which sorting algorithm will make the least comparisons?
(a) Bubble Sort
(b) Selection Sort
(c) Insertion Sort
(d) All make equal comparisons
Answer:
(c) Insertion Sort
Ref: Section 5.4
42. The number of passes in Insertion Sort for n elements is ______.
(a) n
(b) n-1
(c) n+1
(d) log n
Answer:
(b) n-1
Ref: Section 5.4
43. In Bubble Sort, the inner loop runs from 0 to ______.
(a) n
(b) n-i
(c) n-i-1
(d) i
Answer:
(c) n-i-1
Ref: Algorithm 5.1
44. In Selection Sort, the inner loop finds the ______ element.
(a) largest

Primus PU College, Bangalore 560 035 14

January 2, 2026 PUC COMPUTER SCIENCE STUDY MATERIAL

(b) smallest
(c) middle
(d) first
Answer:
(b) smallest
Ref: Algorithm 5.2
45. In Insertion Sort, the variable temp holds the ______.
(a) current element to be inserted
(b) previous element
(c) next element
(d) sorted element
Answer:
(a) current element to be inserted
Ref: Algorithm 5.3
46. Which sorting algorithm is most suitable for sorting a list as elements are received one by one?
(a) Bubble Sort
(b) Selection Sort
(c) Insertion Sort
(d) None
Answer:
(c) Insertion Sort
Ref: Section 5.4
47. The time complexity of an algorithm with a single loop is ______.
(a) constant
(b) linear
(c) quadratic
(d) logarithmic
Answer:
(b) linear
Ref: Section 5.5
48. Which sorting algorithm is also known as “sinking sort”?
(a) Bubble Sort
(b) Selection Sort
(c) Insertion Sort
(d) Heap Sort
Answer:
(a) Bubble Sort
Ref: Section 5.2
49. In Selection Sort, after each pass, the sorted list size ______.
(a) increases by 1

15 L R Mohammed Matheen
PUC COMPUTER SCIENCE STUDY MATERIAL January 2, 2026

(b) decreases by 1
(c) remains same
(d) doubles
Answer:
(a) increases by 1
Ref: Section 5.3
50. Which sorting algorithm uses the concept of “shifting” instead of “swapping”?
(a) Bubble Sort
(b) Selection Sort
(c) Insertion Sort
(d) Both (b) and (c)
Answer:
(c) Insertion Sort
Ref: Section 5.4

Fill in the Blanks

1. Sorting is the process of arranging elements in a particular ______.
Answer:
order
Ref: Section 5.1
2. In ______ sort, adjacent elements are compared and swapped if they are in the wrong order.
Answer:
Bubble
Ref: Section 5.2
3. Each full iteration in Bubble Sort is called a ______.
Answer:
pass
Ref: Section 5.2
4. For a list of n elements, Bubble Sort makes ______ passes.
Answer:
n-1
Ref: Section 5.2
5. In Bubble Sort, if no swapping occurs in a pass, the list is already ______.
Answer:
sorted
Ref: Section 5.2
6. Selection Sort divides the list into ______ and unsorted parts.
Answer:
sorted
Ref: Section 5.3
7. In Selection Sort, the smallest element is swapped with the ______ element of the unsorted list.

Primus PU College, Bangalore 560 035 16

January 2, 2026 PUC COMPUTER SCIENCE STUDY MATERIAL

Answer:
leftmost
Ref: Section 5.3
8. Insertion Sort is similar to arranging ______ in hand.
Answer:
cards
Ref: Section 5.4
9. In Insertion Sort, the sorted list is traversed from the ______ to find the insertion point.
Answer:
end
Ref: Section 5.4
10. The time complexity of Bubble Sort is ______.
Answer:
O(n2 )
Ref: Section 5.5
11. An algorithm with no loops has ______ time complexity.
Answer:
constant or O(1)
Ref: Section 5.5
12. An algorithm with nested loops has ______ time complexity.
Answer:
quadratic or O(n2 )
Ref: Section 5.5
13. The amount of time an algorithm takes is called its ______ complexity.
Answer:
time
Ref: Section 5.5
14. Sorting a list in ______ order means from smallest to largest.
Answer:
ascending
Ref: Section 5.1
15. In Selection Sort, the flag variable indicates whether a ______ was found.
Answer:
smaller element
Ref: Algorithm 5.2
16. In Insertion Sort, the element to be inserted is stored in a ______ variable.
Answer:
temporary or temp
Ref: Algorithm 5.3
17. The extra time taken for sorting is called ______.

17 L R Mohammed Matheen
PUC COMPUTER SCIENCE STUDY MATERIAL January 2, 2026

Answer:
overhead
Ref: Section 5.1
18. ______ analysis helps in comparing different algorithms.
Answer:
Complexity
Ref: Section 5.5
19. In Bubble Sort, the largest element “______” up to its correct position.
Answer:
bubbles
Ref: Section 5.2
20. Selection Sort makes ______ number of swaps compared to Bubble Sort.
Answer:
fewer
Ref: Section 5.2 & 5.3
21. Insertion Sort is efficient for ______ sized lists.
Answer:
small or nearly sorted
Ref: Section 5.4
22. The process of finding the median requires the list to be ______.
Answer:
sorted
Ref: Exercise Q4
23. Percentile is a measure of ______ performance.
Answer:
relative
Ref: Exercise Q5
24. If a candidate’s score is in the 90th percentile, it means they scored better than ______% of candidates.
Answer:
90
Ref: Exercise Q5
25. In ______ sort, elements are shifted to make space for insertion.
Answer:
Insertion
Ref: Section 5.4

DESCRIPTIVE QUESTIONS
2 Marks Questions
1. Define sorting. Give one real-world example.
Answer:

Primus PU College, Bangalore 560 035 18

January 2, 2026 PUC COMPUTER SCIENCE STUDY MATERIAL

Sorting is the process of arranging a collection of elements in a particular order, such as ascending or descending.
Example: Words in a dictionary are arranged in alphabetical order.
Ref: Section 5.1
2. What is a pass in Bubble Sort?
Answer:
A pass in Bubble Sort is one complete iteration through the list where adjacent elements are compared and swapped if
they are in the wrong order.
Ref: Section 5.2
3. How many passes are required in Bubble Sort for n elements?
Answer:
Bubble Sort requires n-1 passes to sort a list of n elements.
Ref: Section 5.2
4. How does Selection Sort divide the list?
Answer:
Selection Sort divides the list into two parts: the sorted part (left) and the unsorted part (right). Initially, the sorted part is
empty.
Ref: Section 5.3
5. What is the role of the flag variable in Selection Sort?
Answer:
The flag variable in Selection Sort is used to indicate whether a smaller element than the current minimum was found
during the pass. If yes, a swap is performed.
Ref: Algorithm 5.2
6. How is Insertion Sort similar to arranging cards?
Answer:
In Insertion Sort, each new element is taken from the unsorted list and inserted into its correct position in the sorted list
by shifting other elements, similar to arranging a hand of cards.
Ref: Section 5.4
7. What is time complexity?
Answer:
Time complexity is the amount of time an algorithm takes to run as a function of the size of the input. It helps in analyzing
algorithm efficiency.
Ref: Section 5.5
8. State the time complexity of Bubble Sort, Selection Sort, and Insertion Sort.
Answer:
All three sorting algorithms—Bubble Sort, Selection Sort, and Insertion Sort—have a time complexity of O(n2 ).
Ref: Section 5.5
9. Why is sorting important in computing?
Answer:
Sorting makes searching faster and more efficient. It organizes data so that operations like searching, merging, and ana-
lyzing become easier and quicker.
Ref: Section 5.1
10. What is meant by “overhead” in sorting?
Answer:

19 L R Mohammed Matheen
PUC COMPUTER SCIENCE STUDY MATERIAL January 2, 2026

Overhead refers to the extra time taken to sort a list. This time is considered worthwhile compared to the time needed to
search an unsorted list.
Ref: Section 5.1
11. Differentiate between ascending and descending order.
Answer:
Ascending order arranges elements from smallest to largest.
Descending order arranges elements from largest to smallest.
Ref: Section 5.1
12. How can Bubble Sort be optimized?
Answer:
Bubble Sort can be optimized by stopping early if no swaps occur in a pass, indicating that the list is already sorted.
Ref: Section 5.2
13. In Insertion Sort, how is the correct insertion point found?
Answer:
The sorted list is traversed from the end backwards until the correct position for the new element is found by comparing
with each element.
Ref: Section 5.4
14. What is a constant time algorithm?
Answer:
A constant time algorithm has a time complexity of O(1), meaning its execution time does not change with the size of the
input.
Ref: Section 5.5
15. What is a linear time algorithm?
Answer:
A linear time algorithm has a time complexity of O(n), meaning its execution time increases linearly with the size of the
input.
Ref: Section 5.5

3 Marks Questions
1. Explain Bubble Sort with an example of a list of 5 numbers.
Answer:
Bubble Sort repeatedly compares adjacent elements and swaps them if they are in the wrong order. For example, sorting
[5, 3, 8, 1, 2] in ascending order:
Pass 1: Compare 5 and 3 → swap → [3,5,8,1,2]; Compare 5 and 8 → no swap; Compare 8 and 1 → swap → [3,5,1,8,2];
Compare 8 and 2 → swap → [3,5,1,2,8]
Pass 2: [3,1,5,2,8]
Pass 3: [1,3,2,5,8]
Pass 4: [1,2,3,5,8] → sorted
Ref: Section 5.2
2. Describe the steps of Selection Sort algorithm.
Answer:
1. Divide the list into sorted (left) and unsorted (right) parts.
2. Find the smallest element in the unsorted part.
3. Swap it with the leftmost element of the unsorted part.
4. Move the boundary between sorted and unsorted one element to the right.

Primus PU College, Bangalore 560 035 20

January 2, 2026 PUC COMPUTER SCIENCE STUDY MATERIAL

5. Repeat until the entire list is sorted.

Ref: Section 5.3
3. How does Insertion Sort work? Illustrate with a small example.
Answer:
Insertion Sort builds the sorted list one element at a time by taking an element from the unsorted part and inserting it into
its correct position in the sorted part by shifting elements.
Example: Sorting [4, 3, 2, 10, 12]
Pass 1: Sorted [4], unsorted [3,2,10,12]; insert 3 → [3,4]
Pass 2: Insert 2 → [2,3,4]
Pass 3: Insert 10 → [2,3,4,10]
Pass 4: Insert 12 → [2,3,4,10,12]
Ref: Section 5.4
4. Compare Bubble Sort and Selection Sort in terms of swaps and comparisons.
Answer:

Aspect Bubble Sort Selection Sort

2
Comparisons O(n ) always O(n2 ) always
Swaps Many swaps possible Fewer swaps (only n-1)
Adaptiveness Can stop early if sorted Not adaptive

Ref: Sections 5.2 & 5.3

5. Why is time complexity analysis important?
Answer:
Time complexity analysis helps in:
1. Predicting how an algorithm will perform as input size grows.
2. Comparing different algorithms for efficiency.
3. Choosing the best algorithm for a given problem and data size.
Ref: Section 5.5
6. Differentiate between linear and quadratic time complexity.
Answer:

Linear Time O(n) Quadratic Time O(n2 )

Execution time increases linearly Execution time increases quadratically
Example: single loop Example: nested loops
Efficient for large n Less efficient for large n

Ref: Section 5.5

7. Explain the concept of “pass” in sorting algorithms.
Answer:
A pass is one complete traversal through the list during sorting.
• In Bubble Sort: each pass compares adjacent elements.
• In Selection Sort: each pass selects the smallest element.
• In Insertion Sort: each pass inserts one element into the sorted list.

21 L R Mohammed Matheen
PUC COMPUTER SCIENCE STUDY MATERIAL January 2, 2026

Ref: Sections 5.2, 5.3, 5.4

8. What is meant by an adaptive sorting algorithm? Give an example.
Answer:
An adaptive sorting algorithm performs better when the input list is partially or fully sorted.
Example: Insertion Sort is adaptive because it reduces the number of comparisons and shifts if the list is nearly sorted.
Ref: Section 5.4
9. How can you calculate the xth percentile of a dataset?
Answer:
Steps:
1. Sort the data in ascending order.
2. Calculate index = (x/100) * n, where n is the number of values.
3. Round the index to the nearest whole number.
4. The value at that index in the sorted list is the xth percentile.
Ref: Exercise Q5
10. Write the algorithm for Insertion Sort.
Answer:
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
Step 9: SET i=i+1

Ref: Algorithm 5.3

5 Marks Questions
1. Explain Bubble Sort in detail with a suitable example. Also write its Python implementation.
Answer:
Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps
them if they are in the wrong order. The process is repeated until the list is sorted.
Example: Sorting [8, 7, 13, 1, -9, 4]
Pass 1: [7,8,13,1,-9,4] → [7,8,1,13,-9,4] → [7,8,1,-9,13,4] → [7,8,1,-9,4,13]
Pass 2: [7,1,8,-9,4,13] → [7,1,-9,8,4,13] → [7,1,-9,4,8,13]
Pass 3: [1,7,-9,4,8,13] → [1,-9,7,4,8,13] → [1,-9,4,7,8,13]
Pass 4: [-9,1,4,7,8,13] → sorted
Python Implementation:
def bubble_Sort(list1):
n = len(list1)
for i in range(n):
for j in range(0, n-i-1):
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)

Primus PU College, Bangalore 560 035 22

January 2, 2026 PUC COMPUTER SCIENCE STUDY MATERIAL

Ref: Section 5.2 & Program 5-1

2. Describe Selection Sort algorithm with example. Write its Python code.
Answer:
Selection Sort divides the list into sorted and unsorted parts. In each pass, it selects the smallest element from the unsorted
part and swaps it with the leftmost unsorted element.
Example: Sorting [8, 7, 13, 1, -9, 4]
Pass 1: Smallest = -9 at index 4 → swap with 8 → [-9,7,13,1,8,4]
Pass 2: Smallest = 1 at index 3 → swap with 7 → [-9,1,13,7,8,4]
Pass 3: Smallest = 4 at index 5 → swap with 13 → [-9,1,4,7,8,13]
Pass 4: Smallest = 7 at index 3 → already in place
Pass 5: Smallest = 8 at index 4 → already in place → sorted
Python Implementation:
def selection_Sort(list2):
n = len(list2)
for i in range(n):
min_idx = i
for j in range(i+1, n):
if list2[j] < list2[min_idx]:
min_idx = j
list2[i], list2[min_idx] = list2[min_idx], list2[i]
numList = [8, 7, 13, 1, -9, 4]
selection_Sort(numList)
print(numList)

Ref: Section 5.3 & Program 5-2

3. Explain Insertion Sort with an example. Provide its Python implementation.
Answer:
Insertion Sort builds the sorted list one element at a time by inserting each unsorted element into its correct position in
the sorted part by shifting elements.
Example: Sorting [8, 7, 13, 1, -9, 4]
Pass 1: Sorted [8], unsorted [7,13,1,-9,4] → insert 7 → [7,8]
Pass 2: Insert 13 → [7,8,13]
Pass 3: Insert 1 → [1,7,8,13]
Pass 4: Insert -9 → [-9,1,7,8,13]
Pass 5: Insert 4 → [-9,1,4,7,8,13]
Python Implementation:
def insertion_Sort(list3):
n = len(list3)
for i in range(1, n):
temp = list3[i]
j = i-1
while j >= 0 and temp < list3[j]:
list3[j+1] = list3[j]
j -= 1
list3[j+1] = temp
numList = [8, 7, 13, 1, -9, 4]
insertion_Sort(numList)
print(numList)

Ref: Section 5.4 & Program 5-3

4. Compare Bubble Sort, Selection Sort, and Insertion Sort in a tabular form.
Answer:

Feature Bubble Sort Selection Sort Insertion Sort

Method Adjacent compare & swap Select smallest & swap Insert in sorted position

23 L R Mohammed Matheen
PUC COMPUTER SCIENCE STUDY MATERIAL January 2, 2026

Feature Bubble Sort Selection Sort Insertion Sort

Passes n-1 n-1 n-1
Time O(n2 ) O(n2 ) O(n2 )
Complexity
Swaps Many Few (n-1) Varies (shifts)
Adaptiveness Yes (can stop early) No Yes
Best for Small lists, educational When swaps costly Small/nearly sorted lists
Stability Stable Unstable Stable

Ref: Sections 5.2, 5.3, 5.4

5. What is time complexity? Explain with examples of constant, linear, and quadratic time.
Answer:
Time complexity measures how the runtime of an algorithm grows with the input size.
• Constant time O(1): Runtime does not change with input size. Example: Accessing an array element by index.
• Linear time O(n): Runtime increases linearly with input size. Example: Traversing a list with a single loop.
• Quadratic time O(n2 ): Runtime increases quadratically with input size. Example: Nested loops as in Bubble Sort.
Ref: Section 5.5
6. Apply Bubble Sort step by step on the list: [63, 42, 21, 9]. Show each pass.
Answer:
List: [63, 42, 21, 9]
Pass 1:
Compare 63 and 42 → swap → [42,63,21,9]
Compare 63 and 21 → swap → [42,21,63,9]
Compare 63 and 9 → swap → [42,21,9,63]
Pass 2:
Compare 42 and 21 → swap → [21,42,9,63]
Compare 42 and 9 → swap → [21,9,42,63]
Compare 42 and 63 → no swap
Pass 3:
Compare 21 and 9 → swap → [9,21,42,63]
Compare 21 and 42 → no swap
Sorted list: [9, 21, 42, 63]
Ref: Section 5.2
7. Apply Selection Sort step by step on the list: [7, 11, 3, 10, 17]. Show each pass.
Answer:
List: [7, 11, 3, 10, 17]
Pass 1: Smallest = 3 at index 2 → swap with 7 → [3,11,7,10,17]
Pass 2: Smallest = 7 at index 2 → swap with 11 → [3,7,11,10,17]
Pass 3: Smallest = 10 at index 3 → swap with 11 → [3,7,10,11,17]
Pass 4: Smallest = 11 at index 3 → already in place → [3,7,10,11,17]
Sorted list: [3, 7, 10, 11, 17]
Ref: Section 5.3
8. Apply Insertion Sort step by step on the list: [12, 11, 13, 5, 6]. Show each pass.
Answer:
List: [12, 11, 13, 5, 6]
Pass 1: Sorted [12], insert 11 → [11,12]
Pass 2: Insert 13 → [11,12,13]
Pass 3: Insert 5 → [5,11,12,13]
Pass 4: Insert 6 → [5,6,11,12,13]
Sorted list: [5, 6, 11, 12, 13]

Primus PU College, Bangalore 560 035 24

January 2, 2026 PUC COMPUTER SCIENCE STUDY MATERIAL

Ref: Section 5.4

9. Write a Python program to find the median of a list of numbers using Bubble Sort.
Answer:
def bubble_Sort(list1):
n = len(list1)
for i in range(n):
for j in range(0, n-i-1):
if list1[j] > list1[j+1]:
list1[j], list1[j+1] = list1[j+1], list1[j]

def find_median(num_list):
bubble_Sort(num_list)
n = len(num_list)
if n % 2 == 1: # odd
median = num_list[n//2]
else: # even
median = (num_list[n//2 - 1] + num_list[n//2]) / 2
return median

# Example
numbers = [7, 11, 3, 10, 17]
print("Median:", find_median(numbers))

Ref: Exercise Q4
10. Explain how to calculate the 90th percentile for a list of marks using Selection Sort.
Answer:
Steps:
1. Sort the list of marks in ascending order using Selection Sort.
2. Calculate index = (90/100) * n, where n is number of students.
3. Round the index to the nearest whole number using round().
4. The mark at that index in the sorted list is the 90th percentile.
Example: For 120 students, index = 0.90 * 120 = 108 → round(108) = 108. The 108th mark in sorted order is the
90th percentile.
Ref: Exercise Q5

Chapter End Exercise Solutions

1. Consider a list of 10 elements: numList = [7,11,3,10,17,23,1,4,21,5]. Display the partially sorted list after three
complete passes of Bubble sort.
Answer:
After three passes of Bubble Sort:
Pass 1: [7,3,10,11,17,1,4,21,5,23]
Pass 2: [3,7,10,11,1,4,17,5,21,23]
Pass 3: [3,7,10,1,4,11,5,17,21,23]
Ref: Section 5.2
2. Identify the number of swaps required for sorting the following list using selection sort and bubble sort and
identify which is the better sorting technique with respect to the number of comparisons. List 1: [63, 42, 21, 9]
Answer:
Bubble Sort swaps:
Pass 1: 3 swaps (63�42, 63�21, 63�9)
Pass 2: 2 swaps (42�21, 42�9)

25 L R Mohammed Matheen
PUC COMPUTER SCIENCE STUDY MATERIAL January 2, 2026

Pass 3: 1 swap (21�9)

Total swaps = 6
Selection Sort swaps:
Pass 1: 1 swap (63�9)
Pass 2: 1 swap (42�21)
Pass 3: 0 swaps
Total swaps = 2
Both make the same number of comparisons (O(n2 )), but Selection Sort is better with respect to number of swaps.
Ref: Sections 5.2 & 5.3
3. Consider the following lists: List 1: [2,3,5,7,11] List 2: [11,7,5,3,2]. If the lists are sorted using Insertion sort
then which of the lists List1 or List 2 will make the minimum number of comparisons? Justify using diagrammatic
representation.
Answer:
List 1 is already sorted in ascending order. Insertion Sort on an already sorted list makes only n-1 comparisons (no shifts
needed).
List 2 is in descending order. Insertion Sort on a reverse-sorted list makes the maximum comparisons: 1+2+3+…+(n-1)
= O(n2 ).
Therefore, List 1 will make the minimum number of comparisons.
Ref: Section 5.4
4. Write a program using user defined functions that accepts a List of numbers as an argument and finds its median.
(Hint: Use bubble sort to sort the accepted list. If there are odd number of terms, the median is the center term.
If there are even number of terms, add the two middle terms and divide by 2 get median)
Answer:
def bubble_Sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]

def find_median(num_list):
bubble_Sort(num_list)
n = len(num_list)
if n % 2 == 1:
return num_list[n//2]
else:
return (num_list[n//2 - 1] + num_list[n//2]) / 2

# Example usage
numbers = [7, 11, 3, 10, 17]
print("Median:", find_median(numbers))

Ref: Exercise Q4
5. All the branches of XYZ school conducted an aptitude test for all the students in the age group 14 - 16. There were
a total of n students. The marks of n students are stored in a list. Write a program using a user defined function
that accepts a list of marks as an argument and calculates the ‘x’ percentile (where x is any number between 0 and
100).
Answer:
def selection_Sort(arr):
n = len(arr)
for i in range(n):
min_idx = i
for j in range(i+1, n):
if arr[j] < arr[min_idx]:

Primus PU College, Bangalore 560 035 26

January 2, 2026 PUC COMPUTER SCIENCE STUDY MATERIAL

min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]

def calculate_percentile(marks, x):

selection_Sort(marks)
n = len(marks)
index = round((x/100) * n)
if index >= n:
index = n-1
elif index < 0:
index = 0
return marks[index]

# Example usage
marks = [85, 92, 78, 90, 88, 76, 95, 89, 84, 91]
x = 90
print(f"{x}th percentile:", calculate_percentile(marks, x))

Ref: Exercise Q5
6. During admission in a course, the names of the students are inserted in ascending order. Thus, performing the
sorting operation at the time of inserting elements in a list. Identify the type of sorting technique being used and
write a program using a user defined function that is invoked every time a name is input and stores the name in
ascending order of names in the list.
Answer:
The technique being used is Insertion Sort, because each new element (name) is inserted into its correct position in the
already sorted list.
def insert_sorted(name_list, new_name):
name_list.append(new_name)
# Insertion Sort logic for one element
i = len(name_list) - 1
while i > 0 and name_list[i] < name_list[i-1]:
name_list[i], name_list[i-1] = name_list[i-1], name_list[i]
i -= 1

# Example usage
students = []
while True:
name = input("Enter student name (or 'stop' to end): ")
if [Link]() == 'stop':
break
insert_sorted(students, name)
print("Current list:", students)

Ref: Exercise Q6 & Section 5.4

27 L R Mohammed Matheen