Insertion Sort vs Bubble Sort + Some analysis

Analysis of Insertion Sort

Usually algorithms performance is analyzed using “big O notation”, which considers only growth rate. In these terms Insertion Sort and Bubble Sort are both O(n^2), both worst case and average case. We consider here only the number of comparisons, though sometimes the number of swaps is considered as well, or other characteristics.

In practice the exact form of the number of comparisons as a function of n can make a big difference. As shown in the video, insertion sort is about twice as fast as bubble sort. The exact function of the average number of comparisons is n(n+3)/4 – H_n, where H_n is the n’th harmonic number. A good approximation is n(n+3)/4 – ln(n) – 0.577.

Analysis of Bubble Sort

Originally Bubble Sort performs n-1 comparisons in each iterations. The variant shows in the video uses an obvious optimization which uses the fact that after each iteration the sorted part at the end of the list grows, so the iterations grow shorter. The exact number of resulting comparisons if n-1 iterations are done is n(n-1)/2.

Bubble sort stops when no swaps are performed in an iteration, so it might performance less than n-1 iterations. It’s hard to calculate exactly how much this contributes to its performance, but it can be shown that as n grows it becomes increasingly unlikely for this to be significant, so the average number of comparisons converges to the worst case of n(n-1)/2.

Analysis of Quick Sort

Quick Sort’s worst case performance is just like Bubble Sort’s (the optimized variant shown in the video). However the average case is much better, and is proportional to n log n (and hence O(n log n) for average performance). As the video shows, in terms of growth this is much better than O(n^2). The ‘log (n)’ is because most of the times quick sort picks a pivot that splits the list in half, or close to it, which causes the number of iterations over the entire sequence to be a logarithm of n.

The line that marks the log(n) height in the video is calculated using base of 2 (a common convention in computer science).

All videos trail: