Brandon.Si(mmons)

code / art / projects

Gnome Sort

In my boredom, I implemented the toy sorting algorithm called Gnome Sort. It accomplishes backtracking by using a zipper-like system of two lists treated as stacks, and is about 100X slower than GHC’s merge sort on the test I used. It’s also not especially small or simple-looking. It’s basically terrible:

Gnome sort algorithm
1
2
3
4
5
6
7
gnomeSort :: (Ord a)=> [a] -> [a]
gnomeSort = sort []
    where sort rs [] = rs
          sort [] (x:xs) = sort [x] xs
          sort (r:rs) (x:xs)
              | x > r = sort rs (x:r:xs)
              | otherwise = sort (x:r:rs) xs

The above doesn’t keep track of where it left off before it began to backtrack, an obvious optimization which turned the algorithm into an insertion sort:

Insertion sort algo.
1
2
3
4
5
6
import Data.List (insert)

insertSort :: (Ord a)=> [a] -> [a]
insertSort = sort []
    where sort rs [] = rs
          sort rs (x:xs) = sort (insert x rs) xs

about 60X slower than Data.List.sort.

Comments