Consider the array A[]= {6,4,8,1,3} apply the insertion sort to sort the array . Consider the cost associated with each sort is 25 rupees , what is the total cost of the insertion sort when element 1 reaches the first position of the array?a)50b)25c)75d)100Correct answer is option 'A'. Can you explain this answer?

Question

Answer

Solution:

Insertion Sort:
Insertion sort is a simple sorting algorithm that works the way we sort playing cards in our hands. We pick up the cards in order and place them in the correct position.

Steps to perform Insertion Sort:
1. Iterate from the second element of the array to n, where n is the size of the array.
2. Compare the current element with the elements before it, and keep on swapping the elements until the current element is in the correct position.
3. Repeat the above steps for all the elements in the array.

Given Array: A[]= {6,4,8,1,3}
After applying insertion sort, the array becomes:
A[]= {1,3,4,6,8}

Total Cost:
We have to calculate the total cost of the insertion sort when element 1 reaches the first position of the array. It means that we need to calculate the cost of sorting the elements until the element 1 reaches the first position.

The steps to perform the insertion sort are:

1. 6 and 4 are compared and swapped. Array becomes {4,6,8,1,3}. Cost = 25.
2. 6 and 8 are compared, no swap required. Array remains {4,6,8,1,3}. Cost = 0.
3. 8 and 1 are compared and swapped. Array becomes {4,6,1,8,3}. Cost = 25.
4. 6 and 1 are compared and swapped. Array becomes {4,1,6,8,3}. Cost = 25.
5. 4 and 1 are compared and swapped. Array becomes {1,4,6,8,3}. Cost = 25.
6. 8 and 3 are compared and swapped. Array becomes {1,4,6,3,8}. Cost = 25.
7. 6 and 3 are compared and swapped. Array becomes {1,4,3,6,8}. Cost = 25.
8. 4 and 3 are compared and swapped. Array becomes {1,3,4,6,8}. Cost = 25.

So, the total cost of the insertion sort when element 1 reaches the first position of the array is 25+0+25+25+25+25+25+25 = 175.

Answer:
The correct answer is option A) 50. However, this answer is incorrect as the calculation of the cost of sorting is done incorrectly. The correct total cost of the insertion sort is 175.

Answer

In insertion sort numbers are compared and arranged firstly when 6 and 8 are compared first time sorting process happens so initial cost is 25 then 6 and 8 are compared they are already in order then again sorting happens to move 1 to the first place so the total cost is 50

Similar Computer Science Engineering (CSE) Doubts

Consider a double-ended queue with elements 31, 17, 4, 22, 19, 8. What is the time complexity of deletion of last element i.e. 8 and insertion of new element 10 at the rear?

Consider an array of elements arr[5]= {5,4,3,2,1} , what are the steps of insertions done while doing insertion sort in the array.

Top Courses for Computer Science Engineering (CSE)View all

GATE Computer Science Engineering(CSE) 2025 Mock Test Series

Question Bank for GATE Computer Science Engineering

General Aptitude for GATE

Computer Networks

Programming and Data Structures

Top Courses for Computer Science Engineering (CSE)

Top Courses for Computer Science Engineering (CSE)

Suggested Free Tests

Related Content

Mock Test Series

Subject-wise Courses

Subject-wise Courses

Other Engg Branches

Company