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
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.