NCERT Solutions Class 12 Computer Science Chapter 5 Sorting

Bubble sort walks through the list and compares each pair of neighbours. In one pass, if the left element is larger, the two are swapped, so the bigger value moves one step right. After each pass the largest value among the unsorted part bubbles to its correct place at the right end. So after three passes the three largest values are locked at the far right. We run only the inner comparison loop three times, not the full sort.

• Pass 1. The largest value 23 keeps swapping rightward until it lands last. The list becomes [7, 3, 10, 11, 17, 1, 4, 21, 5, 23].
• Pass 2. Repeat over the first 9 elements. The next largest, 21, moves to position 8. The list becomes [3, 7, 10, 11, 1, 4, 17, 5, 21, 23].
• Pass 3. Repeat over the first 8 elements. The value 17 moves to position 7. The list becomes [3, 7, 10, 1, 4, 11, 5, 17, 21, 23].

numList = [7, 11, 3, 10, 17, 23, 1, 4, 21, 5]
n = len(numList)
for p in range(3):                 # three passes only
    for i in range(n - 1 - p):     # last p items already in place
        if numList[i] > numList[i + 1]:
            numList[i], numList[i + 1] = numList[i + 1], numList[i]
    print("After pass", p + 1, ":", numList)

After pass 1 : [7, 3, 10, 11, 17, 1, 4, 21, 5, 23]
After pass 2 : [3, 7, 10, 11, 1, 4, 17, 5, 21, 23]
After pass 3 : [3, 7, 10, 1, 4, 11, 5, 17, 21, 23]

Answer: After three complete passes of bubble sort the list is [3, 7, 10, 1, 4, 11, 5, 17, 21, 23].

We compare two methods on the same four-element list [63, 42, 21, 9]. Selection sort finds the smallest element in the unsorted part and puts it in place with one swap per pass. Bubble sort swaps neighbouring pairs whenever they are out of order, so a single pass can cause many swaps. Both methods make the same fixed number of comparisons, n(n-1)/2. For n = 4 that is (4 × 3)/2 = 6 comparisons.

Selection sort (count the swaps).

• Pass 1: smallest of [63, 42, 21, 9] is 9. Swap it with 63. List: [9, 42, 21, 63]. 1 swap.
• Pass 2: smallest of [42, 21, 63] is 21. Swap it with 42. List: [9, 21, 42, 63]. 1 swap.
• Pass 3: smallest of [42, 63] is 42, already in place. No swap.

Selection sort total: 2 swaps, 6 comparisons.

Bubble sort (count the swaps).

• Pass 1: 63>42 swap, 63>21 swap, 63>9 swap. List: [42, 21, 9, 63]. 3 swaps.
• Pass 2: 42>21 swap, 42>9 swap. List: [21, 9, 42, 63]. 2 swaps.
• Pass 3: 21>9 swap. List: [9, 21, 42, 63]. 1 swap.

Bubble sort total: 6 swaps, 6 comparisons.

Selection: (2, 6)
Bubble   : (6, 6)

Answer: Selection sort needs 2 swaps; bubble sort needs 6 swaps. Both make 6 comparisons, so on comparisons they tie; counting swaps, selection sort is the better technique for this list.

Insertion sort builds the sorted list one element at a time. It treats the first element as sorted, then takes the next element (the key) and compares it leftwards, shifting larger values right, until the key sits in place. The number of comparisons depends on the data. In the best case the list is already sorted ascending, so one comparison settles each key. In the worst case the list is reverse sorted, so each key is compared against every value before it.

List 1 [2, 3, 5, 7, 11] is already sorted ascending (best case). Each key needs one comparison with its left neighbour.

• Key 3: compare with 2. 3>2, stays. 1 comparison.
• Key 5: compare with 3. 5>3, stays. 1 comparison.
• Key 7: compare with 5. 7>5, stays. 1 comparison.
• Key 11: compare with 7. 11>7, stays. 1 comparison.

List 1 total: 1+1+1+1 = 4 comparisons, 0 shifts.

List 2 [11, 7, 5, 3, 2] is reverse sorted (worst case). Each key is smaller than everything to its left.

• Key 7: compare with 11. 1 comparison, shift.
• Key 5: compare with 11, then 7. 2 comparisons.
• Key 3: compare with 11, 7, 5. 3 comparisons.
• Key 2: compare with 11, 7, 5, 3. 4 comparisons.

List 2 total: 1+2+3+4 = 10 comparisons, with many shifts.

List 1: 4
List 2: 10

Answer: List 1 makes the minimum number of comparisons (4), because it is already sorted (best case for insertion sort). List 2 is reverse sorted (worst case) and needs 10 comparisons.

The median is the middle value of a list once it is sorted. First we sort the list, and the hint asks for bubble sort. Second we pick the middle. If the count n is odd, there is one exact middle at index n // 2, and that value is the median. If n is even, the median is the average of the two middle terms at n // 2 - 1 and n // 2. We write two user-defined functions: one to bubble sort, one to find the median.

