Question Bank — Sorting

NCERT Class 12 Computer Science · Chapter 5 · CBSE Board Pattern

Class 12 Computer Science Chapter 5 Question Bank CBSE Board Pattern

Section A — MCQs (10 questions, 1 mark each)

1. Which sorting algorithm repeatedly compares adjacent elements and swaps them if they are unordered?
(a) Selection Sort
(b) Insertion Sort
(c) Bubble Sort
(d) Merge Sort

2. In Bubble Sort, for a list of n elements, how many passes are made to sort the list?
(a) n passes
(b) n–1 passes
(c) n+1 passes
(d) n/2 passes

3. Assertion (A): In Selection Sort, the list is divided into two parts — the sorted list and the unsorted list.
Reason (R): In each pass, the smallest element from the unsorted list is selected and swapped with the leftmost element of the unsorted list.
(a) Both A and R are true and R is the correct explanation of A.
(b) Both A and R are true but R is not the correct explanation of A.
(c) A is true but R is false.
(d) A is false but R is true.

4. Which sorting technique places each element from the unsorted part into its correct position in the sorted part by shifting elements?
(a) Bubble Sort
(b) Selection Sort
(c) Insertion Sort
(d) Quick Sort

5. Assertion (A): All three sorting algorithms — Bubble Sort, Selection Sort and Insertion Sort — have a time complexity of n².
Reason (R): Each of these algorithms contains a nested loop.
(a) Both A and R are true and R is the correct explanation of A.
(b) Both A and R are true but R is not the correct explanation of A.
(c) A is true but R is false.
(d) A is false but R is true.

6. In Selection Sort, after how many passes is the list completely sorted for n elements?
(a) n passes
(b) n–1 passes
(c) n+1 passes
(d) 2n passes

7. What is the time complexity of an algorithm that contains a nested loop (loop inside another loop)?
(a) Constant time (1)
(b) Linear time (n)
(c) Quadratic time (n²)
(d) Logarithmic time (log n)

8. In Bubble Sort, if no swapping occurs in a pass, what does it indicate?
(a) The list is reverse sorted
(b) The list is already sorted
(c) There is an error in the algorithm
(d) The algorithm must continue for all passes

9. Which sorting algorithm works by inserting each new element from the unsorted list into its correct position in the sorted list by traversing backwards?
(a) Bubble Sort
(b) Selection Sort
(c) Insertion Sort
(d) Heap Sort

10. An algorithm with no loops has what time complexity?
(a) n
(b) n²
(c) 1 (Constant time)
(d) log n

Section B — Very Short Answer (6 questions, 2 marks each)

1. Define sorting. Give one real-life example from the chapter where sorting is useful.

2. Differentiate between Bubble Sort and Selection Sort on the basis of the number of passes required for n elements.

3. What is the output of the following code fragment when numList = [8, 7, 13, 1, -9, 4] is passed to bubble_Sort?
python def bubble_Sort(list1): n = len(list1) for i in range(n): for j in range(0, n-i-1): if list1[j] > list1[j+1]: list1[j], list1[j+1] = list1[j+1], list1[j] (Write the final sorted list)

4. State the time complexity of Bubble Sort, Selection Sort and Insertion Sort. Justify using the chapter content.

5. In Insertion Sort, what happens in Pass 1 when the first element of the unsorted list is smaller than the single element in the sorted list?

6. What is the role of the flag variable in the Selection Sort algorithm given in the chapter?

Section C — Short Answer (5 questions, 3 marks each)

1. Explain with a diagram (or description) how Bubble Sort places the largest element at the end after the first pass. Use the list [8, 7, 13, 1, -9, 4].

2. The following code has an error. Identify the error and write the corrected code.
python def selection_Sort(list2): n = len(list2) for i in range(n): min = i for j in range(i+1, n): if list2[j] < list2[min]: min = j list2[min], list2[i] = list2[i], list2[min] # missing flag logic

3. Write the steps of the Insertion Sort algorithm (Algorithm 5.3) to sort the list [7, 11, 3] in ascending order. Show the list after each pass.

4. What is time complexity? According to the chapter, classify the following as constant, linear or quadratic time:
(a) An algorithm with a single loop from 1 to n
(b) An algorithm with no loops

5. Show the partially sorted list after three complete passes of Selection Sort on the list [7, 11, 3, 10, 17, 23, 1, 4, 21, 5].

Section D — Long Answer (3 questions, 5 marks each)

1. Write a complete Python program using a user-defined function insertion_Sort() that accepts a list of numbers and sorts it in ascending order using Insertion Sort. Also print the sorted list. (Use the implementation style from the chapter)

2. Explain the working of Selection Sort with a dry run using a trace table for the list [8, 7, 13, 1, -9, 4]. Show the list after each pass and indicate which element gets placed in the sorted portion.

3. Compare Bubble Sort, Selection Sort and Insertion Sort with respect to:
(a) Basic mechanism
(b) Number of passes
(c) Time complexity
Also state one advantage of stopping early in Bubble Sort when no swaps occur.

Section E — Case/Source-Based (2 questions, 4 marks each)

Case 1: A school wants to sort the marks of 120 students stored in a list to calculate the 90th percentile. The teacher decides to use Selection Sort as mentioned in the chapter.

Sub-questions:

(a) Why is Selection Sort suitable here according to the chapter? (1)
(b) How many passes will Selection Sort make on 120 elements? (1)
(c) After ordering the list using Selection Sort, what is the next step to find the 90th percentile? (1)
(d) If the sorted list index for 90th percentile is calculated as 108, what does the value at that index represent? (1)

Case 2: A programmer is implementing sorting for names that are inserted one by one and need to remain in ascending order at all times.

Sub-questions:

(a) Which sorting technique is being used when each new name is inserted at its correct position in the already sorted list? (1)
(b) In which direction does the algorithm traverse the sorted list to find the insertion position? (1)
(c) What is the time complexity of this technique? (1)
(d) State one situation from the chapter where maintaining sorted order helps in searching. (1)

▶ Answer Key Attempt all questions first,
then tap to reveal

Section A

  1. (c)
  2. (b)
  3. (a)
  4. (c)
  5. (a)
  6. (b)
  7. (c)
  8. (b)
  9. (c)
  10. (c)

Section B

  1. Sorting is the process of ordering or arranging a given collection of elements in some particular order. Example: Words in a dictionary are sorted in alphabetical order.
  2. Bubble Sort makes n–1 passes; Selection Sort also makes n–1 passes.
  3. [-9, 1, 4, 7, 8, 13]
  4. All three have time complexity n² because each contains a nested loop.
  5. The element s is shifted to the right and element e is inserted, making the sorted list size 2.
  6. The flag indicates whether a smaller element was found so that swapping is performed only when required.

Section C

  1. In the first pass, adjacent elements are compared and the largest element bubbles to the end.
  2. Error: Missing flag handling. Corrected code uses flag as shown in Program 5-2.
  3. Pass 1: [7,11,3] → [7,3,11]; Pass 2: [3,7,11]; Pass 3: [3,7,11]
  4. (a) Linear time (n) (b) Constant time (1)
  5. After 3 passes: [1, 3, 4, 7, 11, 10, 17, 23, 21, 5]

Section D

  1. Complete program (correct indented code):
    ```python def insertion_Sort(list3): n = len(list3) for i in range(1, n): temp = list3[i] j = i - 1 while j >= 0 and temp < list3[j]: list3[j+1] = list3[j] j = j - 1 list3[j+1] = temp

numList = [8, 7, 13, 1, -9, 4] insertion_Sort(numList) print("The sorted list is :") for i in range(len(numList)): print(numList[i], end=" ") ``` 2. Trace table showing min selection and swap in each pass (as per Figure 5.2).
3. Comparison points as per chapter definitions + early termination advantage in Bubble Sort.

Section E

Case 1: (a) Selection Sort is described for ordering before percentile calculation (b) 119 (c) Calculate index = 0.90 × 120 = 108 (d) Value at index 108 is the 90th percentile mark.
Case 2: (a) Insertion Sort (b) Backward direction (c) n² (d) Searching in a dictionary.

← Revision Summary All Chapters

All questions are answerable from the NCERT chapter text. Reviewed by GFIS faculty.