Shellsort With Three Increments

December 15, 2015

It was a dreary Sunday in St Louis, unseasonably warm, but it rained all day and felt much colder than the actual air temperature, so I sat down to read Donald Knuth’s article, with Svante Janson, Shellsort With Three Increments. After sixteen pages, Janson and Knuth conjecture but do not prove that the gap sequence (h, g, 1) with h ≈ √n and g ≈ √h and h coprime to g leads to time complexity O(n3/2).

Your task is to implement shellsort, as we did in a previous exercise, and test the Janson/Knuth conjecture. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

One Response to “Shellsort With Three Increments”

  1. Paul said

    In Python. For N > 1000 the conjecture seems to hold.

    from fractions import gcd
    from math import sqrt
    from timeit import repeat
    
    
    def shellsort(array, gaps=None):
        n = len(array)
        if gaps is None:
            h, g = round(sqrt(n)), round(sqrt(sqrt(n)))
            while gcd(h, g) != 1:
                h += 1
            gaps = (h, g, 1)
        for gap in gaps:
            for i in range(gap, n):
                val = array[i]
                j = i
                while j >= gap and array[j - gap] > val:
                    array[j] = array[j - gap]
                    j -= gap
                array[j] = val
    
    
    if __name__ == "__main__":
        for n in range(7):
            N = 10 ** n
            setup = "import random;from __main__ import shellsort;"
            setup += "data = cdata = list(range(" + str(N) + "));"
            setup += "random.shuffle(data)"
            stmt = "shellsort(data)"
            print("{:8d} {:12g} {:12g}".format(
                N, N ** 1.5 / 3000000, min(repeat(stmt, setup, number=6))))
        """     N     cN^3/2      time
                1  3.33333e-07  3.07887e-05
               10  1.05409e-05  0.000104681
              100  0.000333333  0.000972409
             1000    0.0105409    0.0162739
            10000     0.333333     0.364905
           100000      10.5409      10.0037
          1000000      333.333      322.088
        """
    

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: