Two Sub-Quadratic Sorts

October 30, 2009

There’s not much to say about either comb sort or shell sort, so they are presented below without comment. You may find it instructive to compare them to the sort functions of the previous exercise.

function sort(A,n,    gap,i,switched,t) {
    gap = n
    do {
        if (gap > 1)
            gap = int(gap / 1.3)
        switched = 0
        for (i=1; i<=n-gap; i++)
            if (A[i+gap] < A[i]) {
                t = A[i]; A[i] = A[i+gap]; A[i+gap] = t
                switched = 1 }
    } while (switched || gap > 1) }

function sort(A,n,    gap,i,j,t) {
    while (gap < n)
        gap = 3 * gap + 1
    while (gap > 1) {
        gap = int(gap / 3)
        for (i=gap+1; i<=n; i++) {
            t = A[i]
            for (j=i; gap<j && t<A[j-gap]; j-=gap)
                A[j] = A[j-gap]
            A[j] = t } } }

Comb sort has been proven to have O(n log n) performance, regardless of the gap sequence, and shell sort has been proven to be somewhat worse, though the hidden constant factors make the two competitive in practice. Either is suitable for a general-purpose sort function, though you should also consider some of the other sorting algorithms we will examine as this series continues.

The code, including the test suite of the previous exercise, is collected at http://programmingpraxis.codepad.org/XysypyUa, but you can’t run it, since codepad doesn’t provide an Awk interpreter.

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 635 other followers

%d bloggers like this: