Efficency of Insertion Sort vs Bubble sort vs Sele

Question

I have written down that Insertion Sort is faster than Selection Sort, which is faster than Bubble Sort, and that their running time for all 3 are O(n^2), but what can I say to compare them with each other?

Answer 1

You can compare sorting algorithms against the following criteria:

1. Time Complexity (Big-O notation). You should note that best-case, worst-case and average run-time can have different time complexity. For example best-case for Bubble Sort is only O(n), making it faster than Selection Sort when the original list is mostly in order (not many elements out of place).
2. Memory Complexity. How much more memory is required to sort a list as n grows?
3. Stability. Does the sort preserve the relative ordering of elements that have equivalent sort values? (For example if you were sorting a list of catalog items by their price, some elements may have equal prices. If the catalog was originally sorted alphabetically by item name, will the chosen sort algortihm preserve the alphabetical ordering within each group of equal-priced items.)
4. Best/Worst/Averavge number of comparisons required. Important when compare operations are expensive. (For example: comparing efficiencies of alternative designs where efficiency is calculated via some simulation or otherwise complex calculation).
5. Best/Worst/Average number of swap operations required. Important when swap operations are expensive. (For example: sorting shipping containers that must be physically moved on the deck of a ship)
6. Code size. Bubble-sort is known for its small code footprint.

Answer 2

There are several ways to see that insertion/selection/bubble sort all run in n^2 time.

• They use nested loops: n outer-loops, and each with n/2 inner-loops on average
• They compare all pairs of elements: there are n*(n-1)/2 pairs

Here are some detailed analysis on the running of insertion/selection/bubble sort.