GATE Exam  >  GATE Questions  >  Consider the following statements:i. Selectio... Start Learning for Free
Consider the following statements:
i. Selection sort performs minimum number of swaps.
ii. Insertion sort performs worst in case of sorted array.
iii. Floyd Warshall uses dynamic programming to calculate all pairs of shortest paths
Q. Which of the statements are true?
  • a)
    i and ii
  • b)
    ii and iii
  • c)
    i and iii
  • d)
    i, ii and iii
Correct answer is option 'C'. Can you explain this answer?
Verified Answer
Consider the following statements:i. Selection sort performs minimum n...
Selection sort uses minimum number of swaps. In each pass, there can be at most 1 swap. So there can be at most n swaps in worst case.
In case of insertion sort, if every element is less than every element to its left, the running time of insertion sort is Θ(n2). Thus insertion sort is worst for reverse sorted data. Floyd Warshall algorithm uses dynamic programming for all pairs of shortest path computation.
View all questions of this test
Most Upvoted Answer
Consider the following statements:i. Selection sort performs minimum n...
Statement i: Selection sort performs minimum number of swaps.
Statement ii: Insertion sort performs worst in case of sorted array.
Statement iii: Floyd Warshall uses dynamic programming to calculate all pairs of shortest paths.

Explanation:
Let's analyze each statement one by one:

Statement i: Selection sort performs minimum number of swaps.
Selection sort works by repeatedly finding the minimum element from the unsorted part of the array and swapping it with the element at the beginning of the unsorted part. This process is repeated until the entire array is sorted.

In selection sort, the minimum number of swaps required is equal to the number of inversions in the array. An inversion occurs when two elements in the array are out of order. Since selection sort always selects the smallest element and moves it to the beginning, it only swaps when it encounters an inversion. Therefore, selection sort performs the minimum number of swaps among all comparison-based sorting algorithms.

Statement ii: Insertion sort performs worst in case of sorted array.
Insertion sort works by dividing the array into a sorted and an unsorted part. It iterates through the unsorted part, selects each element, and inserts it into its correct position in the sorted part by shifting the elements. This process is repeated until the entire array is sorted.

In the case of a sorted array, insertion sort performs the worst because it has to compare each element with all the elements in the sorted part before finding its correct position. This results in a time complexity of O(n^2) as each element may need to be compared with all the previous elements.

Statement iii: Floyd Warshall uses dynamic programming to calculate all pairs of shortest paths.
Floyd Warshall algorithm is a dynamic programming algorithm used to find the shortest paths between all pairs of vertices in a weighted directed graph. It uses a 2D matrix to store the distances between each pair of vertices.

The algorithm initializes the matrix with the direct distances between vertices and gradually updates the matrix by considering intermediate vertices. It iterates through all possible intermediate vertices and checks if using the intermediate vertex can lead to a shorter path between two vertices. If so, it updates the distance in the matrix.

Floyd Warshall algorithm has a time complexity of O(V^3), where V is the number of vertices in the graph. It is based on the principle of dynamic programming, where the optimal solution is built by solving subproblems and gradually solving larger subproblems until the complete solution is obtained.

Conclusion:
From the explanations above, we can conclude that:
- Statement i is true as selection sort performs the minimum number of swaps.
- Statement ii is true as insertion sort performs worst in the case of a sorted array.
- Statement iii is false as Floyd Warshall uses dynamic programming to calculate all pairs of shortest paths.
Explore Courses for GATE exam

Similar GATE Doubts

