Insertion Sort vs Bubble Sort + Some analysis

This short-sighted robot will now demonstrate insertion sort. First, let's assume the left half of our input is already sorted. We'll now add the next element to the sorted part by moving it left until we find where it belongs. We'll compare it with its left neighbor. Since the neighbor is brighter, we will swap. We'll continue until we find an element darker than the one we're adding. This is the right spot for it. We'll now repeat the same steps with the next unsorted element. And so on. Now let's start from the beginning. The first element by itself is already a sorted sub-list. We'll extend it by adding new elements, same as we saw before. The two algorithms share some similarities. Both work in iterations, extending the sorted part one element at a time. So why did insertion sort win so decisively? Let's replay the entire match. We'll focus first on bubble sort. Draw a mark on this chart for each comparison it makes. In this variant of bubble sort, the iterations gradually get shorter. It skipped the last two iterations thanks to its ability to detect when the list is already sorted, and stop. But starting from a random permutation, this optimization is only likely to occur near the end anyway. So the number of comparisons is roughly n squared divided by 2. Now we'll draw the same chart for insertion sort. Insertion sort starts with the shortest iteration, and they gradually get longer. But it doesn't bother running each iteration all the way. It stops when it finds the correct spot for the newly-added element, which on average happens in the middle. Therefore the number of comparisons here is approximately n squared divided by 4. So no wonder insertion sort won. Now let's draw a similar chart for an algorithm we've shown in previous videos: quicksort. Thanks to its divide-and-conquer strategy, the height of this chart is proportional to log(n) on average. So the total number of comparisons is proportional to n log(n) on average. The difference between n log(n) and n squared gets more pronounced as n grows.

Channel: udiprod

Views: 265,302

Keywords: computer science, algorithms, sorting algorithms, animation

Id: TZRWRjq2CAg

Length: 5min 16sec (316 seconds)

Published: Sat Nov 11 2017