Sorting Algorithm

Question

For flag based approach in Bubble sort we can check first by a flag if the list is sorted or not in O(n), and if it is sorted, then no need to sort and the operation ends in Best case = O(n).

Why isn't the same concept applicable to selection sort? Why it never comes down from O(n$^2$)?

Answer 1

Because u can't implement it
The bubble sort early termination is based on the fact that, when in one pass there are no swaps, it means the array is now sorted, so we can stop
But, you can't implement the same idea in selection sort
The idea of selection sort is repeatedly "select" smallest element from the unsorted part and swap it with the 1st element of unsorted part,

suppose u try to implement the early termination idea here, like the right, it won't work

The inner for loop is trying to find element smaller than the 1st ele of unsorted part and swap them
Now ,The idea was if i can't find a number smaller than than the 1st ele of unsorted part(ie flag stays 0), then stop,
Yes this will certainly work for sorted input
but will fail for inputs like
1 3 4 2 7
cuz here for i=0 itn,
minimum=1,
now it's minimum so the if condn won't execute hence flag=0
so break, code stops after 1 itn, but array is unsorted
So, the early termination idea of bubble sort won't work here, hence complexity of selection sort stays $O(n^2)$ for all cases

 

Comments

Thanks for the detailed answer :D

---

In Bubble Sort, the flag-based approach works because it continuously checks adjacent elements and swaps them if they are in the wrong order. If during a pass, no swaps are made, it implies that the list is already sorted, hence terminating the sorting process.

However, Selection Sort doesn't benefit from this concept because it always needs to find the minimum (or maximum) element in the unsorted portion of the list and swap it with the first unsorted element. Even if the list is already sorted, Selection Sort would still iterate through the entire unsorted portion to find the minimum element, resulting in a time complexity of O(n) for the best case.

In other words, the nature of Selection Sort involves scanning through the entire unsorted portion in each iteration, regardless of whether the list is already sorted or not, which prevents it from achieving a best-case time complexity better than O(n).