Sorting Class 12 Notes: Bubble, Selection and Insertion Sort

Welcome to the Sorting Class 12 Notes for Computer Science, prepared for the 2026-27 session. This chapter (Chapter 5) introduces three classic sorting algorithms — Bubble Sort, Selection Sort, and Insertion Sort — and explains why ordered data is so much easier to work with.

On this page, you’ll get clear algorithm definitions, pass-by-pass traces on fresh lists, the n² time complexity logic for all three methods, and exam-ready revision tables.

What Sorting Does and Why It’s Worth the Overhead

Sorting is the process of arranging a given collection of elements in a particular order. Numbers can be arranged in ascending (increasing) or descending (decreasing) order; strings (words) can be arranged alphabetically (a-z or z-a) or by their length. The most familiar everyday example is a dictionary — words are sorted alphabetically so you can locate a word quickly.

Similarly, seats in an examination hall are often ordered by candidates’ roll numbers, and student lists can be sorted by height or weight (NCERT, p. 67).

Why does this matter in computing? Imagine finding a word’s meaning in a dictionary that is not ordered. You would have to flip through every page until you found the word — very tedious. Ordered data makes searching dramatically faster. The trade-off is the time spent sorting in the first place: this is the overhead.

For a large list, sorting takes substantial time, but that overhead is worth it compared to the time needed to find an element in an unsorted list (NCERT, p. 68).

In everyday life, the same idea powers price filters on shopping websites and leaderboards in games — both are built on the sorted data. For example, when you filter products by “price: low to high,” a sorting algorithm quickly rearranges the catalogue by price, so your search results are ready in seconds.

This is a real-world application that the NCERT textbook does not mention, but it helps you connect the concept to familiar situations.

Sorting Vocabulary You Need First

Before diving into the algorithms, get comfortable with the key terms used throughout this chapter. The table below defines each one with a simple example.

Bubble Sort: Swap Neighbours Until the Largest Bubbles Up

Bubble sort is the simplest sorting method. It works by repeatedly comparing adjacent elements and swapping them if they are out of order (NCERT, p. 68). The algorithm repeats this for a total of \(n-1\) passes on a list of \(n\) elements.

In each pass, the largest remaining element “bubbles up” to its correct position at the end of the list, so it is excluded from later passes. This is why it is called bubble sort (NCERT, p. 68).

• Pass definition: A pass is one complete trip through the list, comparing each required pair of adjacent elements (NCERT, p. 68).
• Pass count: A list with \(n\) elements needs \(n-1\) passes to be fully sorted (NCERT, p. 68).
• Algorithm 5.1 structure: The outer loop sets \(i = 0\) and repeats while \(i \lt n\). Inside, the inner loop starts \(j = 0\) and compares \(numList[j]\) with \(numList[j+1]\), swapping when the first is bigger. The inner loop runs while \(j \lt n-i-1\), so the already-sorted tail is skipped (NCERT, p. 70).
• Program 5-1: The Python code follows the same pattern: the outer \(for\) loop runs \(n\) passes, and the inner \(for\) loop runs from 0 to \(n-i-1\) because the last \(i\) elements are already sorted (NCERT, p. 70).

NCERT Figure 5.1 traces bubble sort on the sample list \(numList = [8, 7, 13, 1, -9, 4]\). In the figure, blue highlights the two elements being compared in each step, and green marks the sorted elements at the end of the list after each pass (NCERT, p. 68).

The list becomes fully sorted in the 4th pass, but the algorithm still makes a redundant 5th pass with no swaps (NCERT, p. 70). This is the key insight behind the early-stop improvement.

Think and Reflect (NCERT, p. 70): If a complete pass performs no swaps, the list must already be sorted. So the algorithm could stop. In our own words: a “no-swap pass” is a free signal that the sorting is done, yet the basic bubble sort ignores it.

A smarter version would check a flag after each pass and break out early if no swap happened.

Selection Sort: Move the Smallest Unsorted Element to the Front

Selection sort is the second technique. The list of \(n\) elements is conceptually split into two parts: the left part contains sorted elements, and the right part contains unsorted elements. Initially, the left part is empty and the right part contains everything (NCERT, p. 71).

• Pass behaviour: In each pass, the smallest element is found in the unsorted part and swapped with the leftmost element of the unsorted part. This places it at the correct position in the sorted part, so it is excluded from later passes. Selection sort makes \(n-1\) passes in total; the \(n\)th element is already in place by then (NCERT, p. 71).
• Algorithm 5.2: It sets \(min = i\) and \(flag = 0\) at the start of each pass. The inner loop scans from \(j = i+1\) to the end; when it finds a smaller element, it updates \(min = j\) and sets \(flag = 1\). After the inner loop, if \(flag = 1\), the elements at positions \(i\) and \(min\) are swapped (NCERT, p. 73). So the swap happens at most once per pass — after finding the minimum.
• Program 5-2: The flag variable decides when to swap. Without it, the program would swap inside the inner loop every time it finds a smaller element, which is inefficient. With it, the swap happens only once per pass, and only if a smaller element was actually found (NCERT, p. 74).

Figure 5.2 shows selection sort working on the sample list \(numList = [8, 7, 13, 1, -9, 4]\). It is read like this: the arrows show the two elements currently being compared; the blue highlight marks the smaller element in that comparison; and the green highlight marks the elements that have already been sorted into their final positions at the front of the list (NCERT, p. 71).

As the passes advance, you can watch the green region grow from the left as each smallest element is locked into place.

Insertion Sort: Shift Larger Elements and Insert the Current One

Insertion sort builds a sorted list by taking each unsorted element one at a time and inserting it into the sorted part at its appropriate position (NCERT, p. 74). Like selection sort, it works on two parts — sorted and unsorted — but the operation is shifting, not swapping.

The sorted part is traversed backward to find where the new element belongs; larger elements are shifted right to make space (NCERT, p. 74).

• Pass behaviour: In pass 1, the sorted list has a single element and the unsorted list has \(n-1\) elements. The first unsorted element is compared with the sorted element and shifted if needed. In later passes, the traversal goes backward from the end of the sorted part until the correct insertion point is found (NCERT, p. 74).
• Algorithm 5.3: It starts with \(i = 1\), stores the current element in a temporary variable \(temp\), and sets \(j = i-1\). The inner loop shifts \(numList[j]\) right while \(j \gt 0\) and \(numList[j] \gt temp\). Then \(temp\) is inserted at \(numList[j+1]\) (NCERT, p. 76).
• Important boundary: The algorithm as written uses \(j \gt 0\), but the textbook’s Python program (Program 5-3) uses \(j >= 0\) so that index 0 is also compared. This is a classic pitfall — we cover it in the Common Mistakes section.
• Playing-card analogy: The textbook summary says insertion sort is similar to placing a card at its right position while playing cards (NCERT, p. 79). Think of holding a sorted hand of cards and sliding a new card into its correct spot — everything larger shifts to the right first.

Time Complexity: Why All Three Sorts Are Quadratic

Time complexity is the amount of time an algorithm takes to process a given set of data (NCERT, p. 77). It matters most with large datasets: for the small examples in this chapter, the time differences are negligible, but for huge real-world lists, the total time becomes significant (NCERT, p. 77). The textbook gives four estimating rules (NCERT, p. 78):

• No loop: time complexity is 1 (constant time), because the number of instructions stays constant regardless of data size.
• One loop: time complexity is n (linear time), because the loop executes its body \(n\) times.
• Nested loop: time complexity is n² (quadratic time).
• Nested loop plus a single loop: the complexity is judged by the nested loop only — the nested loop dominates.

Now look at the three Python programs: bubble sort, selection sort, and insertion sort each contain a nested loop (one loop inside another). According to the rules above, all three therefore have a time complexity of \(n^2\) (NCERT, p. 78).

Formulas and Counts to Remember

This chapter has no heavy mathematical formulas — just countable quantities and complexity classes. The table below collects them all for a quick revision.

Here, \(n\) is the number of elements in the list.

Worked Examples: Pass-by-Pass Traces on Fresh Lists

Each trace below uses a fresh list so you can revise alone and check every step. The list is shown after each complete pass.

Bubble Sort on \([5, 2, 9, 1, 6]\)

Method: In each pass, compare adjacent pairs and swap when the left value is greater than the right value. The largest remaining value settles at the end after each pass.

Note: A 5th pass (redundant) would find no swap and confirm the list is sorted. This is exactly the redundant final pass the Think and Reflect prompt asks about.

