CODEWITHSUNDEEP
sorting
danmcardle
danmcardle

Reputation: 2109

What is the benefit of Shell Sort versus Insertion/Bubble Sort?

My professor gave me the following definition of Shell Sort. I've included the Bubble and Insertion Sort algorithms as well.

What is the advantage of using Shell Sort vs just a regular Insertion Sort or Bubble Sort with gap=1? Eventually, the Shell Sort boils down to that anyway, right?

I'm not asking you to do my homework. I'm legitimately confused and want to understand what's going on.

Also, I've already visited Wikipedia and seen the Time Complexity table and I already know what they say. I'm looking for the why, not the what.

def shell(a, n):
    gap = n / 2

    while gap >= 1:
            insertion(a, n, gap) # or bubble
            gap /= 2

def bubble(a, n, gap=1):
    for i in range(n):
            for j in range(n-i-gap):
                    if a[j] > a[j+gap]:
                            swap(a, j, j+1)

def insertion(a, n, gap=1):
    for i in range(1,n):
            x = a[i]
            j = i-gap

            while j>=0 and  a[j]>x:
                    a[j+gap] = a[j]
                    j-=gap

            a[j+gap]=x

Upvotes: 12

Views: 22704

Answers (3)

ApplePotato
ApplePotato

Reputation: 71

The logic of shell sort is to sort entries that are further away first. Given a partially sorted list you can in theory sort a lot faster than O(n^2). Also given a large unsorted array the probability that your final sorted position being far from your current position is high. So logically it makes sense to use a larger gap. But the main point of shell sorts is not really its performance, instead it is the simplicity of the algorithm and the low usage of stack memory.

Given that on average it does better than O(n^2) (depends of the gap sequence), small code sizes and stack usages it is very popular in embedded applications where memory constraints are a factor.

Upvotes: 7

McKay
McKay

Reputation: 12604

Shell sort allows swapping of indexes that are far apart, where bubble sort only swaps items that are adjacent.

The wikipedia entries on

cover the differences.

Edit:

Imagine that you've got a bunch of cards in your hand and the cards are almost in order, except the first and last are swapped. bubble sort would be a pain to do, because there'd be about 2n swaps, insertion sort would be better with n swaps, but shell sort could do it in 1. (the number of swaps varies based on algorithm implementation, this is just an example)

Upvotes: 12

anizzomc
anizzomc

Reputation: 252

The diference is the efficiency.

Insertion Sort and Bubble sort are both O(n^2), meanwhile Shell Sort is O(n log n).

That means if you have a collection that has 100 elements, the amount of operations with Bubble and Insert sort are K * 100^2 = K *  10000 operations, where K depends of others factors, but is mostly constant.

Using the Shell Sort, the operations needed will be Q * 100 * Log 100 = Q * 100 * 2 = Q * 2000 operations, where Q depends on others factors and is mostly constant.

Upvotes: -8

Related Questions