Question Details

P = [1, 2, 3, 5, 4] Two sorting algo Binary sort (BS), Insertion sort (IS) apply. Let N1 be the total number of comparisons done by BS on the element of P and N2 be the total number of comparisons done by IS on the elements of P. Which of the following option is/are correct?

Options

A

IS on P perform only one swap.

B

N1 = 10, N2 = 4

C

N1 > N2

D

Both BS and IS on P will make at least one unnecessary comparison. (i.e. comparing element that are already in correct order)

Show Answer
Correct Answer
A IS on P perform only one swap.
C
N1 > N2
D Both BS and IS on P will make at least one unnecessary comparison. (i.e. comparing element that are already in correct order)

Solution :

The correct options are:
1. IS on P perform only one swap.
2. N1 > N2
3. Both BS and IS on P will make at least one unnecessary comparison. (i.e. comparing element that are already in correct order)

Let us analyze the behavior of both Insertion Sort (IS) and Binary Insertion Sort (BS) on the array P = [1, 2, 3, 5, 4] step-by-step.

1. Insertion Sort (IS) Analysis:
Initially, the sorted subarray is [1]. We insert elements one by one:
- Insert 2: We compare 2 with 1. Since 2 > 1, no swap is needed. Subarray becomes [1, 2]. (Comparisons = 1, Swaps = 0)
- Insert 3: We compare 3 with 2. Since 3 > 2, no swap is needed. Subarray becomes [1, 2, 3]. (Comparisons = 1, Swaps = 0)
- Insert 5: We compare 5 with 3. Since 5 > 3, no swap is needed. Subarray becomes [1, 2, 3, 5]. (Comparisons = 1, Swaps = 0)
- Insert 4: We compare 4 with 5. Since 4 < 5, we swap 4 and 5. Next, we compare 4 with 3. Since 4 > 3, we stop. Subarray becomes [1, 2, 3, 4, 5]. (Comparisons = 2, Swaps = 1)

Thus, for Insertion Sort:
Total number of comparisons, N2 = 1 + 1 + 1 + 2 = 5
Total number of swaps = 1 (only swapping 4 and 5)
This confirms the option: IS on P perform only one swap.

2. Binary Insertion Sort (BS) Analysis:
Binary Insertion Sort uses binary search to find the correct insertion position within the sorted prefix.
- Insert 2 into [1]: Search range is index [0, 0].
We compare 2 with index 0 (value 1). Since 2 > 1, position is found. (Comparisons = 1)
- Insert 3 into [1, 2]: Search range is index [0, 1].
First, mid is index 0 (value 1). We compare 3 with 1. Since 3 > 1, search range becomes [1, 1].
Next, mid is index 1 (value 2). We compare 3 with 2. Since 3 > 2, position is found. (Comparisons = 2)
- Insert 5 into [1, 2, 3]: Search range is index [0, 2].
First, mid is index 1 (value 2). We compare 5 with 2. Since 5 > 2, search range becomes [2, 2].
Next, mid is index 2 (value 3). We compare 5 with 3. Since 5 > 3, position is found. (Comparisons = 2)
- Insert 4 into [1, 2, 3, 5]: Search range is index [0, 3].
First, mid is index 1 (value 2). We compare 4 with 2. Since 4 > 2, search range becomes [2, 3].
Next, mid is index 2 (value 3). We compare 4 with 3. Since 4 > 3, search range becomes [3, 3].
Next, mid is index 3 (value 5). We compare 4 with 5. Since 4 < 5, position is found. (Comparisons = 3)

Thus, for Binary Insertion Sort:
Total number of comparisons, N1 = 1 + 2 + 2 + 3 = 8

Comparing the two comparison counts:
Since N1 = 8 and N2 = 5, we have:
N1 > N2
This confirms the option: N1 > N2.

3. Unnecessary Comparisons:
An unnecessary comparison occurs when we compare elements that are already in their correct relative order.
- In IS, comparing 2 with 1, 3 with 2, and 5 with 3 are comparisons of elements already in correct order.
- In BS, binary search performs comparisons such as comparing 3 with 1, which are also already in correct order.
Thus, both algorithms make at least one unnecessary comparison.

Transparent Access on Mindyard

Built for Learners & Educators Alike

Completely free for students. Educators & coaching institutes get 2 months free Pro trial to create tests.

FREE FOR STUDENTS

Practice & Learn Free for Students

Access unlimited practice questions, detailed step-by-step solutions, and exam study materials — completely free for students.

  • Unlimited mock tests & question bank practice
  • Full access to curated study library & formula notes
  • 100% free for students • No credit card required
2 MONTHS FREE TRIAL

Educators & Coaching Institutes

Create and conduct professional online assessments with AI question generation, tab proctoring, and comprehensive batch management.

  • AI question uploader & rapid test generator
  • Anti-cheating tab proctoring & performance reports
  • Full Pro access free for 60 days • No upfront commitment
Discover more resources

You may also like

Mock Tests

View All
  • CUET UG
  • intermediate
  • 1 hour

A comprehensive CUET UG Mathematics Question Paper with Solutions – 2 June 2023 (Shift 3) designed to help students practice and understand the actual CUET exam pattern. This paper covers important topics from Algebra, Calculus, Coordinate Geometry, Probability, Statistics, Matrices, Determinants, and Vectors, featuring a balanced mix of conceptual, numerical, and application-based questions. Detailed solutions are provided to strengthen problem-solving skills, improve conceptual clarity, and enhance calculation accuracy. Based on the CUET syllabus and previous year exam trends, this paper is ideal for practice, revision, self-assessment, time management, previous year analysis, and final preparation for upcoming CUET UG Mathematics examinations.

  • CUET UG
  • intermediate
  • 1 hour

A comprehensive CUET Accountancy Question Paper – 20 June 2023 (Shift 2) designed to help students practice and analyze previous year exam patterns for effective CUET preparation. This paper covers important topics including Accounting for Partnership Firms, Company Accounts, Financial Statements Analysis, Cash Flow Statements, Accounting Ratios, and Fundamental Accounting Principles. It features a balanced mix of conceptual, numerical, and application-based questions to strengthen accounting concepts, improve calculation accuracy, and enhance problem-solving skills. Based on the CUET exam structure and syllabus, this paper is ideal for practice, revision, self-assessment, time management, previous year analysis, and final preparation for upcoming CUET Accountancy examinations.

Ask AI Tutor
5 left
Q1 View Question & Options
AI Tutor is solving this question...
Reading question context & options...
Ask your own doubt or choose a quick prompt: