chapter

Searching, Sorting, Selection and Hashing Short Notes for GATE CS

Searching, Sorting, Selection and Hashing short notes for GATE CS: 5 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice q

searching sorting selection and hashing short notes

Sorting Operation Cheat Sheet

Quick Reference: Sorting Operation Counts Algorithm Best Case Comparisons Worst Case Comparisons Worst Case Data Movements Bubble Sort Θ (n) Θ (n^{2}) Θ (n^{2}) (Swaps = Inversions) Insertion Sort Θ (n) Θ (n^{2}) Θ (n^{2}) (Shifts = Inversions) Selection Sort Θ (n^{2}) Θ (n^{2}) Θ (n) (Exactly n - 1 swaps) Merge Sort Θ (n lo g n) Θ (n lo g n) Θ (n lo g n) (n - 1 total merges) Quick Sort Θ (n lo g n) Θ (n^{2}) Θ (n^{2}) Core Rules for Exam Analysis: Inversions dictate adaptive sorts: For Bubble and Insertion sort, count inversions to find exact swaps/shifts. Selection sort is rigid: Comparisons are always \frac{n ( n - 1 )}{2} . Void Merge condition: max (L) \leq min (R) . Loop bound math: 0 to K inclusive = K + 1 iterations.

Binary and Bitonic Search Cheat Sheet

Quick Reference: Binary and Bitonic Search Operation Time Complexity Key Condition / Formula Standard Binary Search mid = low + (high - low) / 2 Find Bitonic Peak If A[\text{mid}] &lt; A[\text{mid}+1], low = mid + 1 Bitonic Array Search 1. Find peak. 2. Ascending BS on left. 3. Descending BS on right. Exam Readiness Rules: Distinct Elements: The peak finding relies on the array having distinct elements (or strict inequalities). If duplicates are allowed, worst-case can degrade to . Boundary Checks: Always ensure mid + 1 does not go out of bounds when checking A[\text{mid}] &lt; A[\text{mid}+1]. Recursive Arithmetic: For recursive binary search, the number of arithmetic operations (additions, divisions) is proportional to the depth of the recursion tree, which is .

Comparison Bounds Cheat Sheet

.smart-card { font-family: system-ui, -apple-system, sans-serif; color: var(--color-text); background: var(--color-bg); border: 1px solid var(--color-border); border-radius: 16px; padding: 24px; box-sizing: border-box; width: 100%; max-width: 100%; overflow: hidden; } .smart-card * { box-sizing: border-box; } .smart-card h2 { font-size: 1.25rem; color: var(--color-primary); margin: 0 0 16px 0; border-bottom: 2px solid var(--color-border); padding-bottom: 8px; } .smart-card h3 { font-size: 1rem; color: var(--color-text); margin: 20px 0 10px 0; } .smart-card p, .smart-card li { font-size: 0.95rem; line-height: 1.6; margin: 6px 0; } .smart-card ol { padding-left: 20px; } .smart-card table { width: 100%; border-collapse: collapse; margin: 12px 0; font-size: 0.9rem; } .smart-card th, .smart-card td { border: 1px solid var(--color-border); padding: 10px; text-align: left; } .smart-card th { background: color-mix(in srgb, var(--color-primary) 10%, transparent); font-weight: 600; color: var(--color-primary); } .smart-card .rule-box { background: color-mix(in srgb, var(--color-muted) 10%, transparent); border-radius: 10px; padding: 14px; margin-top: 16px; } Quick Reference: Comparison Bounds Problem Optimal Comparisons Method / Condition Find Min (or Max) n - 1 Linear scan. Find Min AND Max ⌈ \frac{3 n}{2} ⌉ - 2 Pairwise comparison. Find 2nd Largest n + ⌈ lo g_{2} n ⌉ - 2 Tournament tree. Find k -th Smallest O (n) expected Quickselect (randomized pivot). Find k -th Smallest O (n) worst-case Median of Medians (deterministic). Exam Readiness Rules Read the prompt carefully: "Not the largest" \neq = "The smallest". Tournament tree logic: The runner-up must have lost directly to the champion. Median of Medians: Group size of 5 is the smallest odd number that guarantees the O (n) recurrence (1/5 + 7/10 < 1). Groups of 3 fail to guarantee linear time.

2 more cards in this chapter

Try a question

Answer it here to see how it works. Nothing is recorded until you sign in.

Question 1

Level 1: Warm-up

Which of the following classic sorting algorithms performs exactly the same number of comparisons regardless of whether the input array is already sorted, reverse sorted, or randomly ordered?

Question 2

Level 1: Warm-up

For an array of n distinct elements arranged in strictly descending (reverse sorted) order, what is the total number of inversions present in the array?

Question 3

Level 1: Warm-up

In the context of sorting algorithms, an "inversion" in an array A is defined as a pair of indices (i, j) such that:

Question 4

Level 1: Warm-up

What is the exact number of comparisons performed by the Insertion Sort algorithm in its best-case scenario (when the input array is already sorted in ascending order) for an array of size n ?

Question 5

Level 1: Warm-up

When sorting an array of n elements using the standard top-down Merge Sort algorithm, what is the total number of merge operations performed?

Question 6

Level 1: Warm-up

In Merge Sort, a merge operation between a sorted left subarray L and a sorted right subarray R is defined as "void" if max (L) \leq min (R) . During such a void merge operation, how many elements from R are placed before the first element of L in the merged output?

Question 7

Level 1: Warm-up

The "operation count fingerprint" of a sorting algorithm primarily helps a student to:

Question 8

Level 1: Warm-up

In the standard Bubble Sort algorithm, the total number of swap operations performed on an arbitrary array is exactly equal to which of the following?

Question 9

Level 1: Warm-up

For an array of n elements, how many comparisons does the standard Selection Sort algorithm perform, regardless of the initial order of the elements?

Question 10

Level 1: Warm-up

During a single partition step in the Quick Sort algorithm on a subarray of size k, how many comparisons are made between the array elements and the pivot?

Free preview ends here

Login to view the complete short notes

Creating an account is free. You get the rest of this chapter, step-by-step solutions, and a study plan built around the topics you are actually weak at.

Why MastersUp

Personalised first. High quality throughout.

Most platforms hand everyone the same content. Here the content moves with your performance, topic by topic.

Built around you, not around a syllabus PDF

Every answer you give moves your topic-level intelligence rate. The next question, the next revision card and tomorrow's plan all change with it.

Revision that hits your weak spots

We only revise topics you have actually attempted and are still below the safe bar on — never the same chapter on repeat.

Questions calibrated to the real exam

Each question carries a measured toughness. You are served a rung above your current level, so practice keeps stretching you.

Notes written for recall, not for volume

Full lesson cards for first study, curated short-note cards for the last mile — with derivations, traps and exam patterns marked.

One place for everything

Notes, chapter practice, previous-year questions, test series and full-length papers — all feeding one picture of your preparation.

Honest progress

No vanity streaks. Progress here means chapters mastered and accuracy that held up on harder questions.

Unlock the whole course

Full notes and short notes, the complete question bank with worked solutions, mock tests, full-length papers, and an adaptive plan that rebuilds itself as you improve.

View all plans Start free

Searching, Sorting, Selection and Hashing Short Notes for GATE CS

Searching, Sorting, Selection and Hashing short notes for GATE CS: 5 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice questions.

Sorting Operation Cheat Sheet

Quick Reference: Sorting Operation Counts

Algorithm	Best Case Comparisons	Worst Case Comparisons	Worst Case Data Movements
Bubble Sort	$Θ (n)$	$Θ (n^{2})$	$Θ (n^{2})$ (Swaps = Inversions)
Insertion Sort	$Θ (n)$	$Θ (n^{2})$	$Θ (n^{2})$ (Shifts = Inversions)
Selection Sort	$Θ (n^{2})$	$Θ (n^{2})$	$Θ (n)$ (Exactly $n - 1$ swaps)
Merge Sort	$Θ (n lo g n)$	$Θ (n lo g n)$	$Θ (n lo g n)$ ( $n - 1$ total merges)
Quick Sort	$Θ (n lo g n)$	$Θ (n^{2})$	$Θ (n^{2})$

Core Rules for Exam Analysis:

Inversions dictate adaptive sorts: For Bubble and Insertion sort, count inversions to find exact swaps/shifts.
Selection sort is rigid: Comparisons are always $\frac{n ( n - 1 )}{2}$ .
Void Merge condition: $max (L) \leq min (R)$ .
Loop bound math: 0 to K inclusive = $K + 1$ iterations.

Binary and Bitonic Search Cheat Sheet

Quick Reference: Binary and Bitonic Search

Operation	Time Complexity	Key Condition / Formula
Standard Binary Search	$O (lo g n)$	`mid = low + (high - low) / 2`
Find Bitonic Peak	$O (lo g n)$	If $A[\text{mid}] < A[\text{mid}+1]$ , `low = mid + 1`
Bitonic Array Search	$O (lo g n)$	1. Find peak. 2. Ascending BS on left. 3. Descending BS on right.

Exam Readiness Rules:

Distinct Elements: The $O (lo g n)$ peak finding relies on the array having distinct elements (or strict inequalities). If duplicates are allowed, worst-case can degrade to $O (n)$ .
Boundary Checks: Always ensure mid + 1 does not go out of bounds when checking $A[\text{mid}] < A[\text{mid}+1]$ .
Recursive Arithmetic: For recursive binary search, the number of arithmetic operations (additions, divisions) is proportional to the depth of the recursion tree, which is $O (lo g n)$ .

Comparison Bounds Cheat Sheet

Quick Reference: Comparison Bounds

Problem	Optimal Comparisons	Method / Condition
Find Min (or Max)	$n - 1$	Linear scan.
Find Min AND Max	$⌈ \frac{3 n}{2} ⌉ - 2$	Pairwise comparison.
Find 2nd Largest	$n + ⌈ lo g_{2} n ⌉ - 2$	Tournament tree.
Find $k$ -th Smallest	$O (n)$ expected	Quickselect (randomized pivot).
Find $k$ -th Smallest	$O (n)$ worst-case	Median of Medians (deterministic).

Exam Readiness Rules

Read the prompt carefully: "Not the largest" $\neq =$ "The smallest".
Tournament tree logic: The runner-up must have lost directly to the champion.
Median of Medians: Group size of 5 is the smallest odd number that guarantees the $O (n)$ recurrence ( $1/5 + 7/10 < 1$ ). Groups of 3 fail to guarantee linear time.

Linear Verification Cheat Sheet

Quick Reference: Linear Verification

Property to Verify	Optimal Strategy	Time Complexity
Sorted (Ascending)	Check $A [k] \leq A [k + 1]$ for all $k$ .	$O (N)$
Sorted (Either Direction)	Use `is_asc` and `is_desc` flags in one pass.	$O (N)$
Strictly Increasing Differences	Check $(A [k + 1] - A [k]) > (A [k] - A [k - 1])$ for all $k$ .	$O (N)$
Bitonic Array	Find peak, verify ascending before, descending after.	$O (N)$

Golden Rule

Global transitive properties $⟹$ Local adjacent checks $⟹$ Single Pass $O (N)$ .

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

Question 1 · Algorithms MCQ

Which of the following classic sorting algorithms performs exactly the same number of comparisons regardless of whether the input array is already sorted, reverse sorted, or randomly ordered?

A.
Insertion Sort
B.
Bubble Sort (with early termination flag)
C.
Selection Sort
D.
Quick Sort

Correct Answer:

Step-by-Step Solution

Key idea: This is a comparative operation count question, testing knowledge of which algorithms are "adaptive" versus "non-adaptive" in their comparison behavior.

Step 1: Insertion Sort is adaptive; it makes $n - 1$ comparisons on a sorted array but $\frac{n ( n - 1 )}{2}$ on a reverse sorted array.

Step 2: Bubble Sort with an early termination flag is adaptive; it makes $n - 1$ comparisons on a sorted array.

Step 3: Quick Sort's comparison count heavily depends on pivot selection and the initial order of the array.

Step 4: Selection Sort always scans the entire unsorted portion to find the minimum element, performing exactly $\frac{n ( n - 1 )}{2}$ comparisons in all cases.

Answer: C

Question 2 · Algorithms MCQ

For an array of $n$ distinct elements arranged in strictly descending (reverse sorted) order, what is the total number of inversions present in the array?

A.
$n$
B.
$n - 1$
C.
$r a c n (n - 1) 2$
D.
$r a c n (n + 1) 2$

Correct Answer:

Step-by-Step Solution

Key idea: This is a direct application of the inversion definition to a specific worst-case input configuration.

Step 1: In a strictly descending array, every element is greater than every element that appears after it.

Step 2: Therefore, every possible pair of indices $(i, j)$ with $i < j$ forms an inversion.

