Why is selection sort faster than bubble sort?

It is written on Wikipedia that “… selection sort almost always outperforms bubble sort and gnome sort.” Can anybody please explain to me why is selection sort considered faster than bubble sort even though both of them have:

  1. Worst case time complexity: O(n2)

  2. Number of comparisons: O(n2)

  3. Best case time complexity :

    • Bubble sort: O(n)
    • Selection sort: O(n2)
  4. Average case time complexity :

    • Bubble sort: O(n2)
    • Selection sort: O(n2)

Answer

All complexities you provided are true, however they are given in Big O notation, so all additive values and constants are omitted.

To answer your question we need to focus on a detailed analysis of those two algorithms. This analysis can be done by hand, or found in many books. I’ll use results from Knuth’s Art of Computer Programming.

Average number of comparisons:

  • Bubble sort: 12(N2NlnN(γ+ln21)N)+O(N)
  • Insertion sort: 14(N2N)+NHN
  • Selection sort: (N+1)HN2N

Now, if you plot those functions you get something like this:
plot
plot2

As you can see, bubble sort is much worse as the number of elements increases, even though both sorting methods have the same asymptotic complexity.

This analysis is based on the assumption that the input is random – which might not be true all the time. However, before we start sorting we can randomly permute the input sequence (using any method) to obtain the average case.

I omitted time complexity analysis because it depends on implementation, but similar methods can be used.

Attribution
Source : Link , Question Author : RYO , Answer Author : Bartosz Przybylski

Leave a Comment