Selection Sort on \([29, 10, 14, 37, 13]\)

Method: In each pass, find the smallest element in the unsorted part and swap it with the leftmost unsorted element. The sorted part grows from the left.

Insertion Sort on \([23, 42, 15, 8, 30]\)

Method: Start with the first element as the sorted part. For each next element, shift larger elements in the sorted part to the right, then insert the current element into the gap.

Common Mistakes Students Make in Sorting Traces and Code

Exam Notes: How to Present Sorting Answers

The chapter’s exercise set (NCERT, p. 79) asks three main kinds of questions. Structure your answers as follows:

• Trace questions: Name the sorting method first, then write the list state after each complete pass, labelled clearly (Pass 1, Pass 2, etc.). The exercise often asks for the partially sorted list after a given number of passes, so practising list states matters more than memorising code (NCERT, p. 79).
• Comparison questions: Count comparisons and swaps separately, and justify which technique is better from those counts. For example, a question might ask you to compare bubble sort and selection sort on a specific list (NCERT, p. 79) — walk through both traces and use the numbers as evidence.
• Programming questions: Define a user-defined function that takes a list as an argument, sorts it with the stated method, and then computes the required result from the sorted list. Examples in the exercise include finding the median (Q4, NCERT p. 79) and calculating the \(x\)th percentile (Q5, NCERT p. 80).

For a complete revision of the subject, visit the Class 12 Computer Science notes hub or the Class 12 notes main page. You may also find it useful to review searching notes — the two chapters complement each other — or the queue notes for more data-structure practice.

Chapter 5 in 60 Seconds: Revision Summary

• Purpose of sorting: ordered data makes searching dramatically faster — the sorting overhead is worth it (NCERT, p. 68).
• No-swap early stop: if a pass makes no swaps, the list is already sorted and the algorithm can stop (NCERT, p. 70).
• Complexity rules: no loop → 1 (constant), one loop → \(n\) (linear), nested loop → \(n^2\) (quadratic), and nested loop dominates if both appear (NCERT, p. 78).

FAQs: Sorting Doubts Students Ask

What is the difference between selection sort and insertion sort?

Selection sort finds the smallest element in the unsorted part and swaps it to the front, doing at most one swap per pass. Insertion sort takes the next unsorted element and shifts larger sorted elements to the right to make space, then inserts it in place.

Selection sort works on the whole unsorted remainder each pass; insertion sort works backward through the sorted part and uses shifting rather than swapping (NCERT, pp. 71, 74).

Why does bubble sort make n – 1 passes even if the list gets sorted earlier?

Because the basic bubble sort algorithm has no mechanism to detect that the list is already sorted. After a no-swap pass, the next pass will also be no-swap, but the algorithm keeps going until all \(n-1\) passes are done (NCERT, p. 70). The Think and Reflect hint is to add a check: if a pass completes with zero swaps, stop early.

Why is the time complexity of bubble sort, selection sort and insertion sort all n squared?

All three programs contain a nested loop: one loop runs \(n\) times, and inside it another loop also runs up to \(n\) times. The rule is that a nested loop has time complexity \(n^2\) (NCERT, p. 78). Since each sorting program’s body is dominated by its nested loop, all three get \(n^2\).

Does insertion sort use j greater than 0 or j greater than or equal to 0?

It must use \(j >= 0\) to include index 0 in the comparison. The textbook’s Algorithm 5.3 writes \(j \gt 0\), but the working Python program (Program 5-3) correctly uses \(j >= 0\) (NCERT, pp. 76-77). If you use \(j \gt 0\), the element at index 0 is never compared, so the smallest element can never be shifted to the very front.

This is a classic misconception: the pseudocode says \(\gt 0\), but the code needs \(>=0\).

What should be shown when a question asks for the partially sorted list after three passes?

Show the list state after exactly three complete passes, not after three comparisons or three swaps. Label it clearly, e.g. “After Pass 3: [1, 2, 5, 6, 9].”

The exercise set (NCERT, p. 79) asks for the partially sorted list after a given number of passes, so your trace should end at the required pass and stop there — do not continue to the fully sorted state unless asked.

Reference: NCERT Class 12 Computer Science textbook, chapter Sorting.

Official source: download the NCERT textbook free from ncert.nic.in.