Sorting

Sorting means arranging data in a specified order. We might arrange examination scores from highest to lowest, student names alphabetically, or textbook pages by number. A useful sorting method gives the correct order and makes it possible to reason about what is compared, moved, and finished after each pass.

Source scope. This chapter follows the supplied NCERT Class XII Computer Science, Chapter 5, printed pages 67–80 (2026–27 reprint). The source contains Exercises 1–6, Activities 5.1–5.4, Algorithms 5.1–5.3, and Programs 5-1–5-3. Those items are covered in dedicated, independently explained sections below. The master curriculum provides no permanent sorting lesson IDs; the identifiers C12-CH05-S01 through C12-CH05-S06 are chapter anchors only and do not alter the curriculum.

Student navigation. Lessons → NCERT Activities → NCERT Program Walkthroughs → NCERT Exercise Solutions → Extra Practice → Revision/Viva. Each can be displayed separately on the website, even though this Markdown is delivered as a single editorial resource. Implementation instructions and image specifications are hidden in the appendix at the end.

Learning objectives#

After studying, you should be able to define sorting and passes; trace Bubble, Selection and Insertion Sort; write and call sorting functions; distinguish swapping from shifting; explain sorted and unsorted regions; solve all six NCERT exercises and four activities; calculate median and a clearly defined percentile; maintain alphabetically ordered names on insertion; estimate best-, average- and worst-case time and extra space; and select an appropriate technique for small or nearly sorted inputs.

Reading map#

Section C12-CH05-S01 — Sorting Fundamentals#

1. Order is a rule, not a single fixed operation#

A list [8, 7, 13, 1, -9, 4] can become [-9, 1, 4, 7, 8, 13] in ascending order or [13, 8, 7, 4, 1, -9] in descending order. The same idea applies to alphabetical names. A program needs a comparison rule: numeric < and > for numbers, or lexicographic string comparisons for names when appropriate. Mixing incomparable values (for example, a number and a string under Python 3) causes a TypeError unless a key or conversion is supplied.

marks = [8, 7, 13, 1, -9, 4]
print(sorted(marks))                 # [-9, 1, 4, 7, 8, 13]
print(sorted(marks, reverse=True))   # [13, 8, 7, 4, 1, -9]
print(marks)                         # original list unchanged

sorted(sequence) returns a new sorted list; list.sort() modifies that list in place and returns None. The three algorithms studied below also mutate an input list. Always state whether a function returns a new list or changes its argument.

2. Four words that appear in every sorting trace#

A comparison checks an ordering relation; a swap exchanges two positions; a pass is one defined sweep or iteration of an algorithm; and a sorted region is the part already guaranteed to be in final/ordered condition under the algorithm's invariant. These are not interchangeable terms: a comparison need not cause a swap, and insertion sort usually shifts elements rather than swapping every adjacent pair.

Stability is a useful extension: a stable algorithm preserves the original relative order of elements with equal sorting keys. Bubble Sort (strict >) and Insertion Sort (strict >) can be stable; this standard swap-based Selection Sort generally is not. This is supplemental precision beyond the textbook's main introductory descriptions.

3. Tracking an invariant#

An invariant is a fact that stays true at a particular program point. For Bubble Sort, after pass 1 the largest element occupies the last position. For Selection Sort, after pass 1 the smallest element occupies the first position. For Insertion Sort, after pass 1 the first two elements are ordered. This lets you check traces without memorizing every intermediate state.

Section C12-CH05-S02 — Bubble Sort#

Source: NCERT §5.2, Algorithm 5.1 and Program 5-1. The method compares adjacent elements and swaps only when their order is wrong. For ascending order, each complete pass moves the largest still-unsorted element to the rightmost available slot.

1. A complete trace of the textbook list#

Start with [8, 7, 13, 1, -9, 4]. In pass 1 compare indices (0,1), (1,2), ..., (4,5). The final 13 is guaranteed to be correct; the later passes do not inspect it. Record the list only at the end of each complete pass:

The textbook explicitly notes that the final pass above can be avoided if a pass makes no swaps; however, an early-stop optimization detects order by executing a zero-swap pass and is not necessarily able to skip the immediately preceding useful pass.

2. Algorithm 5.1 in words and pseudocode#

1. Let n be the list length.
2. Make at most n−1 passes for normal Bubble Sort.
3. In pass i, compare each adjacent pair from index 0 through n−i−2.
4. Swap if the left item is greater than the right item.
5. Once no swap happens in a pass, an optimized version may finish early.

BUBBLE-SORT(A)
    for i = 0 to length(A) - 2:
        for j = 0 to length(A) - i - 2:
            if A[j] > A[j+1]:
                swap A[j] and A[j+1]

3. Correct, readable Python implementation#

def bubble_sort(values):
    """Sort the input list in ascending order, in place."""
    n = len(values)
    for i in range(n - 1):
        for j in range(n - i - 1):
            if values[j] > values[j + 1]:
                values[j], values[j + 1] = values[j + 1], values[j]
    return values

numbers = [8, 7, 13, 1, -9, 4]
print(bubble_sort(numbers))
# [-9, 1, 4, 7, 8, 13]

The textbook's Program 5-1 uses an outer loop of range(n), which creates an extra empty-comparison final iteration; using range(n-1) avoids it without changing the sorted result. It prints elements individually; the revised function above prints the list so that the algorithm can be reused in NCERT Exercise 4.

4. Optimized Bubble Sort (extra clarification)#

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

print(bubble_sort_early_stop([1, 2, 3, 4]))  # [1, 2, 3, 4]

Complexity: standard Bubble Sort performs n(n−1)/2 comparisons and has O(n²) time even for ordered input; the early-stop variant performs O(n) comparisons on already ordered input but still has O(n²) worst-case time. Space is O(1) beyond the input list. Its swaps of adjacent unequal items give a stable ascending sort when using strict >.

5. Descending Bubble Sort#

For descending order, swap when values[j] < values[j + 1]; that moves the smallest remaining item to the right in each pass.

def bubble_sort_descending(values):
    for i in range(len(values) - 1):
        for j in range(len(values) - 1 - i):
            if values[j] < values[j + 1]:
                values[j], values[j + 1] = values[j + 1], values[j]
    return values

print(bubble_sort_descending([4, 2, 9, 1]))  # [9, 4, 2, 1]

Exam traps. Count full passes, not individual adjacent comparisons; a list may become sorted before n−1 passes have ended. bubble_sort mutates its argument; sorted does not. Two equal values should not be swapped for stability.

Section C12-CH05-S03 — Selection Sort#

Source: NCERT §5.3, Algorithm 5.2, Program 5-2. Selection Sort divides the list into a left sorted portion and right unsorted portion. On each pass it finds the minimum in the unsorted portion and exchanges it with that portion's first element.

1. See how the minimum is selected#

For [8, 7, 13, 1, -9, 4], the first minimum is -9 at index 4. After it exchanges with index 0, the first element is permanently correct. In pass 2 the smallest value among indexes 1–5 is 1, so it moves to index 1.

The fifth element needs no swap when it is already the minimum in the remaining range. Selection Sort always checks the remaining positions; a sorted input does not eliminate those comparisons.

2. Algorithm 5.2, improved explanation#

NCERT's algorithm uses a flag to decide whether to swap. Conceptually the simplest rule is: in pass i, set min_index=i, scan all j>i, update the minimum index if necessary, then swap only when min_index!=i.

SELECTION-SORT(A)
    for i = 0 to length(A) - 2:
        min_index = i
        for j = i+1 to length(A) - 1:
            if A[j] < A[min_index]:
                min_index = j
        if min_index != i:
            swap A[i] and A[min_index]

Textbook bug noted: The printed Program 5-2 sets its flag outside the outer pass loop, so the flag can remain true even after a later pass discovers no smaller item. Resetting the flag each pass, or replacing it with if min_index != i, gives a reliable reusable solution. The function below uses the latter approach.

3. Program 5-2 — corrected Python version#

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

numbers = [8, 7, 13, 1, -9, 4]
print(selection_sort(numbers))
# [-9, 1, 4, 7, 8, 13]

4. Why Selection Sort can reduce writes#

The basic algorithm makes exactly n(n−1)/2 key comparisons, whether the input is sorted or reversed. Each useful pass uses at most one swap, so there are at most n−1 swaps in total; some passes need none. This can matter if writes are costly. Time is O(n²) in best, average and worst cases for this implementation; auxiliary space is O(1).

Stability trap: Swapping a distant minimum can reorder records with equal keys. E.g. [2a, 2b, 1] (letters label separate records) becomes [1, 2b, 2a] after one swap, changing the order of records 2a and 2b.

Section C12-CH05-S04 — Insertion Sort#

Source: NCERT §5.4, Algorithm 5.3 and Program 5-3. Insertion Sort resembles placing each playing card into its correct position among cards already in the hand. The left part is ordered; the next key is inserted by shifting larger values right.

1. Inserting a key versus swapping a minimum#

