Shell sort vs Insertion sort

Let's start with an ordinary insertion sort. This is the darkest element. It should  be placed at the first position but this   short-sighted robot is going to require four  comparisons to move it all the way to the front. But here's an idea. Let's start over. We'll choose  a sub list with a gap of two. That is, we picked   every second element. We'll now run insertion sort  over this sub-list only. Because of the gaps it   will now be quicker to move the darkest element  to its correct position - only two comparisons.   Similarly, the brightest element  will be more quickly moved   closer to its correct position since  it is moved with strides of two. We'll now sort the other sub-list. Here too   this will bring the elements closer  to where they belong in the full list. We'll complete the sort with  an ordinary insertion sort.   Since the elements are close to their correct  positions this step will be much quicker now. We can extend this idea to larger  gaps. Here's a sub list with a gap of   five. Sorting it will also quickly move elements  large distances improving the order of the list.   There are four more such sub-lists. It's now easier to continue sorting  with smaller gaps. We'll choose the   gaps according to the following scheme:  first the length of the list divided by two,   which is five, as we've just done. Then  divided by four and rounded down which is two. After that we'll conclude with a gap of one. The shell sort idea didn't work out so well so  far. Let's try to see why. When sorting with gaps   the robot moved long distances from  side to side which wasted time. Next   we're going to provide it with jet  engines so it can do that more quickly.   Of course insertion sort will get the same boost  as well. To reduce the number of comparisons let's   revisit the gaps it uses. Previously we used  this gap sequence. It was generated by taking   the length of the list and repeatedly dividing by  2. This was the original description of Shell sort   but afterwards other variants were explored. This  one for example is generated by powers of two   minus one. It can be shown to have  a better worst case upper bound,   but generally analyzing Shell sort variants is  difficult and there are many open questions. See   in the description more information regarding how  it's done. But we have a simpler problem. We know   this robot will compete in sorting 10 elements  so we can optimize it especially for this task.   We can scan all possible gap sequences and  select the one that performs best on average.

Channel: udiprod

Views: 85,715

Keywords:

Id: g06hNBhoS1k

Length: 6min 23sec (383 seconds)

Published: Sun May 22 2022