Step 3: The total number of such pairs in an array of size $n$ is given by the combination formula $(2 n) = \frac{n ( n - 1 )}{2}$ .

Answer: C

Question 3 · Algorithms MCQ

In the context of sorting algorithms, an "inversion" in an array $A$ is defined as a pair of indices $(i, j)$ such that:

A.
$i < j$ and $A [i] > A [j]$
B.
$i > j$ and $A [i] < A [j]$
C.
$i < j$ and $A [i] < A [j]$
D.
$i > j$ and $A [i] > A [j]$

Correct Answer:

Step-by-Step Solution

Key idea: This is a definition recall question, recognisable because it asks for the precise mathematical condition of an inversion.

Step 1: Recall that an inversion represents a pair of elements that are out of their natural sorted order.

Step 2: For elements to be out of order, the element appearing earlier in the array (smaller index $i$ ) must be strictly greater than the element appearing later (larger index $j$ ).

Step 3: Therefore, the conditions are $i < j$ (index order) and $A [i] > A [j]$ (value order).

Answer: A

Question 4 · Algorithms MCQ

What is the exact number of comparisons performed by the Insertion Sort algorithm in its best-case scenario (when the input array is already sorted in ascending order) for an array of size $n$ ?

A.
$0$
B.
$1$
C.
$n - 1$
D.
$\frac{n ( n - 1 )}{2}$

Correct Answer:

Step-by-Step Solution

Key idea: This is a direct recall question about Insertion Sort best-case behavior, recognisable because it specifies the "best-case scenario" and "already sorted" input.

Step 1: Recall how Insertion Sort works. It iterates through the array, taking one element at a time and inserting it into its correct position in the already sorted prefix.

Step 2: In the best case, the array is already sorted.

Step 3: For each element from index 1 to $n - 1$ , the algorithm compares it with the element immediately before it.

Step 4: Since the array is sorted, the condition $A [j] > A [j + 1]$ (or equivalent) fails immediately on the first comparison.

Step 5: This results in exactly 1 comparison per element for the $n - 1$ elements being processed, totaling $n - 1$ comparisons.

Answer: C

Question 5 · Algorithms MCQ

When sorting an array of $n$ elements using the standard top-down Merge Sort algorithm, what is the total number of merge operations performed?

A.
$lo g_{2} n$
B.
$n - 1$
C.
$n$
D.
$\frac{n ( n - 1 )}{2}$

Correct Answer:

Step-by-Step Solution

Key idea: This is a direct recall question about Merge Sort operation counts, recognisable because it asks for the total number of merge operations (not comparisons) for the entire sort.

Step 1: Recall the structure of top-down Merge Sort. It recursively divides the array into halves until subarrays of size 1 are reached.

Step 2: Each merge operation takes two sorted subarrays and combines them into one larger sorted subarray.

Step 3: Every merge operation reduces the total number of disjoint sorted subarrays by exactly 1.

Step 4: We start with $n$ subarrays of size 1. We want to end up with 1 sorted subarray of size $n$ .

Step 5: To go from $n$ subarrays to 1 subarray, we must perform exactly $n - 1$ merge operations, regardless of the tree shape.

Answer: B

Question 6 · Algorithms MCQ

In Merge Sort, a merge operation between a sorted left subarray $L$ and a sorted right subarray $R$ is defined as "void" if $max (L) \leq min (R)$ . During such a void merge operation, how many elements from $R$ are placed before the first element of $L$ in the merged output?

A.
0
B.
1
C.
$∣ L ∣$
D.
$∣ R ∣$

Correct Answer:

Step-by-Step Solution

Key idea: This is a definition and behavior recall question for a specific Merge Sort edge case.

Step 1: The condition $max (L) \leq min (R)$ means every element in the left subarray is less than or equal to every element in the right subarray.

Step 2: During the merge process, the algorithm will compare the front of $L$ and $R$ . Since all elements of $L$ are smaller, it will exhaust all elements of $L$ first.

Step 3: Only after $L$ is completely copied will the algorithm begin copying elements from $R$ . Thus, zero elements of $R$ are placed before any element of $L$ .

Answer: A

Question 7 · Algorithms MCQ

The "operation count fingerprint" of a sorting algorithm primarily helps a student to:

A.
Determine the exact programming language used to implement it.
B.
Predict its exact behavior and performance on a specific input without running the code.
C.
Identify the memory address of the array elements.
D.
Convert the algorithm into a recursive form.

Correct Answer:

Step-by-Step Solution

Key idea: This is a conceptual definition question about the purpose of algorithmic analysis via operation counting.

Step 1: An "operation count fingerprint" refers to the precise number of comparisons and data movements an algorithm makes.

Step 2: This count is deterministic for a given algorithm and a specific input configuration (e.g., sorted, reverse sorted, or a specific number of inversions).

Step 3: By knowing this fingerprint, one can mathematically predict the algorithm's runtime behavior and efficiency on that input without needing to execute the code.

Answer: B

Question 8 · Algorithms MCQ

In the standard Bubble Sort algorithm, the total number of swap operations performed on an arbitrary array is exactly equal to which of the following?

A.
The number of elements in the array
B.
The number of inversions in the array
C.
The total number of comparisons made
D.
The number of unique elements in the array

Correct Answer:

Step-by-Step Solution

Key idea: This is a direct recall question about Bubble Sort operation counts, recognisable because it asks for the exact mathematical equivalent of the number of swaps.

Step 1: Recall how Bubble Sort works. It repeatedly steps through the list and swaps adjacent elements if they are in the wrong order.

Step 2: Each swap corrects exactly one inversion (a pair of elements that are out of order).

Step 3: The algorithm terminates when no inversions remain. Therefore, the total number of swaps is exactly equal to the initial number of inversions in the array.

Answer: B

Question 9 · Algorithms MCQ

For an array of $n$ elements, how many comparisons does the standard Selection Sort algorithm perform, regardless of the initial order of the elements?

A.
$n - 1$
B.
$\frac{n ( n - 1 )}{2}$
C.
$n lo g_{2} n$
D.
$n^{2}$

Correct Answer:

Step-by-Step Solution

Key idea: This is a direct recall question about Selection Sort operation counts, recognisable because it asks for the fixed number of comparisons independent of input order.

Step 1: Recall how Selection Sort works. It finds the minimum element in the unsorted portion and swaps it into place.

Step 2: In the first pass, it makes $n - 1$ comparisons to find the minimum of $n$ elements.

Step 3: In the second pass, it makes $n - 2$ comparisons, and so on, down to 1 comparison in the final pass.

Step 4: The total number of comparisons is the sum of the first $n - 1$ integers: $(n - 1) + (n - 2) + \dots + 1 = \frac{n ( n - 1 )}{2}$ .

Step 5: This count is fixed and does not change whether the array is sorted, reverse sorted, or random.

Answer: B

Question 10 · Algorithms MCQ

During a single partition step in the Quick Sort algorithm on a subarray of size $k$ , how many comparisons are made between the array elements and the pivot?

A.
$k$
B.
$k - 1$
C.
$\frac{k ( k - 1 )}{2}$
D.
$k lo g_{2} k$

Correct Answer:

Step-by-Step Solution

Key idea: This is a direct recall question about Quick Sort partition mechanics, recognisable because it isolates a single partition step and asks for the comparison count.

Step 1: Recall the standard partition process (e.g., Lomuto or Hoare). One element is chosen as the pivot.

Step 2: The algorithm iterates through the remaining elements of the subarray to compare each one against the pivot to determine which side of the partition it belongs to.

Step 3: Since the pivot itself is not compared against itself, there are exactly $k - 1$ other elements in the subarray of size $k$ .

Step 4: Therefore, exactly $k - 1$ comparisons are made during that single partition step.

Answer: B

searching sorting selection and hashing short notes

Sorting Operation Cheat Sheet

Quick Reference: Sorting Operation Counts

Binary and Bitonic Search Cheat Sheet

Quick Reference: Binary and Bitonic Search

Comparison Bounds Cheat Sheet

Quick Reference: Comparison Bounds

Exam Readiness Rules

Try a question

Login to view the complete short notes

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 Short Notes for GATE CS

Sorting Operation Cheat Sheet

Quick Reference: Sorting Operation Counts

Binary and Bitonic Search Cheat Sheet

Quick Reference: Binary and Bitonic Search

Comparison Bounds Cheat Sheet

Quick Reference: Comparison Bounds

Exam Readiness Rules

Linear Verification Cheat Sheet

Quick Reference: Linear Verification

Golden Rule

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 short notes in this unit