ace mock 6

Question

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

Answer 1

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.

Comments

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

---

We must consider worst case. And also for best and average case no other method can have lesser swaps then selection sort.

---

Insertion sort takes zero swaps i think.

---

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.

---

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.

---

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

---

"But if array is sorted how are making swap???" :- Swap with itself. as the per the algorithm implementation in C.

---

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