Shell sort with Algo-rythmics ♫

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.

for-my-cakeday-i-present-my-skeptical-dog-62998
you watched it, right?

 

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.

  1. öt: five
  2. három: three
  3. 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”. 

for-my-cakeday-i-present-my-skeptical-dog-62998
sceptical dog is still sceptical

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:

first

This is when they say “holeeey” for the first time:

second

We should compare a[0] with a[5], a[1] with a[6] 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).

third
a[0] – a[5] and a[4] -a[9] are swapped. The others just lift their hands, indicating that no swapping will be done.
This is when they say “holeeey” for the second time (or something like haj mosteve?)

fourth

Now, we are comparing a[0] with a[3], a[1] with a[4] and so on (that’s why they yell something with harow). a[0] – a[3], a[1] – a[4] and a[2] – a[5] dance as pairs but no swapping occur, so a[6] starts to dance with a[3].

fifth

Now be careful! a[6] swapped with a[3], but we still have to check a[0] and a[3] 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:

sixth
after some dancing, a[4] swaps with a[7] and a[6] swaps with a[9].
Then, the dancers face the camera once more:

seventh

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.amca.png

“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.

deck1

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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s