Consider the following statements:i. Selection sort performs minimum number of swaps.ii. Insertion sort performs worst in case of sorted array.iii. Floyd Warshall uses dynamic programming to calculate all pairs of shortest pathsQ. Which of the statements are true?a)i and iib)ii and iiic)i and iiid)i, ii and iiiCorrect answer is option 'C'. Can you explain this answer?
Question Description
Consider the following statements:i. Selection sort performs minimum number of swaps.ii. Insertion sort performs worst in case of sorted array.iii. Floyd Warshall uses dynamic programming to calculate all pairs of shortest pathsQ. Which of the statements are true?a)i and iib)ii and iiic)i and iiid)i, ii and iiiCorrect answer is option 'C'. Can you explain this answer? for GATE 2024 is part of GATE preparation. The Question and answers have been prepared according to the GATE exam syllabus. Information about Consider the following statements:i. Selection sort performs minimum number of swaps.ii. Insertion sort performs worst in case of sorted array.iii. Floyd Warshall uses dynamic programming to calculate all pairs of shortest pathsQ. Which of the statements are true?a)i and iib)ii and iiic)i and iiid)i, ii and iiiCorrect answer is option 'C'. Can you explain this answer? covers all topics & solutions for GATE 2024 Exam. Find important definitions, questions, meanings, examples, exercises and tests below for Consider the following statements:i. Selection sort performs minimum number of swaps.ii. Insertion sort performs worst in case of sorted array.iii. Floyd Warshall uses dynamic programming to calculate all pairs of shortest pathsQ. Which of the statements are true?a)i and iib)ii and iiic)i and iiid)i, ii and iiiCorrect answer is option 'C'. Can you explain this answer?.
Solutions for Consider the following statements:i. Selection sort performs minimum number of swaps.ii. Insertion sort performs worst in case of sorted array.iii. Floyd Warshall uses dynamic programming to calculate all pairs of shortest pathsQ. Which of the statements are true?a)i and iib)ii and iiic)i and iiid)i, ii and iiiCorrect answer is option 'C'. Can you explain this answer? in English & in Hindi are available as part of our courses for GATE. Download more important topics, notes, lectures and mock test series for GATE Exam by signing up for free.
Here you can find the meaning of Consider the following statements:i. Selection sort performs minimum number of swaps.ii. Insertion sort performs worst in case of sorted array.iii. Floyd Warshall uses dynamic programming to calculate all pairs of shortest pathsQ. Which of the statements are true?a)i and iib)ii and iiic)i and iiid)i, ii and iiiCorrect answer is option 'C'. Can you explain this answer? defined & explained in the simplest way possible. Besides giving the explanation of Consider the following statements:i. Selection sort performs minimum number of swaps.ii. Insertion sort performs worst in case of sorted array.iii. Floyd Warshall uses dynamic programming to calculate all pairs of shortest pathsQ. Which of the statements are true?a)i and iib)ii and iiic)i and iiid)i, ii and iiiCorrect answer is option 'C'. Can you explain this answer?, a detailed solution for Consider the following statements:i. Selection sort performs minimum number of swaps.ii. Insertion sort performs worst in case of sorted array.iii. Floyd Warshall uses dynamic programming to calculate all pairs of shortest pathsQ. Which of the statements are true?a)i and iib)ii and iiic)i and iiid)i, ii and iiiCorrect answer is option 'C'. Can you explain this answer? has been provided alongside types of Consider the following statements:i. Selection sort performs minimum number of swaps.ii. Insertion sort performs worst in case of sorted array.iii. Floyd Warshall uses dynamic programming to calculate all pairs of shortest pathsQ. Which of the statements are true?a)i and iib)ii and iiic)i and iiid)i, ii and iiiCorrect answer is option 'C'. Can you explain this answer? theory, EduRev gives you an ample number of questions to practice Consider the following statements:i. Selection sort performs minimum number of swaps.ii. Insertion sort performs worst in case of sorted array.iii. Floyd Warshall uses dynamic programming to calculate all pairs of shortest pathsQ. Which of the statements are true?a)i and iib)ii and iiic)i and iiid)i, ii and iiiCorrect answer is option 'C'. Can you explain this answer? tests, examples and also practice GATE tests.
Explore Courses for GATE exam
Signup for Free!
Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.
10M+ students study on EduRev