Whoa, it has been over two months since my last post!
Let’s get this train back on track (choof choof).
So, two weeks ago I was studying for my midterms and I was reminded of an awesome group called AlgoRythmics. They are a bunch of people from a university in Romania that demonstrate the sorting algorithms with various folk dances (mostly Hungarian). Although my midterm was not about sorting or any sort of algorithm at all, I watched all of their videos, totally hypnotized by their nerdiness and awesomeness. My favorite ones are merge sort, shell sort and quick sort (although I feel like they should’ve chosen a different dance for quick sort – the video is even longer than the one on bubble sort!).
I understood the mechanisms behind all of them at first glance, except shell sort. I haven’t learned it before so I had to watch it more than once (sorry, systems programming midterm) before I could have a clue of what is going on. That’s why today we’re going to learn how shell sort works.
First things first: please watch this to continue.
By the way, I do not understand what they yell most of the time but I have some legit guesses. So let’s learn some Hungarian.
- öt: five
- három: three
- Hej, te szomszed!: Hey, you’re next!
…and that’s all of my Hungarian knowledge.
…sooo when a bunch of people turns to camera (like in 0:05) I will assume they are yelling “holeeey”.
Shell sort works as follows: We compare the n elements that have distance k from each other only, and then decrease k until it becomes 1. There are several ways to decrease the gap. Easiest way is to take k = n/2 and go with k = k/2 in each iteration. In this video, however, they go with “5,3,1” instead of “5,2,1”. I will take a wild guess here: if n/2 evaluates to an odd number, they start with that k and subtract 2 in each iteration. If n/2 is even, they start with k = n/2 – 1 since the algorithm should end with k=1, not k=0 (if you have any other guesses, please let me know by writing a comment below).
Let’s go step by step. This is their first arrangement:
This is when they say “holeeey” for the first time:
We should compare a with a, a with a and so on. If the one on left is larger than the one on right, we should swap them (since we are looking for an increasing order).
(Note that the array elements with the same color of dot are in the same sublist, so swapping will occur only between those elements, if there is any).
This is when they say “holeeey” for the second time (or something like haj mosteve?)
Now, we are comparing a with a, a with a and so on (that’s why they yell something with harow). a – a, a – a and a – a dance as pairs but no swapping occur, so a starts to dance with a.
Now be careful! a swapped with a, but we still have to check a and a since they have a distance of three.
We check it, and see that no swapping should happen. False alarm. Phew.
We apply the same to the rest:
Then, the dancers face the camera once more:
Now, since the interval is 1, every element is in the same sublist and every one of them can swap with each other, so we apply basic insertion sort (we try to place the element where it belongs at last).
“Why should I even bother? What’s the point, really?” He thought for a moment.
“Who says there has to be a point?” he asked.
“Or a reason. Maybe it’s just something you have to do.”
You may ask yourself (as I also asked myself) why you even bothered to learn this algorithm since it boils down to insertion sort anyway. Now, imagine that you have a list that is almost in order except for an element or two and they are far away from each other.
If you performed an insertion sort on this list (or shell sort with gap = 1), you would have to move 3, 4, 5 and 6 to the left of 7, then you would move 2 to the left of 6, 5, 4 and finally 3, a total number of 8 moves. However, if you performed shell sort with gap = 5, you would just swap 2 and 7 and your list would be sorted.
Valla kod yazmadan bırakmam. I am currently learning Python for a course, so I gave it a shot.
def main(): mylist = [3,0,1,8,7,2,5,4,9,6] shellSort(mylist) print mylist def shellSort(mylist): gap = len(mylist)//2 #gap is integer division of the list's length if gap % 2 == 0: #if even gap, make it odd gap-=1 while gap > 0: for start in range(gap): for i in range(start+gap, len(mylist), gap): #start from starting position + gap, go until end, increment by gap in each iteration pos = i #current position current = mylist[pos] while pos >= gap and mylist[pos-gap] > current: #if one on the right is less, swap mylist[pos] = mylist[pos-gap] pos -= gap mylist[pos] = current gap -= 2 #subtract 2 from gap in every iteration main()
p e a c e o u t