Why Selection sort is faster than Bubble sort.

Why Selection sort is faster than Bubble sort.

---

Selection sort is faster than Bubble sort because Selection sort swaps elements "n" times in worst case, but Bubble sort swaps almost n*(n-1) times.

Why is Selection sort faster than Bubble sort?

---

Selection sort swaps elements "n" times in worst case, but Bubble sort swaps almost n*(n-1) times.

We all know, Reading time is less than writing time even in-memory. 
(Compare and running time can be ignored)

If we have a system where write operations are extremely expensive and read operations are not, then Selection sort could be ideal.
Selection sort is good for sorting arrays of small size.

Selection sort is better than Bubble sort due to less swapping required.

Note:
In Bubble sort, we can identify whether list is sorted or not in 1st iteration but in Selection sort we can't able to identify that.
Compared to Selection sort, Bubble sort should be used when the given array is almost sorted.

Selection sort Time Complexity Analysis

---

Selecting the lowest element requires scanning all n elements (this takes n - 1 comparisons) and then swapping it into the first position.
 
Finding the next lowest element requires scanning the remaining n - 1 elements and so on, 
= (n - 1) + (n - 2) + ... + 2 + 1 = n(n - 1) / 2 
= O(n^2) comparisons.

Best Case :       O(n)^2 
Worst Case :    O(n)^2 
Average Case : O(n)^2 
Worst Case Space Complexity : O(1) 

Stable : No

Bubble Sort Time Complexity Analysis

---

1. Time complexity of Bubble sort in Worst Case is O(N^2), which makes it quite inefficient for sorting large data volumes. O(N^2) because it sorts only one item in each iteration and in each iteration it has to compare n-i elements.
2. Time complexity of Bubble sort in Best Case is O(N). When the given data set is already sorted, in that case bubble sort can identify it in one single iteration hence O(N). It means while iteratng, from i=0 till arr.length, if there is no swapping required, then the array is already sorted and stop there.
3. Bubble sort can identify when the list is sorted and can stop early.
4. Bubble sort is efficient for (quite) small data sets. 
5. It is Stable sort; i.e., does not change the relative order of elements with equal keys.
6. It takes O(1) extra space.
   

You may also like to see

---

Merge Sort

Heap Sort

Bubble Sort

Insertion Sort

Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.