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.
Programming Praxis 
[…] […]
[…] Praxis – Two Sub-Quadratic Sorts By Remco Niemeijer In yesterday’s Programming Praxis problem we have to implement two sort algorithms. Let’s get […]
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 nshell 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; } } }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?