Home › Free notes › Class 12 Computer Science › Sorting

Sorting – Class 12 Computer Science notes, important questions and MCQs

NCERT Class 12 Computer Science, chapter 5. Notes, key terms, important questions with answers and MCQs.

Chapter overview

Sorting is the process of arranging elements in a particular order, ascending or descending. Sorted data makes searching and analysis faster. This chapter covers three simple sorting algorithms: bubble sort, selection sort and insertion sort. Each works in passes and has a time complexity of O(n²) in the worst case, which is analysed by counting comparisons and swaps.

Bubble sort and selection sort

Bubble sort repeatedly compares adjacent elements and swaps them if they are in the wrong order; after each pass, the largest remaining element moves to its correct position at the end. A list of n elements needs at most n − 1 passes, and the process can stop early if no swap occurs in a pass.
Selection sort divides the list into a sorted part and an unsorted part; in each pass it selects the smallest element from the unsorted part and swaps it with the first unsorted element.
Selection sort makes at most n − 1 swaps, while bubble sort may make many swaps.

Insertion sort and complexity

Insertion sort takes elements one by one from the unsorted part and inserts each into its correct position in the sorted part by shifting larger elements to the right, like arranging playing cards in hand.
Time complexity describes how running time grows with input size n; constant O(1), linear O(n), quadratic O(n²); all three algorithms are O(n²) in the worst case, while bubble sort with an early-exit check and insertion sort take O(n) on an already sorted list.
Python's built-in sort() and sorted() use an efficient algorithm (Timsort), but learning simple algorithms helps understand algorithm design.

Key terms

Sorting: arranging elements in a specific order
Bubble sort: repeatedly swapping adjacent elements that are out of order
Selection sort: repeatedly selecting the smallest element and placing it in position
Insertion sort: inserting each element into its correct place in a sorted part
Time complexity: a measure of how running time grows with input size

Important questions with answers

What is time complexity?2 marks

Time complexity is a measure of how the running time of an algorithm increases as the size of the input (n) increases. It is expressed in Big-O notation, such as O(1) for constant time, O(n) for linear time and O(n²) for quadratic time.

Write the Python code for bubble sort.3 marks

def bubble_sort(L): n = len(L); for i in range(n - 1): for j in range(n - 1 - i): if L[j] > L[j + 1]: L[j], L[j + 1] = L[j + 1], L[j]. After each outer pass, the largest remaining element reaches its correct position at the end.

Explain insertion sort with an example and its Python implementation.5 marks

Insertion sort builds a sorted list one element at a time. The list is treated as having a sorted part, initially only the first element, and an unsorted part. Each element from the unsorted part is picked and compared with elements of the sorted part from right to left; larger elements are shifted one position to the right, and the picked element is inserted into the gap. Example: sort [8, 3, 5, 1]. Pass 1: pick 3, shift 8 right, insert 3, giving [3, 8, 5, 1]. Pass 2: pick 5, shift 8 right, 3 is smaller, so insert 5, giving [3, 5, 8, 1]. Pass 3: pick 1, shift 8, 5 and 3 right, insert 1 at the start, giving [1, 3, 5, 8]. Python implementation: def insertion_sort(L): for i in range(1, len(L)): key = L[i]; j = i - 1; while j >= 0 and L[j] > key: L[j + 1] = L[j]; j = j - 1; then L[j + 1] = key. In the worst case, when the list is in reverse order, every element is compared with all previous elements, giving O(n²) time complexity. In the best case, when the list is already sorted, only one comparison is made per element, giving O(n). Insertion sort is efficient for small or nearly sorted lists and is stable, meaning equal elements keep their original order.

Quick revision

Need for sorting.
Bubble sort passes and swaps.
Selection sort and insertion sort.
Time complexity: O(1), O(n), O(n²).

Exam tips

Trace each algorithm on [5, 2, 8, 1] pass by pass.
Remember: all three are O(n²) in the worst case.

Practice MCQs

Arranging elements in ascending or descending order is
1. sorting
2. searching
3. hashing
4. merging only
Show answer
Answer: (a) sorting. It makes searching faster.
The sorting method that compares and swaps adjacent elements is
1. selection sort
2. insertion sort
3. bubble sort
4. binary sort
Show answer
Answer: (c) bubble sort. Larger elements bubble to the end.
In the worst case, bubble sort has time complexity
1. O(1)
2. O(n²)
3. O(log n)
4. O(n)
Show answer
Answer: (b) O(n²). Nested passes over the list.
The sort that repeatedly finds the minimum element and places it at the beginning is
1. bubble sort
2. insertion sort
3. selection sort
4. quick sort
Show answer
Answer: (c) selection sort. It selects the smallest element.
The maximum number of passes bubble sort needs for n elements is
1. n − 1
2. n
3. n + 1
4. 2n
Show answer
Answer: (a) n − 1. The last element is placed automatically.
Arranging playing cards one by one in the correct position resembles
1. selection sort
2. insertion sort
3. bubble sort
4. binary search
Show answer
Answer: (b) insertion sort. Each card is inserted into the sorted part.
After the first pass of bubble sort (ascending) on [5, 1, 4, 2], the list is
1. [1, 4, 2, 5]
2. [1, 5, 4, 2]
3. [1, 2, 4, 5]
4. [5, 4, 2, 1]
Show answer
Answer: (a) [1, 4, 2, 5]. The largest element 5 moves to the end.
After the first pass of selection sort (ascending) on [7, 3, 9, 1], the list is
1. [1, 3, 9, 7]
2. [3, 7, 9, 1]
3. [1, 7, 9, 3]
4. [3, 7, 1, 9]
Show answer
Answer: (a) [1, 3, 9, 7]. 1 is swapped with 7.

All chapters of Class 12 Computer Science

Written by Kundali IQ from standard, well-established facts to help with revision. This is not an official NCERT publication; always read your textbook too.