Chapter 05 - Sorting

CBSE Class 12 Computer Science

5.1 Introduction

What is Sorting?

Sorting is the process of arranging data elements in a particular order:

  • Ascending order (small → large)
  • Descending order (large → small)

Why Sorting is Important?

  • Faster searching
  • Better data organization
  • Efficient processing
  • Easier analysis

Examples

Unsorted list:

[45, 12, 89, 34, 10]

Sorted list (ascending):

[10, 12, 34, 45, 89]

📌 In CBSE Class 12, you must know three sorting techniques:

  1. Bubble Sort
  2. Selection Sort
  3. Insertion Sort

5.2 Bubble Sort

Concept

Bubble sort repeatedly compares adjacent elements and swaps them if they are in the wrong order.

📌 Largest element “bubbles up” to the end after each pass.

Algorithm (Exam Ready)

  1. Repeat for n-1 passes
  2. Compare adjacent elements
  3. Swap if first > second
  4. Continue till list is sorted

Dry Run Example

List:

[5, 1, 4, 2]

Pass 1:

[1, 4, 2, 5]

Pass 2:

[1, 2, 4, 5]

Python Program: Bubble Sort

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

data = [64, 34, 25, 12, 22]
bubble_sort(data)
print("Sorted list:", data)

Optimized Bubble Sort (Extra Knowledge)

def bubble_sort_opt(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break

📌 If no swapping occurs → list already sorted

Characteristics

  • Simple to understand
  • Very slow for large data
  • Mostly used for learning, not real systems

5.3 Selection Sort

Concept

Selection sort repeatedly selects the smallest element from the unsorted portion and places it at the correct position.

📌 Number of swaps is minimum compared to bubble sort.

Algorithm (Exam Ready)

  1. Assume first element is smallest
  2. Compare with remaining elements
  3. Find minimum element
  4. Swap with first position
  5. Repeat for remaining list

Dry Run Example

List:

[64, 25, 12, 22]

Pass 1:

[12, 25, 64, 22]

Pass 2:

[12, 22, 64, 25]

Pass 3:

[12, 22, 25, 64]

Python Program: Selection Sort

def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        min_index = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        arr[i], arr[min_index] = arr[min_index], arr[i]

data = [64, 25, 12, 22, 11]
selection_sort(data)
print("Sorted list:", data)

Characteristics

  • Fewer swaps
  • Still slow for large lists
  • Always takes same number of comparisons

5.4 Insertion Sort

Concept

Insertion sort works like sorting playing cards in hand.

📌 Each element is placed in its correct position in the sorted part.

Algorithm (Exam Ready)

  1. Assume first element is sorted
  2. Take next element
  3. Shift larger elements right
  4. Insert element at correct position
  5. Repeat till end

Dry Run Example

List:

[8, 3, 5, 2]

Steps:

[3, 8, 5, 2]
[3, 5, 8, 2]
[2, 3, 5, 8]

Python Program: Insertion Sort

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

data = [12, 11, 13, 5, 6]
insertion_sort(data)
print("Sorted list:", data)

Characteristics

  • Very efficient for small datasets
  • Fast if list is nearly sorted
  • Used in real systems for small data

5.5 Time Complexity of Algorithms

What is Time Complexity?

Time complexity measures:

How the execution time grows with input size (n)

Best, Average & Worst Case

  • Best case – list already sorted
  • Worst case – list sorted in reverse
  • Average case – random order

Time Complexity Comparison Table (VERY IMPORTANT)

Algorithm Best Case Average Case Worst Case
Bubble Sort O(n) O(n²) O(n²)
Selection Sort O(n²) O(n²) O(n²)
Insertion Sort O(n) O(n²) O(n²)

📌 Most common board question

Which Sorting is Best?

  • Small data → Insertion Sort
  • Nearly sorted → Insertion Sort
  • Learning purpose → Bubble Sort
  • Minimum swaps → Selection Sort

📝 NCERT EXAM SUMMARY (Must Memorize)

  • Sorting arranges data in order
  • Bubble sort → adjacent comparison
  • Selection sort → minimum element selection
  • Insertion sort → insert in sorted part
  • Insertion sort best for small lists
  • Selection sort always O(n²)
  • Bubble sort easiest but slow

Board-Level Solved Programs (10 Programs)

Program 1: Bubble Sort (Ascending Order)

def bubble_sort(a):
    n = len(a)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]

lst = [64, 34, 25, 12, 22]
bubble_sort(lst)
print("Sorted list:", lst)

📌 Concept: Adjacent comparison and swapping

Program 2: Bubble Sort (Descending Order)

def bubble_sort_desc(a):
    n = len(a)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if a[j] < a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]

lst = [5, 1, 4, 2]
bubble_sort_desc(lst)
print(lst)

Program 3: Optimized Bubble Sort

def bubble_sort_opt(a):
    n = len(a)
    for i in range(n):
        swapped = False
        for j in range(n - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                swapped = True
        if not swapped:
            break

lst = [1, 2, 3, 4, 5]
bubble_sort_opt(lst)
print(lst)

📌 Best case O(n)

Program 4: Selection Sort (Ascending)

def selection_sort(a):
    n = len(a)
    for i in range(n - 1):
        min_index = i
        for j in range(i + 1, n):
            if a[j] < a[min_index]:
                min_index = j
        a[i], a[min_index] = a[min_index], a[i]

lst = [64, 25, 12, 22, 11]
selection_sort(lst)
print(lst)

Program 5: Selection Sort (Descending)

def selection_sort_desc(a):
    n = len(a)
    for i in range(n - 1):
        max_index = i
        for j in range(i + 1, n):
            if a[j] > a[max_index]:
                max_index = j
        a[i], a[max_index] = a[max_index], a[i]

lst = [3, 7, 1, 9]
selection_sort_desc(lst)
print(lst)

Program 6: Insertion Sort (Ascending)

def insertion_sort(a):
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and key < a[j]:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key

lst = [12, 11, 13, 5, 6]
insertion_sort(lst)
print(lst)

Program 7: Insertion Sort (Descending)

def insertion_sort_desc(a):
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and key > a[j]:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key

lst = [4, 2, 9, 1]
insertion_sort_desc(lst)
print(lst)

Program 8: Sort Names Alphabetically (Insertion Sort)

names = ["Ravi", "Amit", "Kiran", "Suman"]

for i in range(1, len(names)):
    key = names[i]
    j = i - 1
    while j >= 0 and key < names[j]:
        names[j + 1] = names[j]
        j -= 1
    names[j + 1] = key

print(names)

📌 Frequently asked practical

Program 9: Sort Marks and Display Highest & Lowest

marks = [78, 92, 65, 88, 70]

bubble_sort = lambda a: sorted(a)

sorted_marks = bubble_sort(marks)
print("Sorted:", sorted_marks)
print("Highest:", sorted_marks[-1])
print("Lowest:", sorted_marks[0])

📌 Application-based

Program 10: Count Number of Passes (Bubble Sort)

def bubble_sort_count(a):
    n = len(a)
    passes = 0
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
        passes += 1
    print("Number of passes:", passes)

lst = [5, 4, 3, 2]
bubble_sort_count(lst)
print(lst)

📌 Theory + coding combo question

Case-Study Questions (CBSE 2025 Pattern)

Case Study 1: Student Marks Processing

A school needs to arrange student marks in ascending order to prepare merit lists.

Questions:

  1. Which sorting technique is easiest to implement? ✔ Bubble Sort

  2. Which sorting technique is best if marks are already almost sorted? ✔ Insertion Sort

  3. Write a Python program to sort marks.

    marks = [85, 70, 92, 60]

for i in range(len(marks) - 1):
for j in range(len(marks) - 1 - i):
    if marks[j] > marks[j + 1]:
        marks[j], marks[j + 1] = marks[j + 1], marks[j]

print(marks)

Case Study 2: Library Book Arrangement

Books need to be arranged alphabetically.

Questions:

  1. Which sorting technique is suitable for small datasets? ✔ Insertion Sort

  2. Write a Python program to sort book names.

    books = ["Python", "Java", "C", "Ruby"]

for i in range(1, len(books)):
key = books[i]
j = i - 1
while j >= 0 and key < books[j]:
    books[j + 1] = books[j]
    j -= 1
books[j + 1] = key

print(books)

Case Study 3: Performance Analysis

A programmer compares sorting algorithms.

Questions:

  1. Which sorting algorithm always takes O(n²) time? ✔ Selection Sort

  2. Which sorting algorithm has best case O(n)? ✔ Bubble Sort (optimized), Insertion Sort

  3. Why is Bubble Sort not used for large datasets? ✔ Because it is inefficient with O(n²) complexity.

Page last updated: 17-Mar-2026 18:38 IST
Document Version: v18