### 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.

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

```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
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))))

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?