Let the input be [8, 7, 13, 1, -9, 4].

On pass 3, the key is 1. First shift 13 right, then 8, then 7, until index 0 becomes available. Place 1 there. The method need not swap the key repeatedly, even though the original textbook illustration uses visual swap language.

2. Algorithm 5.3 — the ordered-prefix invariant#

Before each pass i, elements A[0:i] are sorted. Save A[i] as key and scan leftward through that prefix. Move every greater element right one slot, and finally place key in the remaining space.

INSERTION-SORT(A)
    for i = 1 to length(A) - 1:
        key = A[i]
        j = i-1
        while j >= 0 and A[j] > key:
            A[j+1] = A[j]
            j = j-1
        A[j+1] = key

3. Correct Python implementation#

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

numbers = [8, 7, 13, 1, -9, 4]
print(insertion_sort(numbers))
# [-9, 1, 4, 7, 8, 13]

NCERT's Program 5-3 begins the outer loop at 0; this produces a harmless redundant initial pass. Starting at 1 makes the invariant explicit: one element is already sorted. The while loop's condition must check j >= 0 before accessing values[j].

4. Why Insertion Sort behaves differently on sorted input#

For an already ordered list, each new key can stay where it is after roughly one key comparison: best-case O(n). On a reversed list, inserting each key requires shifting nearly the entire sorted prefix, giving worst-case O(n²). It uses O(1) auxiliary space. The strict values[j] > key comparison does not move equal keys past one another, so the algorithm is stable.

5. Maintaining names as they arrive#

If names are accepted one at a time and inserted in their alphabetical place, the design uses insertion-sort thinking. The code can insert the new name directly into an already sorted list rather than rerun full sorting. A concrete answer for NCERT Exercise 6 appears in the solution bank.

Section C12-CH05-S05 — Time Complexity and Algorithm Comparison#

Source: NCERT §5.5. Time complexity describes how the amount of work grows when input size n grows. It is not a universal duration in seconds, because machines and inputs differ.

1. Counting comparisons#

Three common textbook growth patterns are: one fixed operation O(1), one full traversal O(n), and two nested passes each around n giving O(n²). But the exact loop bounds and data-dependent exits matter: a nested loop is not automatically quadratic if its total number of iterations is less; it must be analysed in context.

For fixed-bound Bubble Sort and standard Selection Sort:

Here, O(n²) describes upper-bound growth; the explicit count is the number of comparisons for the particular implementations above.

2. Comparison chart#

Source distinction: NCERT groups all three sorting algorithms as quadratic by observing nested loops; the detailed best-case distinctions above are an extension needed for accurate reasoning. The textbook's introductory aim is to estimate growth, not provide a full formal proof.

3. Do not confuse comparisons, swaps, and moves#

A Selection Sort pass may compare five values and swap once. A Bubble Sort pass may compare five adjacent pairs and swap up to five times. An Insertion Sort pass can shift several items and then insert the key once. For a fair exercise answer, state what counts as a comparison (normally key-to-key) and whether self-swaps are counted (normally not).

4. Boundary cases#

The input [] and a one-element list are already sorted. Duplicate values require a consistent comparison rule. Extremely large data generally calls for built-in sorted()/.sort() in real Python applications, not these classroom algorithms; the goal here is to learn invariants and algorithmic thinking. Python's built-in sorting is stable, and the beginner programs in this chapter are illustrative rather than replacements for production sorting libraries.

Section C12-CH05-S06 — Sorting in Problem-Solving Applications#

1. Median after sorting#

The median is the central value when the list has odd length. With even length, take the average of the two central values. Sorting helps locate these positions. The empty list has no median, and a function should specify how it handles that case.

