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.

Posted by programmingpraxis

Filed in Exercises

5 Comments »

5 Responses to “Two Sub-Quadratic Sorts”

Posts about Programming from google blogs as of October 30, 2009 « tryfly.com said
October 30, 2009 at 11:47 PM
[…] […]
Programming Praxis – Two Sub-Quadratic Sorts « Bonsai Code said
October 31, 2009 at 11:48 AM
[…] Praxis – Two Sub-Quadratic Sorts By Remco Niemeijer In yesterday’s Programming Praxis problem we have to implement two sort algorithms. Let’s get […]

Remco Niemeijer said

October 31, 2009 at 11:48 AM

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

Vikas Tandi said

April 28, 2011 at 4:28 AM

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;
		}
	}
}

Nikunj Banka said
March 18, 2014 at 4:25 AM
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?

Programming Praxis