0 votes 0 votes which of the following methods will be the best if number of swappings done, is the only measure of efficiency? A) Bubble sort B) Selection sort C) Insertion sort D) Quick sort Algorithms sorting quick-sort ace-test-series + – iita asked Jan 30, 2017 • retagged Jun 23, 2022 by Lakshman Bhaiya iita 691 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 1 votes 1 votes Answer is selection sort. In worst case only O(n) swaps. Also in best and average case no other method can have less number of swaps then selection sort. Rahul Jain25 answered Jan 30, 2017 • selected Mar 20, 2017 by rude Rahul Jain25 comment Share Follow See all 8 Comments See all 8 8 Comments reply Shubham Sharma 2 commented Mar 20, 2017 reply Follow Share should we consider worst or best case for swapping ? "which of the following methods will be the best if number of swappings done" according to this statement Insertion sort has 0 swaps having constant complexity O(1). 0 votes 0 votes Rahul Jain25 commented Mar 20, 2017 reply Follow Share We must consider worst case. And also for best and average case no other method can have lesser swaps then selection sort. 0 votes 0 votes Shubham Sharma 2 commented Mar 20, 2017 reply Follow Share Insertion sort takes zero swaps i think. 0 votes 0 votes Rahul Jain25 commented Mar 20, 2017 reply Follow Share In best case insertion sort requires 0 swaps bu selection will also require 0 swaps. It is possible other method may have swaps equal to selection but they cannot have less swaps then selection sort. 0 votes 0 votes Shubham Sharma 2 commented Mar 20, 2017 reply Follow Share Selection sort cannot have zero swaps considering best case it will always have n-1 swaps.Check for best case that is check sorted order(increasing order or almost sorted) of elements by using for both selection sort and insertion sort algorithm . Remember if you are taking decreasing order as sorted order specially in case of insertion sort you will get worst case. 0 votes 0 votes Rahul Jain25 commented Mar 20, 2017 reply Follow Share Selection sort will do zero swaps in best case when array is in increasing order. You are saying about comparisons. In selection sort we traverse array and select min and put at first place and so on. But if array is sorted how are making swap??? 0 votes 0 votes Shubham Sharma 2 commented Mar 20, 2017 reply Follow Share "But if array is sorted how are making swap???" :- Swap with itself. as the per the algorithm implementation in C. 0 votes 0 votes rude commented Mar 20, 2017 reply Follow Share @Shubham Yes, Selection sort only perform $ O(n) $ swapping. There are many implementation. You are confused because you may not have seen the efficient one. Check Wikipedia page of selection sort, it has that algorithm. 1 votes 1 votes Please log in or register to add a comment.