36
$\begingroup$

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: $\mathcal O(n^2)$

  2. Number of comparisons: $\mathcal O(n^2)$

  3. Best case time complexity :

    • Bubble sort: $\mathcal O(n)$
    • Selection sort: $\mathcal O(n^2)$
  4. Average case time complexity :

    • Bubble sort: $\mathcal O(n^2)$
    • Selection sort: $\mathcal O(n^2)$
$\endgroup$
0

7 Answers 7

43
$\begingroup$

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: $\frac{1}{2}(N^2-N\ln N -(\gamma+\ln2 -1)N) +\mathcal O(\sqrt N)$
  • Insertion sort: $\frac{1}{4}(N^2-N) + N - H_N$
  • Selection sort: $(N+1)H_N - 2N$

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.

$\endgroup$
5
  • $\begingroup$ I have a problem with "we can randomly permute input sequence to obtain avarage case". Why can that be done any faster than the time required to sort? $\endgroup$ Jul 7, 2013 at 18:30
  • 1
    $\begingroup$ You can permute any sequence of numbers it will take $N$ time where $N$ is sequence length. It's obvious that any comparation based sorting algorithm must have at least $\mathcal O(N\log N)$ complexity so even if you add $N$ to it's complexity won't be changed that much. Anyway we are talking about comparation not about time, time complexity depends on implementation and running machine, as I mentioned in answer. $\endgroup$ Jul 7, 2013 at 19:14
  • $\begingroup$ I guess I was sleepy, you are right, the sequence can be permuted in linear time. $\endgroup$ Jul 8, 2013 at 4:16
  • $\begingroup$ Since $H_N = \Theta(log N)$, is your comparison bound correct for selection sort? It looks like you're implying that it makes O(n log n) comparisons on average. $\endgroup$ Mar 31, 2015 at 5:52
  • $\begingroup$ Gamma=0.577216 is Euler-Mascheroni's constant. The relevant chapter is "The Art of Programming" vol 3 section 5.2.2 pg. 109 and 129. How did you plot the bubble sort case exactly especially the O(sqrt(N)) term? Did you just neglect it? $\endgroup$
    – mxmlnkn
    Nov 15, 2017 at 15:43
13
$\begingroup$

The asymptotic cost, or $\mathcal O$-notation, describes the limiting behaviour of a function as its argument tends to infinity, i.e. its growth rate.

The function itself, e.g. the number of comparisons and/or swaps, may be different for two algorithms with the same asymptotic cost, provided they grow with the same rate.

More specifically, Bubble sort requires, on average, $n/4$ swaps per entry (each entry is moved element-wise from its initial position to its final position, and each swap involves two entries), while Selection sort requires only $1$ (once the minimum/maximum has been found, it is swapped once to the end of the array).

In terms of the number of comparisons, Bubble sort requires $k\times n$ comparisons, where $k$ is the maximum distance between an entry's initial position and its final position, which is usually larger than $n/2$ for uniformly distributed initial values. Selection sort, however, always requires $(n-1)\times(n-2)/2$ comparisons.

In summary, the asymptotic limit gives you a good feel for how the costs of an algorithm grow with respect to the input size, but says nothing about the relative performance of different algorithms within the same set.

$\endgroup$
5
  • 1
    $\begingroup$ this is even very good answer $\endgroup$ Jul 6, 2013 at 17:18
  • $\begingroup$ which book you does prefer? $\endgroup$ Sep 27, 2013 at 11:24
  • $\begingroup$ @GrijeshChauhan: Books are a matter of taste, so take any recommendation with a grain of salt. I personally like Cormen, Leiserson, and Rivest's "Introduction to Algorithms", which gives a good overview on a number of topics, and Knuth's "The Art of Computer Programming" series if you need more/all details on any specific topic. You may want to check if the question of books has been asked here before, or post that question if it hasn't. $\endgroup$
    – Pedro
    Sep 27, 2013 at 14:06
  • $\begingroup$ For me, third para in your answer is the actual answer. Not the graphs for large inputs, given in other answer. $\endgroup$ Jul 28, 2015 at 4:21
  • $\begingroup$ I don’t understand your explanation for why it’s n/4 on average. How do you deduce it’d be n/2 swaps to go from initial to final position? $\endgroup$
    – Kashif
    Jul 11, 2022 at 20:13
6
$\begingroup$

Bubble sort uses more swap times, while selection sort avoids this.

When using selecting sort it swaps n times at most. but when using bubble sort, it swaps almost n*(n-1). And obviously reading time is less than writing time even in memory. The compare time and other running time can be ignored. So swap times is the critical bottleneck of the problem.

$\endgroup$
3
  • $\begingroup$ I think the other answer by Bartek is more reasonable but I can't vote or comment... BTW I still think writing time affect greater and hope he can take this into consideration if he see this and agree. $\endgroup$
    – simonmysun
    Jul 6, 2013 at 10:45
  • $\begingroup$ You cannot simply ignore number of comparisons, as there are use cases where time spent to compare two items can far exceed time spent to swap two items. Consider a linked list of extremely long strings (say 100k characters each). Reading in each string would take far longer than to do pointer reassignment. $\endgroup$
    – Irvin Lim
    Apr 18, 2016 at 17:07
  • $\begingroup$ @IrvinLim I think you might be right but I may have to see the statistic data before I change my mind. $\endgroup$
    – simonmysun
    Apr 30, 2016 at 15:46
0
$\begingroup$

$T(n)=O(n^2)$ means that for all $n\ge N$,

$$T(n)\le cn^2$$ for some $N$ and $c$.

In no way does

$$T_a(n)\le c_a n^2$$ and $$T_b(n)\le c_b n^2$$

allow you to draw conclusions on which of $T_a$ and $T_b$ is smaller.

$\endgroup$
0
$\begingroup$

I'm surprised that no one mentioned it, but there is a very good metric to measure the running time of the insertion sort: it's the number of inversions, i.e. the pairs $(i,j)$ such that $i<j$ and $a_i > a_j$. Denoting the number of inversions as $I$, insertion sort does $I$ swaps and $O(n) + I$ comparisons.

On the other hand, $I$ is the lower bound on the number of swaps for any algorithm which swaps adjacent elements, so bubble sort can't do better than that. Also, it's easy to construct an example when any implementation of bubble sort will require $n (n-1) / 2$ comparisons (e.g. swap the smallest and the largest elements in the smallest arrays), while the number of inversions is $O(n)$.

Finally, there are some optimizations that you can do in the insertion sort:

  • You can implement swaps more efficiently. When you want to insert $k$ into the sorted prefix of the array, you just need to store $k$, shift all elements that are greater than $k$ to the right, and place $k$ in the freed-up position.
  • You can guarantee that there are at most $O(n \log n)$ comparisons by using binary search.
$\endgroup$
0
$\begingroup$

Compare bubblesort with a selection sort that looks for the largest element and moves it to the end.

You will see that both actually make the exact same comparisons, finding the largest array element. Bubblesort also moves elements around so the indices it compares constantly change, but the values compared are the same. This extra movement after most comparisons makes bubblesort slower. Most of its n^2/2 comparisons are followed by a swap, and selection sort doesn’t need to do that. Selection sort can manage with one single exchange per element.

So: n^2/2 compare + swap operations vs n2/2 compare operations plus a tiny number of swaps.

$\endgroup$
-1
$\begingroup$

It is very informal, but intuitively in case of bubble sort on each step you do a smallest possible step towards the goal (swap elements next to each other) while in selection sort you can do long jumps towards the goal.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.