Consider the following array.

23 |
32 |
45 |
69 |
72 |
73 |
89 |
97 |

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

This question was previously asked in

GATE CS 2021 Official Paper: Shift 1

- Insertion sort
- Selection sort
- Quicksort using the last element as pivot
- Merge sort

Option 1 : Insertion sort

Free

ST 1: General Awareness

6945

15 Questions
15 Marks
15 Mins

__Insertion sort:__

In Insertion sort, the best-case takes Θ (n) time, the best case of insertion sort is when elements are sorted in ascending order. In that case, the number of comparisons will be **n - 1 = 8 - 1 = 7**

It is the least number of comparisons (among the array elements) to sort the above array in ascending order:

The number of swaps needed is zero.

__Additional Information__

In Insertion sort, the worst-case takes Θ (n2) time, the worst case of insertion sort is when elements are sorted in reverse order. In that case the number of comparisons will be like:

\(\mathop \sum \limits_{{\rm{p}} = 1}^{{\rm{N}} - 1} {\rm{p}} = 1 + 2 + 3 + \ldots . + {\rm{N}} - 1 = {\rm{\;}}\frac{{{\rm{N}}\left( {{\rm{N}} - 1} \right)}}{2} - 1\)

This will give Θ (n2) time complexity.

India’s **#1 Learning** Platform

Start Complete Exam Preparation

Daily Live MasterClasses

Practice Question Bank

Mock Tests & Quizzes

Trusted by 2,17,58,055+ Students

Start your FREE coaching now >>

Testbook Edu Solutions Pvt. Ltd.

1st & 2nd Floor, Zion Building,

Plot No. 273, Sector 10, Kharghar,

Navi Mumbai - 410210

[email protected]
Plot No. 273, Sector 10, Kharghar,

Navi Mumbai - 410210

Toll Free:1800 833 0800

Office Hours: 10 AM to 7 PM (all 7 days)