ITPEC FE Subject B April 2026 Question 11

Topic: Sorting

From the answer group below, select the correct combination of answers to be inserted into A and B in the program. Here, the array indexes start at 1.

Counting Sort is a non-comparison-based sorting algorithm. It is suitable for sorting a collection of objects according to keys that are small positive integers by means of counting the occurrences of key values in all data and then using those counts to place the values in their correct sorted positions.
The function countSort below describes a simple variant of counting sort algorithm. The function countSort receives 2 arguments as follows: arr, the array of small positive integers to be sorted, and M, the max value for the range of the array (from 1 to M), and returns the sorted array. Element count[k] of local array count holds the frequency of key value k in the range 1 to M.
For instance, when the function countSort is called as countSort({3, 6, 1, 5, 3, 4, 5}, 6), the value of array count is {1, 0, 2, 1, 2, 1}, and the function returns {1, 3, 3, 4, 5, 5, 6}.

[Program]
○ integer []: countSort(integer []: arr, integer M)
integer []: count ← {M zeros}
integer: i, j, k
integer: n ← the number of elements of arr
integer []: result ← {n zeros}
// counting each element of arr
for (increase i from 1 to n by 1)
k ← arr[i]
count[k] ← count[k] + 1
endfor
// forming array result from each key value and its count
i ← 1
for (increase k from 1 to M by 1)
if (A)
for (increase j from 1 to count[k] by 1)
result[i] ← k
B
endfor
endif
endfor
return result // sorted array

Answer group

OptionAB

Explanation

A: count[k] > 0, B: i ← i + 1 — the output loop walks the key values and writes each one as often as it was counted.

In the second loop the three counters have separate jobs: k is the key value being output, j counts its repetitions, and i is the next free slot in result.

  • •Blank A asks whether key k occurred at all, so it must read count[k]; a key with a count of 0 is skipped
  • •Blank B moves the write position on by one after each stored value, so the next copy goes into the next slot

Trace of the example, count = {1, 0, 2, 1, 2, 1}: key 1 goes to slot 1, key 2 is skipped, key 3 fills slots 2 and 3, key 4 slot 4, key 5 slots 5 and 6, key 6 slot 7, giving {1, 3, 3, 4, 5, 5, 6}.

Answer (d)

Why not others:

  • •(a), (b) and (c) — test count[i], the frequency of the slot number rather than of the key; in the example, at k = 3 the slot is i = 2 and count[2] is 0, so both 3s are skipped (and i can exceed M when n > M)
  • •(e) — i ← j + 1 resets the position from the repetition counter, which restarts at 1 for every key; the example ends as {1, 5, 6, 0, 0, 0, 0}, each key overwriting the start of result
  • •(f) — i ← k + 1 ties the slot to the key value, so later copies of a key and later keys collide; the example ends as {1, 3, 0, 4, 5, 6, 0}

Key rule: When a loop has several counters, name each one's role (key, repetition, output position) and check that every index and update uses the counter with that role.

Sorting · AI-written, may contain errors

Practice this exam

This question comes from an official ITPEC past paper. ITPEC Practice is an independent study tool and is not affiliated with ITPEC. See the official FE past-paper collection or Report an issue.