def median_using_bubble(numbers):
    if not numbers:
        raise ValueError("median requires at least one value")
    data = numbers.copy()
    bubble_sort(data)  # defined in the previous lesson
    n = len(data)
    if n % 2:
        return data[n // 2]
    return (data[n // 2 - 1] + data[n // 2]) / 2

print(median_using_bubble([9, 3, 5]))    # 5
print(median_using_bubble([9, 3, 5, 7])) # 6.0

The function above refers to the reusable bubble_sort function in Section S02; the full standalone solution in Exercise 4 repeats the sorting function so a student can copy one example alone.

2. Percentiles need an explicit convention#

A percentile is an order-statistic summary. There are several definitions (nearest rank, interpolation and other conventions); different definitions can give different values for the same data. NCERT Exercise 5 prescribes selection sorting and then rounding a rank calculation, but it incorrectly names Python function math.round(), and the text does not resolve the 0-based/1-based offset or ties. In this resource, the nearest-rank rule is explicitly chosen: for 0 < p <= 100, use 1-based rank ceil(p*n/100), then index rank-1; for p=0, return the minimum. This is a clearly labelled, correct interpretation of the classroom exercise rather than an assertion that it is the only percentile convention.

from math import ceil

def percentile_nearest_rank(values, p):
    if not values:
        raise ValueError("no values")
    if not 0 <= p <= 100:
        raise ValueError("percentile must be 0 to 100")
    data = values.copy()
    selection_sort(data)  # defined in the previous lesson
    rank = max(1, ceil(p * len(data) / 100))
    return data[rank - 1]

print(percentile_nearest_rank([10, 30, 20, 40, 50], 60))  # 30
print(percentile_nearest_rank([10, 30, 20, 40, 50], 0))   # 10
print(percentile_nearest_rank([10, 30, 20, 40, 50], 100)) # 50

For example, for n=120, p=90, the rank is ceil(108)=108, so the correct zero-based index is 107, not index 108. In some other quantile conventions, the reported percentile may differ. With ties, a score at the 90th percentile does not literally mean “better than exactly 90%” of classmates.

3. Inserting a name into a sorted list#

def insert_name_sorted(names, new_name):
    """Insert into a list already sorted in Python lexicographic order."""
    i = len(names)
    names.append(new_name)
    while i > 0 and names[i - 1] > new_name:
        names[i] = names[i - 1]
        i -= 1
    names[i] = new_name
    return names

admitted = []
for name in ("Rita", "Aman", "Neha", "Geet"):
    insert_name_sorted(admitted, name)
print(admitted)  # ['Aman', 'Geet', 'Neha', 'Rita']

Exam note: Python's default string sorting is case-sensitive and uses Unicode code-point comparisons; for case-insensitive sorting, decide and state a comparison rule. A list that is already ordered by one key must not silently be treated as ordered by another.

4. A single safe way to trace every sorting question#

Write the initial list. Mark the exact outer-loop pass number. Run all the internal comparisons for that pass. Record the completed state and its sorted prefix/suffix. Continue only for the requested number of passes. For a question about comparisons or swaps, count them separately and define whether an unchanged pass counts as a pass (usually yes).

NCERT Activities 5.1–5.4 — Complete Answers#

These activities are the four side exercises printed within NCERT Chapter 5; they are not additional numbered end-of-chapter exercises.

Activity 5.1 — Adapt Bubble Sort for descending order#

Task in original terms: Write a bubble-sort algorithm that orders numbers from largest to smallest. The only required comparison change is > → < for adjacent elements: when a left element is smaller than its right neighbour, exchange the two. After each pass the smallest item moves to the end of the unsorted prefix.

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

print(bubble_desc([8, 7, 13, 1, -9, 4]))
# [13, 8, 7, 4, 1, -9]

Activity 5.2 — Bubble Sort [8, 7, 6, 5, 4]: where is the last swap?#

Answer: The last swap occurs in pass 4. Under range(n-1) there is no further fifth pass; under the textbook's outer range(n) there would be a redundant fifth outer iteration with no comparisons.

Activity 5.3 — Selection Sort 10 elements for four passes#

List: [7,11,3,10,17,23,1,4,21,5].

Answer: The requested partially sorted list is [1,3,4,5,17,23,7,11,21,10]. The four leftmost values are now in final ascending positions, but the list as a whole is not yet sorted.

Activity 5.4 — Insertion Sort 10 elements for three passes#

Use the same list as Activity 5.3. In the first insertion pass, insert the element at index 1 (11) into the prefix [7] (no move). Pass 2 inserts 3; pass 3 inserts 10.

Answer: [3,7,10,11,17,23,1,4,21,5] after three complete passes, using Algorithm 5.3's outer pass beginning at index 1.

NCERT Worked Programs 5-1–5-3 — Explained Walkthroughs#

The official textbook programs all demonstrate ascending ordering of [8,7,13,1,-9,4]. The following runnable versions show the same core operations and result while removing harmless/reliability issues in the printouts.

Program 5-1 — Bubble Sort walkthrough#

Input: [8,7,13,1,-9,4]. Key operation: compare neighbours and exchange when left > right. Important bound: range(n-i-1) avoids comparing the confirmed sorted suffix. The textbook's extra outer pass is unnecessary. Output: [-9,1,4,7,8,13].

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

print(bubble_textbook_demo([8, 7, 13, 1, -9, 4]))
# [-9, 1, 4, 7, 8, 13]

Program 5-2 — Selection Sort walkthrough#

Input: Same six values. Key operation: track min_index across the entire unsorted suffix, then possibly swap once. The printed flag implementation is safer if flag is reset each pass; here the condition min_index != i makes the fix obvious. Output: [-9,1,4,7,8,13].

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

print(selection_textbook_demo([8, 7, 13, 1, -9, 4]))
# [-9, 1, 4, 7, 8, 13]

Program 5-3 — Insertion Sort walkthrough#

Input: Same values. Key operation: set aside key, shift larger values to the right, insert into the remaining gap. Outer range(1,n) avoids the redundant index-0 iteration in the printed program. Output: [-9,1,4,7,8,13].

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

print(insertion_textbook_demo([8, 7, 13, 1, -9, 4]))
# [-9, 1, 4, 7, 8, 13]

Common output check for all three: the sorted values, in increasing order, are -9 1 4 7 8 13. When comparing classroom programs, count key comparisons and data movements separately; identical output does not mean identical work.

NCERT Chapter 5 — Complete Exercise Solutions (Questions 1–6)#

Each question heading preserves the original NCERT exercise number; prompts are paraphrased rather than reproduced verbatim. The given numerical values, required methods and distinct parts are maintained.

NCERT Exercise 1 — Bubble Sort: first three passes for ten values#

Question: Given [7,11,3,10,17,23,1,4,21,5], determine the state after three complete Bubble Sort passes.

Final answer after exactly 3 passes: [3,7,10,1,4,11,5,17,21,23]. Even though the rightmost three positions are correct, the prefix is not fully sorted. Do not mistakenly report the final sorted list.

a = [7, 11, 3, 10, 17, 23, 1, 4, 21, 5]
for i in range(3):
    for j in range(len(a) - i - 1):
        if a[j] > a[j + 1]:
            a[j], a[j+1] = a[j+1], a[j]
    print(f"After pass {i+1}: {a}")
# 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]

NCERT Exercise 2 — Swaps and comparisons: [63,42,21,9]#

Question: Sort four descending values with Selection and Bubble Sort; count swaps and decide which makes fewer comparisons.

Selection Sort trace:

Selection Sort totals: 2 actual swaps, 6 key comparisons (3+2+1). If a pseudocode version counts a self-assignment at pass 3 as a “swap”, it may report 3 swap statements, but we do not count a no-op as an actual exchange.

Bubble Sort trace:

Bubble Sort totals: 6 swaps, 6 comparisons (3+2+1). Conclusion: Under these standard loop bounds neither algorithm is better in comparison count for this list: both make 6. Selection is better in actual swap count, 2 versus 6. A claim that Selection made fewer comparisons would conflate the two measurements.

NCERT Exercise 3 — Insertion Sort: ordered versus reverse-ordered input#

Question: Compare insertion sorting of [2,3,5,7,11] and [11,7,5,3,2]. Which needs the fewest key comparisons? Explain with a diagram/trace.

For the already ordered first list, each key 3,5,7,11 is checked against the rightmost previous value and no shifting occurs.

For the reverse-ordered second list, the key must be compared against every value in the sorted prefix and all larger values shift right.

Answer: List 1 makes fewer key comparisons: 4 versus 10. Here a “key comparison” means an actual comparison between two data values; we exclude j >= 0 loop-bound checks.

NCERT Exercise 4 — Function to find median using Bubble Sort#

Question: Write a user-defined function that takes a numeric list, sorts it with Bubble Sort and reports the median.

def median_bubble(numbers):
    if len(numbers) == 0:
        raise ValueError("Cannot find the median of an empty list")
    data = numbers.copy()
    n = len(data)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if data[j] > data[j+1]:
                data[j], data[j+1] = data[j+1], data[j]
    mid = n // 2
    return data[mid] if n % 2 else (data[mid - 1] + data[mid]) / 2

print(median_bubble([15, 7, 11, 3, 9]))  # 9
print(median_bubble([15, 7, 11, 3]))     # 9.0

Explanation: For five items the ordered values are [3,7,9,11,15]; index 5//2=2 contains 9. For four items [3,7,11,15], use (7+11)/2=9.0. Copying the list prevents surprising callers by changing their original list. The guard avoids indexing an empty list.

NCERT Exercise 5 — Percentile of aptitude marks using Selection Sort#

Question: Accept a marks list and an x between 0 and 100, order the marks using Selection Sort and report the xth percentile.

Important corrections to the printed question: math.round() does not exist in Python (round() is built in); the example 0.90*120=108 is a rank calculation, not a valid Python index; and different percentile conventions have different boundaries/interpolations. To produce a testable function, this solution uses the nearest-rank definition stated in Section S06, and a zero-based index rank-1.

from math import ceil

def percentile_selection(marks, x):
    if not marks:
        raise ValueError("At least one mark is required")
    if not 0 <= x <= 100:
        raise ValueError("x must be between 0 and 100")

    values = marks.copy()
    n = len(values)
    for i in range(n - 1):
        min_index = i
        for j in range(i + 1, n):
            if values[j] < values[min_index]:
                min_index = j
        if min_index != i:
            values[i], values[min_index] = values[min_index], values[i]

    rank = max(1, ceil(x * n / 100))
    return values[rank - 1]

marks = [49, 88, 60, 75, 91, 70, 81, 55, 96, 78]
print(percentile_selection(marks, 90))   # 91
print(percentile_selection(marks, 0))    # 49
print(percentile_selection(marks, 100))  # 96

Worked trace: The ordered marks are [49,55,60,70,75,78,81,88,91,96]. At x=90, ceil(90*10/100)=9, so the ninth smallest value is 91 (index 8). For x=0, return the minimum; for x=100, return the maximum. Tied scores and interpolation conventions can affect a percentile interpretation; state the chosen definition when comparing external results.

NCERT Exercise 6 — Insert names in alphabetical order as they arrive#

Question: Identify the method and write a function called each time a student name is received.

Technique: Insertion Sort / ordered insertion. After each accepted name the list should remain sorted. The efficient teaching solution preserves the existing sorted prefix and shifts only those names greater than the incoming one.

def admit_name(names, new_name):
    # Precondition: names is already sorted in ascending order.
    # This uses the default case-sensitive Python string comparison.
    names.append(new_name)
    i = len(names) - 1
    while i > 0 and names[i-1] > new_name:
        names[i] = names[i-1]
        i -= 1
    names[i] = new_name
    return names

students = []
for name in ("Meera", "Aman", "Rita", "Geet", "Neha"):
    admit_name(students, name)
    print(students)
# ['Meera']
# ['Aman', 'Meera']
# ['Aman', 'Meera', 'Rita']
# ['Aman', 'Geet', 'Meera', 'Rita']
# ['Aman', 'Geet', 'Meera', 'Neha', 'Rita']

Explanation: When Geet arrives, move Rita and Meera one position right until an appropriate slot is available after Aman. Insert Geet without rebuilding the earlier sorted list. If case-insensitive alphabetical order is desired, define a consistent key (e.g. casefold()) for every comparison; mixing order conventions invalidates the assumption that the current list is sorted.

Original Practice — 30 Questions with Explained Answers#

These are original extra questions, not quotations from NCERT or previous-year board examinations. Read the explanations after attempting each item independently.

Part A — Conceptual MCQs (1–10)#

Practice 1 — When Bubble Sort compares two adjacent elements for ascending order, which condition triggers a swap?#

A. Left > right; B. Left < right; C. Left == right; D. Always

Answer: A. For ascending order, adjacent values are exchanged only when the left value exceeds the right value.

Practice 2 — After one Selection Sort pass on an unsorted list, which position is guaranteed to be correct?#

A. Last; B. First; C. Middle; D. All positions

Answer: B. The smallest value is moved to the first position, so the sorted prefix has length one.

Practice 3 — An insertion-sort pass starts with an already sorted prefix. What is done with the next key?#

A. Delete it; B. Append it at the end unconditionally; C. Shift larger values right and insert; D. Reverse the prefix

Answer: C. Insertion Sort creates a gap by shifting larger prefix values one place right and inserts the saved key.

Practice 4 — Which method is normally best-case linear for already sorted data?#

A. Standard Selection Sort; B. Insertion Sort; C. Standard fixed-pass Bubble Sort; D. Both A and C

Answer: B. Insertion Sort finds no larger preceding item for each key and needs only about one key comparison per pass.

Practice 5 — What does sorted([3,1,2]) return?#

A. The number of swaps; B. None; C. A new list [1,2,3]; D. It raises an error

Answer: C. The built-in sorted creates a new list, leaving the input untouched.

Practice 6 — Which sorting algorithm typically uses at most one exchange per outer pass?#

A. Selection Sort; B. Bubble Sort; C. Both always; D. Neither

Answer: A. A minimum is selected from the remaining suffix and optionally swapped with the first unsorted element.

Practice 7 — What is the space complexity of the provided in-place insertion sort, ignoring the input list?#

A. O(n); B. O(log n); C. O(1); D. O(n²)

Answer: C. Only the key and a few indices are stored; no auxiliary array scales with n.

Practice 8 — For ascending stable insertion sort, which shift condition is correct?#

A. a[j] >= key; B. a[j] > key; C. a[j] == key; D. j < 0

Answer: B. Strictly greater values shift, while equal values preserve their relative order.

Practice 9 — For five elements, how many key comparisons does the fixed-pass Bubble Sort program perform?#

A. 5; B. 10; C. 20; D. 25

Answer: B. The nested bounds yield 4+3+2+1 = 10 comparisons.

Practice 10 — For x=100, which position does nearest-rank percentile select from a nonempty sorted dataset?#

A. First; B. Middle; C. Last; D. Outside the list

Answer: C. Rank ceil(1*n)=n, which corresponds to zero-based index n−1.

Part B — Tracing and Calculations (11–18)#

Practice 11 — Trace a single Bubble Sort pass on [5,1,4,2].#

Answer: [1,4,2,5].

Why: 5 moves past 1, 4 and 2; after the pass it is in the final rightmost position.

Practice 12 — Trace two complete Bubble Sort passes on [4,3,2,1].#

Answer: Pass 1 [3,2,1,4]; pass 2 [2,1,3,4].

Why: The largest remaining element is pushed into place on each pass.

Practice 13 — Trace one Selection Sort pass on [9,4,7,1].#

Answer: [1,4,7,9].

Why: The minimum 1 at the last position exchanges with 9 at the first position.

Practice 14 — Trace two Selection Sort passes on [6,5,4,3].#

Answer: Pass 1 [3,5,4,6]; pass 2 [3,4,5,6].

Why: After the first pass 3 is final; the second pass selects 4 from the remaining suffix.

Practice 15 — Trace one Insertion Sort pass on [2,5,3,7] when the key is 3 at index 2.#

Answer: [2,3,5,7].

Why: 5 shifts right; then 3 occupies the freed index 1.

Practice 16 — Find the number of actual Bubble Sort swaps for [3,2,1].#

Answer: 3 swaps.

Why: Reverse order has three inverted pairs: (3,2), (3,1), (2,1). Bubble Sort exchanges each inversion once.

Practice 17 — Find actual Selection Sort swaps for [1,2,3,4] when self-swaps are skipped.#

Answer: 0 swaps.

Why: At each pass, the minimum is already at the leftmost available position.

Practice 18 — Show first three Insertion Sort passes for [6,2,5,1,4].#

Answer: Pass 1 [2,6,5,1,4]; pass 2 [2,5,6,1,4]; pass 3 [1,2,5,6,4].

Why: The keys 2, 5 and 1 are inserted in turn into increasingly long sorted prefixes.

Part C — Short-answer Reasoning (19–24)#

Practice 19 — Distinguish an adjacent swap from a shift.#

Answer and explanation: A swap exchanges the values at two positions; a shift copies a value to the adjacent free position to create room for a later insertion.

Practice 20 — Why is standard Selection Sort not usually stable?#

Answer and explanation: It can swap a distant minimum ahead of an earlier equal-key item, changing the original order of equal records.

Practice 21 — Why can early-stop Bubble Sort be O(n) on sorted data?#

Answer and explanation: A single pass compares adjacent items, finds no swap, and immediately ends; about n−1 comparisons are needed.

Practice 22 — Why does insertion sort work efficiently on nearly ordered data?#

Answer and explanation: Most keys require few comparisons and shifts because their correct position is close to where they already appear.

Practice 23 — Does a value at the 90th percentile always beat exactly 90% of classmates?#

Answer and explanation: No. Percentile conventions vary, and tied scores break a literal exact-percentage interpretation.

Practice 24 — Explain how the sorted region grows for each of the three techniques.#

Answer and explanation: Bubble: a confirmed suffix expands from the right. Selection: a final-position prefix expands from the left. Insertion: an internally ordered prefix grows from the left.

Part D — Applied Python Programming (25–30)#

Practice 25 — Write a function that returns a new sorted numeric list using Insertion Sort, leaving the original unchanged.#

Worked answer:

def insertion_copy(values):
    data = values.copy()
    for i in range(1, len(data)):
        key = data[i]
        j = i - 1
        while j >= 0 and data[j] > key:
            data[j + 1] = data[j]
            j -= 1
        data[j + 1] = key
    return data

source = [7, 2, 5]
print(insertion_copy(source))  # [2, 5, 7]
print(source)                  # [7, 2, 5]

Explanation: The copy is sorted in place, so the caller's original list retains its initial order.

Practice 26 — Implement Selection Sort descending on [4,1,9,3].#

Worked answer:

def selection_desc(values):
    for i in range(len(values) - 1):
        max_index = i
        for j in range(i + 1, len(values)):
            if values[j] > values[max_index]:
                max_index = j
        if max_index != i:
            values[i], values[max_index] = values[max_index], values[i]
    return values

print(selection_desc([4, 1, 9, 3]))  # [9, 4, 3, 1]

Explanation: To sort descending, select the largest remaining value instead of the smallest.

Practice 27 — Write a function that counts Bubble Sort swaps without modifying the input.#

Worked answer:

def bubble_swaps(values):
    data = values.copy()
    swaps = 0
    for i in range(len(data) - 1):
        for j in range(len(data) - 1 - i):
            if data[j] > data[j + 1]:
                data[j], data[j + 1] = data[j + 1], data[j]
                swaps += 1
    return swaps

print(bubble_swaps([4, 3, 2, 1]))  # 6

Explanation: Each adjacent exchange fixes exactly one inverted pair; this reverse-sorted four-element input has six such pairs.

Practice 28 — Write an empty-input-safe minimum finder using Selection Sort, returning the minimum value.#

Worked answer:

def minimum_via_selection(values):
    if not values:
        raise ValueError("empty input")
    data = values.copy()
    for i in range(len(data) - 1):
        minimum = i
        for j in range(i + 1, len(data)):
            if data[j] < data[minimum]:
                minimum = j
        if minimum != i:
            data[i], data[minimum] = data[minimum], data[i]
    return data[0]

print(minimum_via_selection([6, -2, 8]))  # -2

Explanation: Selection Sort places the overall minimum at index zero; the empty-list guard prevents invalid indexing.

Practice 29 — Make a function that reports whether sorting changed a list's original order, using Bubble Sort.#

Worked answer:

def originally_sorted(values):
    return all(values[i] <= values[i + 1]
               for i in range(len(values) - 1))

print(originally_sorted([1, 2, 2, 3]))  # True
print(originally_sorted([1, 3, 2]))     # False

Explanation: A neighbouring inversion is sufficient to prove a list is not already in nondecreasing order; this direct test is simpler than sorting a copy.

Practice 30 — Write a program that maintains sorted exam scores as they arrive.#

Worked answer:

def add_score(sorted_scores, score):
    sorted_scores.append(score)
    pos = len(sorted_scores) - 1
    while pos > 0 and sorted_scores[pos - 1] > score:
        sorted_scores[pos] = sorted_scores[pos - 1]
        pos -= 1
    sorted_scores[pos] = score
    return sorted_scores

scores = []
for score in (70, 55, 90, 65):
    add_score(scores, score)
print(scores)  # [55, 65, 70, 90]

Explanation: Each new score is inserted into the existing sorted prefix, so ordering is maintained after every arrival.

Quick Revision — Sorting at a Glance#

Common NCERT exam traps#

1. Pass count is not swap count. A pass may contain no swaps or several.
2. Partially sorted ≠ fully sorted. Record the state after exactly the requested number of full passes.
3. Selection comparisons ≠ Selection swaps. A selection pass scans an entire suffix but exchanges at most once.
4. Insertion Sort shifts. It is not identical to Bubble Sort's adjacent-pair exchanges.
5. sorted() is not sort(). The former returns a new list, the latter returns None after mutating the original list.
6. math.round() does not exist. Python has built-in round(), while percentile work requires a clear convention and index conversion.
7. Loop counts depend on bounds. The textbook sometimes includes redundant outer-loop iterations; reference implementations here use the minimally necessary bounds.
8. Time complexity is input-sensitive. Optimized Bubble and Insertion can be linear on already sorted input, unlike standard Selection.
9. Equal keys matter. A distant Selection swap can upset relative ordering among equal-key records.
10. Check empty input and boundaries. Functions calculating medians or percentiles must reject [] and avoid out-of-range indexes.

Viva / oral review — with concise model answers#

Student self-check#

• I can run one complete pass of each sort by hand.
• I know which region is already sorted after any pass.
• I can explain all NCERT Exercises 1–6 and Activities 5.1–5.4.
• I can write ascending and descending variants.
• I can calculate median for odd and even list lengths.
• I understand the chosen nearest-rank percentile rule and why different rules exist.
• I can write a function that inserts a student name in alphabetical order.
• I can describe best/worst time and stability at the level of this chapter.