def bubble_sort(data):
    a = data[:]                 # work on a copy
    n = len(a)
    for p in range(n - 1):
        for i in range(n - 1 - p):
            if a[i] > a[i + 1]:
                a[i], a[i + 1] = a[i + 1], a[i]
    return a

def find_median(numbers):
    s = bubble_sort(numbers)    # sort first
    n = len(s)
    if n % 2 == 1:              # odd count: one middle term
        return s[n // 2]
    else:                       # even count: average the two middles
        return (s[n // 2 - 1] + s[n // 2]) / 2

marks = [12, 5, 7, 1, 9]
print("Median (odd count):", find_median(marks))
marks2 = [12, 5, 7, 1]
print("Median (even count):", find_median(marks2))

For [12, 5, 7, 1, 9], bubble sort gives [1, 5, 7, 9, 12]; with n = 5 the middle index is 5 // 2 = 2, so the median is 7. For [12, 5, 7, 1], the sorted list is [1, 5, 7, 12]; the two middle terms are 5 and 7, so the median is (5 + 7) / 2 = 6.0.

Median (odd count): 7
Median (even count): 6.0

Answer: The program sorts the list with bubble sort, then returns the middle term for an odd count or the average of the two middle terms for an even count. Example: [12, 5, 7, 1, 9] gives median 7; [12, 5, 7, 1] gives median 6.0.

A percentile tells you how a score compares with everyone else. The 90th percentile is the value a candidate must beat to score better than 90% of the group. The NCERT method has four steps. First, selection sort arranges the marks smallest to largest. Second, find an index by (x / 100) * n. Third, make that index a whole number with round(). Fourth, read and display the value at that index. Note: the hint writes math.round(), but the real function in Python is plain round().

def selection_sort(data):
    a = data[:]                 # work on a copy
    n = len(a)
    for i in range(n - 1):
        mn = i                  # index of smallest in the rest
        for j in range(i + 1, n):
            if a[j] < a[mn]:
                mn = j
        a[i], a[mn] = a[mn], a[i]   # swap smallest into place
    return a

def percentile(marks, x):
    s = selection_sort(marks)       # Step I: order ascending
    n = len(s)
    index = round((x / 100) * n)    # Step II and III: index, then whole number
    if index >= n:                  # keep the index inside the list
        index = n - 1
    return s[index]                 # Step IV: value at the index

marks = [20, 50, 33, 12, 45, 60, 18, 75, 29, 90]
print("Sorted:", selection_sort(marks))
print("90th percentile:", percentile(marks, 90))
print("50th percentile:", percentile(marks, 50))

For the sample list of 10 marks, selection sort gives [12, 18, 20, 29, 33, 45, 50, 60, 75, 90]. For the 90th percentile, (90 / 100) * 10 = 9.0, round(9.0) = 9, so the value at index 9 is 90. For the 50th percentile, (50 / 100) * 10 = 5.0, round(5.0) = 5, so the value at index 5 is 45.

Sorted: [12, 18, 20, 29, 33, 45, 50, 60, 75, 90]
90th percentile: 90
50th percentile: 45

Answer: The function sorts the marks with selection sort, computes index = round((x/100)*n), and returns the value at that index. For the 10-mark sample, the 90th percentile is 90 and the 50th percentile is 45.

Sorting items at the moment they are added, so the list is always in order, is exactly how insertion sort works. Insertion sort takes one new element and slides it left past every larger value, dropping it into place; doing this on every new name keeps the list sorted at all times. Names are compared with the ordinary operators, which order strings lexicographically (dictionary order), so "Amit" < "Bina" is true. We write a user-defined function called once per name: it appends the name, then bubbles it left until the name on its left is not greater.

def insert_in_order(names, new_name):
    names.append(new_name)          # add at the end first
    i = len(names) - 1
    while i > 0 and names[i - 1] > names[i]:
        names[i - 1], names[i] = names[i], names[i - 1]   # slide left
        i -= 1
    return names

student_list = []
count = int(input("How many names? "))
for k in range(count):
    name = input("Enter name: ")
    insert_in_order(student_list, name)     # called once per name
    print("List so far:", student_list)

Suppose names are entered as Riya, Amit, Sara, Bina, Dev. After each input the function drops the new name into place, so the list stays sorted throughout.

How many names? 5
Enter name: Riya
List so far: ['Riya']
Enter name: Amit
List so far: ['Amit', 'Riya']
Enter name: Sara
List so far: ['Amit', 'Riya', 'Sara']
Enter name: Bina
List so far: ['Amit', 'Bina', 'Riya', 'Sara']
Enter name: Dev
List so far: ['Amit', 'Bina', 'Dev', 'Riya', 'Sara']

Answer: The technique is insertion sort. The function appends each new name, then slides it left past larger names into its correct slot, so the list stays in ascending (dictionary) order after every input.