Searching, Sorting, Selection and Hashing PYQs for GATE CS

Solve 10+ Searching, Sorting, Selection and Hashing previous year questions for GATE CS with answers and detailed solutions. Free sample questions below.

Chapter Roadmap: Searching, Sorting, Selection and Hashing

Your journey through this chapter:

1. Sorting Algorithms and Operation Counts Master exact comparison and swap counts for Bubble, Insertion, Selection, Merge, and Quick sort.

2. Binary and Bitonic Array Searching Achieve logarithmic time search in sorted and bitonic arrays.

3. Selection and Comparison Bounds Learn the theoretical minimum comparisons required for selection problems.

4. Linear-Time Array Property Verification Design single-pass algorithms to verify specific array conditions.

5. Universal Hashing and Adversarial Inputs Choose hash functions that minimize collisions against malicious inputs.

What you will master: Trace any sorting or searching algorithm, count its exact operations, and identify the most efficient approach for any data distribution.

Sorting Algorithms and Operation Counts

Why this matters: Sorting is not just about getting a sorted array; it is about understanding the computational cost of rearranging data. Different algorithms pay this cost in different ways: some through excessive comparisons, others through excessive data movement.

What you will learn here:

How to derive exact comparison and swap counts for standard sorting algorithms.
The relationship between array inversions and sorting operation counts.
How to identify "void" operations in divide-and-conquer sorting.
Common pitfalls in analyzing loop bounds and operation totals.

The core idea: An algorithm's efficiency on a specific input is determined by counting its fundamental operations. For sorting, these are comparisons (A[j] > A[j+1]) and data movements (swap or shift).

Searching, Sorting, Selection and Hashing: Solved Questions with Step-by-Step Explanations (10 Problems)

Question 1 · Algorithms · 2026_Set2 NAT

Consider an array

A = [10, 7, 8, 19, 41, 35, 25, 31]

. Suppose the merge sort algorithm is executed on array

A

to sort it in increasing order. The merge sort algorithm will carry out a total of 7 merge operations.

A merge operation on sorted left array

L

and sorted right array

R

is said to be void if the output of the merge operation is the elements of array

L

followed by the elements of array

R

.

The number of void merge operations among these 7 merge operations is __________. (answer in integer)

Correct Answer:

Step-by-Step Solution

Key idea: This is a merge sort operation counting question, recognisable because it asks for the number of "void" merge operations on a specific array. A void merge occurs when the left subarray's maximum element is less than or equal to the right subarray's minimum element.

Step 1: Trace the merge sort tree for $A = [10, 7, 8, 19, 41, 35, 25, 31]$ .

Step 2: Level 3 (size 1 to 2):

Merge $[10]$ and $[7] \to [7, 10]$ . Not void ( $10 > 7$ ).
Merge $[8]$ and $[19] \to [8, 19]$ . Void ( $8 \leq 19$ ). (Count = 1)
Merge $[41]$ and $[35] \to [35, 41]$ . Not void ( $41 > 35$ ).
Merge $[25]$ and $[31] \to [25, 31]$ . Void ( $25 \leq 31$ ). (Count = 2)

Step 3: Level 2 (size 2 to 4):

Merge $[7, 10]$ and $[8, 19] \to [7, 8, 10, 19]$ . Not void ( $10 > 8$ ).
Merge $[35, 41]$ and $[25, 31] \to [25, 31, 35, 41]$ . Not void ( $41 > 25$ ).

Step 4: Level 1 (size 4 to 8):

Merge $[7, 8, 10, 19]$ and $[25, 31, 35, 41] \to [7, 8, 10, 19, 25, 31, 35, 41]$ . Void ( $19 \leq 25$ ). (Count = 3)

Step 5: Total void merges = 3.

Answer: 3

Question 2 · Algorithms · 2026_Set2 MCQ

Consider an array

A

of integers of size

n

. The indices of

A

run from

1

n

. An algorithm is to be designed to check whether

A

satisfies the condition given below.

\forall i, j \in {1, \dots, n - 1} such that i > j, (A [i + 1] - A [i]) > (A [j + 1] - A [j])

Which one of the following gives the worst case time complexity of the fastest algorithm that can be designed for the problem?

A.
$Θ (n)$
B.
$Θ (lo g (n))$
C.
$Θ (n lo g (n))$
D.
$Θ (n^{2})$

Correct Answer:

Step-by-Step Solution

Key idea: The condition implies that the sequence of differences between adjacent elements is strictly increasing. This can be verified in a single pass.

Step 1: Decode the mathematical condition.

The condition is: $\forall i, j \in {1, \dots, n - 1}$ such that $i > j$ , $(A [i + 1] - A [i]) > (A [j + 1] - A [j])$ .
Let $D [k] = A [k + 1] - A [k]$ be the difference between adjacent elements.
The condition states: If $i > j$ , then $D [i] > D [j]$ .
This means the sequence of differences $D [1], D [2], \dots, D [n - 1]$ must be strictly increasing.
In other words, $D [1] < D [2] < D [3] < \dots < D [n - 1]$ .

Step 2: Design the algorithm.

We need to check if the array $D$ is strictly sorted in ascending order.
We can compute $D [k]$ on the fly.
Iterate $k$ from $1$ to $n - 2$ (indices for $D$ ).
Check if $D [k] < D [k + 1]$ .
Substitute back: Check if $(A [k + 1] - A [k]) < (A [k + 2] - A [k + 1])$ .

Step 3: Analyze complexity.

We iterate through the array once from $1$ to $n - 2$ .
Each step involves constant time arithmetic and comparison.
Total time: $O (n)$ .

Step 4: Verify lower bound.

We must inspect every element at least once to ensure the property holds globally. Thus, $Ω (n)$ is the lower bound.
Since we have an $O (n)$ algorithm, the tight bound is $Θ (n)$ .

Answer: A

Question 3 · Algorithms · 2025_Set2 MCQ

Consider an unordered list of

N

distinct integers.

What is the minimum number of element comparisons required to find an integer in the list that is NOT the largest in the list?

A.
1
B.
$N - 1$
C.
$N$
D.
$2 N - 1$

Correct Answer:

Step-by-Step Solution

Key idea: To find an element that is NOT the largest, we only need to ensure we pick an element that lost at least one comparison. We can do this with just 1 comparison.

Step 1: Analyze the requirement. We need to output any integer from the list that is not the maximum. We do not need to find the minimum, nor the second largest, nor sort the list.

Step 2: Consider the smallest case. Let $N = 2$ . The elements are $a$ and $b$ .

Compare $a$ and $b$ .
If $a < b$ , then $a$ is not the largest. Output $a$ .
If $b < a$ , then $b$ is not the largest. Output $b$ .
In either case, 1 comparison is sufficient to identify a non-maximum element.

Step 3: Generalize to $N > 2$ .

Pick any two elements, say $A [1]$ and $A [2]$ .
Compare them.
The smaller of the two is definitely not the largest element in the entire list (because the other one is larger than it, so the smaller one cannot be the global maximum).
Thus, we have found an element that is not the largest.
Total comparisons: 1.

Step 4: Verify minimality.

Can we do it in 0 comparisons? No, because without comparing, we don't know the relative order, and any element we pick could potentially be the largest.
Therefore, 1 is the minimum.

Answer: A

Question 4 · Algorithms · 2025_Set2 MCQ

An array

A

of length

n

with distinct elements is said to be bitonic if there is an index

1 \leq i \leq n

such that

A [1.. i]

is sorted in the non-decreasing order and

A [i + 1.. n]

is sorted in the non-increasing order.

Which ONE of the following represents the best possible asymptotic bound for the worst-case number of comparisons by an algorithm that searches for an element in a bitonic array

A

A.
$Θ (n)$
B.
$Θ (1)$
C.
$Θ (lo g^{2} n)$
D.
$Θ (lo g n)$

Correct Answer:

Step-by-Step Solution

Key idea: A bitonic array consists of a sorted ascending part followed by a sorted descending part. We can search in $O (lo g n)$ by first finding the peak and then performing binary search on both halves.

Step 1: Understand the structure. A bitonic array increases to a peak element and then decreases. Let the peak index be $p$ .

Subarray $A [1 \dots p]$ is sorted in non-decreasing order.
Subarray $A [p \dots n]$ is sorted in non-increasing order.

Step 2: Find the peak. We can find the peak element in $O (lo g n)$ time using a modified binary search.

Compare $A [mi d]$ with $A [mi d + 1]$ .
If $A [mi d] < A [mi d + 1]$ , the peak is in the right half.
If $A [mi d] > A [mi d + 1]$ , the peak is in the left half (including mid).
This takes $O (lo g n)$ comparisons.

Step 3: Search for the element. Once the peak $p$ is found:

Perform standard binary search on $A [1 \dots p]$ (ascending). This takes $O (lo g n)$ .
Perform modified binary search on $A [p \dots n]$ (descending). This also takes $O (lo g n)$ .

Step 4: Total complexity.

Finding peak: $O (lo g n)$ .
Searching left part: $O (lo g n)$ .
Searching right part: $O (lo g n)$ .
Total: $O (lo g n) + O (lo g n) + O (lo g n) = O (lo g n)$ .

Step 5: Compare with options.

$Θ (n)$ is linear search (too slow).
$Θ (1)$ is impossible for unsorted/search problems without preprocessing.
$Θ (lo g^{2} n)$ is slower than necessary.
$Θ (lo g n)$ is the tight bound.

Answer: D

Question 5 · Algorithms · 2025_Set1 NAT

The pseudocode of a function fun() is given below:

fun(int A[0,…,n-1]){
for i=0 to n-2
for j=0 to n-i-2
if (A[j]>A[j+1])
then swap A[j] and A[j+1]

}

Let

A [0, \dots, 29]

be an array storing 30 distinct integers in descending order. The number of swap operations that will be performed, if the function fun() is called with

A [0, \dots, 29]

as argument, is __________. (Answer in integer)

Correct Answer:

435

Step-by-Step Solution

Key idea: This is a sorting algorithm operation counting question, recognisable because it provides pseudocode and asks for the number of swap operations. The added layer is identifying the algorithm and its behavior on a specific input (reverse sorted).

Step 1: Analyze the pseudocode. The outer loop runs for $i$ from $0$ to $n - 2$ . The inner loop runs for $j$ from $0$ to $n - i - 2$ . Inside, it swaps $A [j]$ and $A [j + 1]$ if $A [j] > A [j + 1]$ .

Step 2: Recognize this as the standard Bubble Sort algorithm.

Step 3: The input array $A$ has $n = 30$ distinct integers in descending order. This is the worst-case input for Bubble Sort.

Step 4: In the worst case, every comparison $A [j] > A [j + 1]$ evaluates to true, so a swap is performed every time.

Step 5: Calculate the total number of comparisons (and thus swaps).

For $i = 0$ , $j$ goes from $0$ to $n - 2$ (which is $n - 1$ iterations).

For $i = 1$ , $j$ goes from $0$ to $n - 3$ (which is $n - 2$ iterations).

...

For $i = n - 2$ , $j$ goes from $0$ to $0$ (which is $1$ iteration).

Step 6: Total swaps = $(n - 1) + (n - 2) + \dots + 1 = \frac{n ( n - 1 )}{2}$ .

Step 7: Substitute $n = 30$ : Total swaps = $\frac{30 \times 29}{2} = 15 \times 29 = 435$ .

Answer: 435

Question 6 · Algorithms · 2024_Set1 MCQ

Given an integer array of size $N$ , we want to check if the array is sorted (in either ascending or descending order). An algorithm solves this problem by making a single pass through the array and comparing each element of the array only with its adjacent elements. The worst-case time complexity of this algorithm is

A.
both $O (N)$ and $Ω (N)$
B.
$O (N)$ but not $Ω (N)$
C.
$Ω (N)$ but not $O (N)$
D.
neither $O (N)$ nor $Ω (N)$

Correct Answer:

Step-by-Step Solution

Key idea: This is a linear-time array property verification question, recognisable because it asks for the worst-case time complexity of an algorithm that checks a global property (sorted order) using a single pass and adjacent comparisons.

Step 1: Analyze the algorithm's description. It makes a "single pass through the array".

Step 2: In a single pass, the algorithm compares each element with its adjacent element. For an array of size $N$ , there are exactly $N - 1$ adjacent pairs.

Step 3: Therefore, the algorithm performs exactly $N - 1$ comparisons, regardless of the input array's content.

Step 4: A function that performs exactly $c \cdot N + d$ operations (where $c$ and $d$ are constants) has a time complexity of $Θ (N)$ .

Step 5: By definition, $Θ (N)$ means the complexity is bounded both above and below by $N$ . Thus, it is both $O (N)$ (upper bound) and $Ω (N)$ (lower bound).

Answer: A

Question 7 · Algorithms · 2023 MCQ

An algorithm has to store several keys generated by an adversary in a hash table. The adversary is malicious who tries to maximize the number of collisions. Let

k

be the number of keys,

m

be the number of slots in the hash table, and

k > m

.

Which one of the following is the best hashing strategy to counteract the adversary?

A.
Division method, i.e., use the hash function $h (k) = k mod m$ .
B.
Multiplication method, i.e., use the hash function $h (k) = ⌊ m (k A - ⌊ k A ⌋) ⌋$ , where $A$ is a carefully chosen constant.
C.
Universal hashing method.
D.
If $k$ is a prime number, use Division method. Otherwise, use Multiplication method.

Correct Answer:

Step-by-Step Solution

Key idea: Adversarial inputs defeat deterministic hashing. Universal hashing uses randomization to prevent the adversary from predicting collisions.

Step 1: Analyze the threat. The adversary knows the hash function and tries to maximize collisions. If the hash function is fixed (like Division or Multiplication method with fixed constants), the adversary can simply choose keys that all map to the same slot. For example, if $h (k) = k (mod m)$ , the adversary picks ${0, m, 2 m, \dots}$ . This results in $O (k)$ worst-case time for operations.

Step 2: Evaluate Division Method. It is deterministic. Once $m$ is known, the adversary can easily construct a worst-case input. Thus, it is not robust against a malicious adversary.

Step 3: Evaluate Multiplication Method. It depends on a constant $A$ . If $A$ is fixed and known, the adversary can still analyze the function and find collisions. While it distributes keys better for random data, it does not provide theoretical guarantees against an adversary who knows $A$ .

Step 4: Evaluate Universal Hashing. In universal hashing, we select a hash function $h$ randomly from a family $H$ at runtime. The adversary does not know which specific $h$ was chosen. By definition of a universal family, for any two distinct keys $x$ and $y$ , the probability of collision $P r [h (x) = h (y)] \leq 1/ m$ . This ensures that the expected number of collisions remains low, regardless of the adversary's strategy.

Step 5: Conclusion. Universal hashing is the only strategy among the options that provides probabilistic guarantees against an adversary by introducing randomness unknown to the attacker.

Answer: C

Question 8 · Algorithms · 2021_Set2 MCQ

What is the worst-case number of arithmetic operations performed by recursive binary search on a sorted array of size $n$ ?

A.
$Θ (n)$
B.
$Θ (lo g_{2} (n))$
C.
$Θ (n^{2})$
D.
$Θ (n)$

Correct Answer:

Step-by-Step Solution

Key idea: Recursive binary search divides the problem size by 2 in each step. The depth of the recursion tree determines the number of operations.

Step 1: Analyze the algorithm.

Binary search on a sorted array of size $n$ .
In each recursive call, we calculate the middle index and compare the target with the middle element.
Based on the comparison, we recurse on either the left half or the right half.
The size of the problem reduces from $n$ to $n /2$ .

Step 2: Formulate the recurrence.

Let $T (n)$ be the number of arithmetic operations/comparisons.
$T (n) = T (n /2) + O (1)$ .
The $O (1)$ term accounts for calculating mid and the comparison.

Step 3: Solve the recurrence.

This is a standard recurrence solved by the Master Theorem or iteration.
Depth of recursion = $lo g_{2} n$ .
At each level, constant work is done.
Total operations $\propto lo g_{2} n$ .

Step 4: Determine the asymptotic bound.

Worst-case occurs when the element is not present or is at a leaf.
Number of steps = $⌊ lo g_{2} n ⌋ + 1$ .
This is $Θ (lo g_{2} n)$ .

Step 5: Match with options.

Option B is $Θ (lo g_{2} n)$ .

Answer: B

Question 9 · Algorithms · 2021_Set1 MCQ

Consider the following array.

Which algorithm out of the following options uses the least number of comparisons (among the array elements) to sort the above array in ascending order?

A.
Selection sort
B.
Mergesort
C.
Insertion sort
D.
Quicksort using the last element as pivot

Correct Answer:

Step-by-Step Solution

Key idea: This is a sorting algorithm operation counting question, recognisable because it provides a specific array and asks which algorithm uses the least number of comparisons. The added layer is recognizing the initial state of the array.

Step 1: Observe the given array: $[23, 32, 45, 69, 72, 73, 89, 97]$ .

Step 2: Notice that the array is already sorted in ascending order. Let $n = 8$ .

Step 3: Evaluate each option for an already sorted array:

Selection sort: Always performs $\frac{n ( n - 1 )}{2}$ comparisons regardless of input order. For $n = 8$ , this is $\frac{8 \times 7}{2} = 28$ comparisons.
Mergesort: Always performs $Θ (n lo g n)$ comparisons. For $n = 8$ , it is around $8 \times 3 = 24$ comparisons (specifically, 17 to 21 depending on implementation).
Insertion sort: For an already sorted array, the inner loop condition fails immediately on the first check for each element. It performs exactly $n - 1$ comparisons. For $n = 8$ , this is $7$ comparisons.
Quicksort (last element as pivot): For an already sorted array, this is the worst-case scenario. It performs $\frac{n ( n - 1 )}{2}$ comparisons. For $n = 8$ , this is 28 comparisons.

Step 4: Compare the counts: $7$ (Insertion) is the least.

Answer: C

Question 10 · Algorithms · 2021_Set1 MCQ

Let $P$ be an array containing $n$ integers. Let $t$ be the lowest upper bound on the number of comparisons of the array elements, required to find the minimum and maximum values in an arbitrary array of $n$ elements. Which one of the following choices is correct?

A.
$t > 2 n - 2$
B.
$t > 3 ⌈ \frac{n}{2} ⌉$ and $t \leq 2 n - 2$
C.
$t > n$ and $t \leq 3 ⌈ \frac{n}{2} ⌉$
D.
$t > ⌈ lo g_{2} (n) ⌉$ and $t \leq n$

Correct Answer:

Step-by-Step Solution

Key idea: This is a comparison bounds question, recognisable because it asks for the lowest upper bound on the number of comparisons required to find both the minimum and maximum values simultaneously.

Step 1: The naive approach finds the minimum in $n - 1$ comparisons and the maximum in another $n - 1$ comparisons, totaling $2 n - 2$ comparisons.

Step 2: The optimal approach processes elements in pairs. Divide the $n$ elements into $⌈ n /2 ⌉$ pairs.

Step 3: Compare the two elements within each pair. This takes $⌈ n /2 ⌉$ comparisons and yields a local minimum and a local maximum for each pair.

Step 4: Find the global minimum by comparing the $⌈ n /2 ⌉$ local minimums. This takes $⌈ n /2 ⌉ - 1$ comparisons.

Step 5: Find the global maximum by comparing the $⌈ n /2 ⌉$ local maximums. This takes $⌈ n /2 ⌉ - 1$ comparisons.

Step 6: Total comparisons $t = ⌈ n /2 ⌉ + 2 (⌈ n /2 ⌉ - 1) = 3 ⌈ n /2 ⌉ - 2$ .

Step 7: This value is strictly less than or equal to $3 ⌈ n /2 ⌉$ . For $n \geq 3$ (with the minor exception of $n = 4$ where it equals $n$ ), it is greater than $n$ . Among the choices, Option C is the only one that correctly bounds the optimal count from above by $3 ⌈ n /2 ⌉$ and generally satisfies the lower bound for meaningful array sizes.

Answer: C

Try a question

Login to view the complete previous-year questions and solutions

Personalised first. High quality throughout.

Built around you, not around a syllabus PDF

Revision that hits your weak spots

Questions calibrated to the real exam

Notes written for recall, not for volume

One place for everything

Honest progress

Unlock the whole course

Searching, Sorting, Selection and Hashing PYQs for GATE CS

Chapter Roadmap: Searching, Sorting, Selection and Hashing

Chapter Roadmap: Searching, Sorting, Selection and Hashing

Sorting Algorithms and Operation Counts

Sorting Algorithms and Operation Counts

What you will learn here:

Searching, Sorting, Selection and Hashing: Solved Questions with Step-by-Step Explanations (10 Problems)

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

More previous year questions (pyqs) in this unit