27
$\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$
32
$\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$
  • $\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$ – Sasho Nikolov Jul 7 '13 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$ – Bartosz Przybylski Jul 7 '13 at 19:14
  • $\begingroup$ I guess I was sleepy, you are right, the sequence can be permuted in linear time. $\endgroup$ – Sasho Nikolov Jul 8 '13 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$ – templatetypedef Mar 31 '15 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 '17 at 15:43
11
$\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$
  • 1
    $\begingroup$ this is even very good answer $\endgroup$ – Grijesh Chauhan Jul 6 '13 at 17:18
  • $\begingroup$ which book you does prefer? $\endgroup$ – Grijesh Chauhan Sep 27 '13 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 '13 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$ – overexchange Jul 28 '15 at 4:21
3
$\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$
  • $\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 '13 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 '16 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 '16 at 15:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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