Geek Answers Handbook

What is the advantage of Shell Sort vs Insertion / Bubble Sort?

My professor gave me the following definition of Shell Sort. I have included Bubble and Insertion Sort sorting algorithms.

What is the advantage of using Shell Sort versus regular insertion sorting or bubble sorting with gap=1? After all, Shell sorting comes down to what?

I do not ask you to do your homework. I am legally confused and want to understand what is happening.

Also, I already visited Wikipedia and saw the Time Complexity table, and I already know what they say. I am looking for why, not that.

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
+5
source share
3 answers

- , . , , O (n ^ 2). , , , , . . - , .

, , O (n ^ 2) ( ), , , .

0

- .

Bubble - O (n ^ 2), Shell Sort O (n log n).

This means that if you have a collection containing 100 elements, the number of operations with Bubble and Insert sort is K * 100 ^ 2 = K * 10,000 operations, where K depends on other factors, but is basically constant.

Shell sorting requires operations Q * 100 * Log 100 = Q * 100 * 2 = Q * 2000, where Q depends on other factors and is mostly constant.

-3
source

More articles:


All Articles