Two Sub-Quadratic Sorts

October 30, 2009

In the previous exercise we looked at three sorting algorithms that work in quadratic time. Today we look at two sorting algorithms, each a minor variant on one of the previous algorithms, that work much more quickly.

Comb sort is a variant of bubble sort popularized by Stephen Lacey and Richard Box in an article in the April 1991 edition of Byte Magazine. The basic idea is to quickly eliminate turtles, small values near the end of the array, since they greatly hamper the speed of the sort. In bubble sort, the elements being compared are always adjacent; the gap between them is 1. In comb sort, the gap is initially the length of the list being sorted; the array is sorted using that gap size, then the gap is reduced and the array is sorted again, and so on until the gap is reduced to 1, when the sort reduces to ordinary bubble sort. Since early stages with large gaps quickly move turtles near the front of the array, later stages with smaller gaps have less work to do, and the sorting algorithm becomes relatively efficient. Most often, the gap is reduced by a factor of 1.3 at each step, though other shrink factors are sometimes used.

In the same way that comb sort is a variant of bubble sort, shell sort, invented by Donald Shell in 1959, is a variant of insertion sort that attempts to eliminate large disorder in early stages so that later stages have less work to do. Shell sort performs multiple stages of insertion sort, using a diminishing sequence of gaps that eventually reaches 1; a popular gap sequence is …, 364, 121, 40, 13, 4, 1.

Your task is to write functions that perform comb sort and shell sort, in the same manner as the previous exercise. 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.

About these ads

Pages: 1 2

5 Responses to “Two Sub-Quadratic Sorts”

  1. […] Praxis – Two Sub-Quadratic Sorts By Remco Niemeijer In yesterday’s Programming Praxis problem we have to implement two sort algorithms. Let’s get […]

  2. Remco Niemeijer said

    My Haskell solution (see http://bonsaicode.wordpress.com/2009/10/31/programming-praxis-two-sub-quadratic-sorts/ for a version with comments):

    import Control.Monad
    import Data.List
    import Data.List.HT
    import Data.Array.IO
    import Data.Array.MArray
    
    swap :: (MArray a e m, Ix i, Ord e) => i -> i -> a i e -> m ()
    swap i j a = do x <- readArray a i
                    y <- readArray a j
                    when (y < x) $ writeArray a i y >> writeArray a j x
    
    combSort :: Ord a => [a] -> IO [a]
    combSort [] = return []
    combSort xs = comb (s-1) =<< newListArray (1, s) xs where
        comb :: Ord a => Int -> IOArray Int a -> IO [a]
        comb 0 a = getElems a
        comb n a = mapM_ (\i -> swap i (i+n) a) [1..s-n] >> comb (n-1) a
        s = length xs
    
    shellSort :: Ord a => [a] -> IO [a]
    shellSort [] = return []
    shellSort xs = return $ shell (last . takeWhile (< length xs) $
                                   iterate (succ . (*3)) 1) xs where
        shell 1 = foldr insert []
        shell n = shell (div (n-1) 3) . concatMap (shell 1) . sliceHorizontal n
    
  3. Vikas Tandi said

    shell sort implemented in c

    #define NELEMS(x)	((sizeof(x))/(sizeof((x)[0])))
    
    void shell_sort(int arr[], int n)
    {
    	int i, j, k;
    	int gap;
    	int sequence[] = {1750, 701, 301, 132, 57, 23, 10, 4, 1};
    	int s;
    
    	for(i = 0, s = NELEMS(sequence); i < s; i++)
    	{
    		gap = sequence[i];
    
    		for(j = gap; j < n; j++)
    		{
    			int key;
    			for(k = j - gap, key = arr[j]; (k >= 0) && (arr[k] > key); k = k - gap)
    				arr[k+gap] = arr[k];
    
    			arr[k+gap] = key;
    		}
    	}
    }
    
  4. Nikunj Banka said

    Your analysis is wrong for comb sort!. See http://cstheory.stackexchange.com/questions/9619/analysis-of-comb-sort . The answers on the link I just gave are referring to a link that says that COMB SORT CANNOT RUN FASTER THAN O(N^2). Do you have any source that says that comb sort runs in sub quadratic time?

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

Follow

Get every new post delivered to your Inbox.

Join 645 other followers

%d bloggers like this: