Algorithm implementation/Sorting/Shell sort

From Wikibooks, the open-content textbooks collection

Wikipedia has related information at Shell sort

[edit] C

 /* Performs an insertion sort on elements of a[] with the given gap.
  * If gap == 1, performs an ordinary insertion sort.
  * If gap >= length, does nothing.
  */
 void shellSortPhase(int a[], int length, int gap) {
     int i;
     for (i = gap; i < length; ++i) {
         int value = a[i];
         int j;
         for (j = i - gap; j >= 0 && a[j] > value; j -= gap) {
             a[j + gap] = a[j];
         }
         a[j + gap] = value;
     }
 }//end for
 
 void shellSort(int a[], size_t length) {
     /*
      * gaps[] should approximate a [[w:geometric progression|geometric progression]].
      * The following sequence is the best known in terms of
      * the average number of key comparisons made [http://www.research.att.com/~njas/sequences/A102549]
      */
     static const int gaps[] = {
         1, 4, 10, 23, 57, 132, 301, 701
     };
     int sizeIndex;
 
     for (sizeIndex = sizeof(gaps)/sizeof(gaps[0]) - 1;
                sizeIndex >= 0;
                --sizeIndex)
         shellSortPhase(a, length, gaps[sizeIndex]);
 }

[edit] Haskell

import Data.List (transpose)
-- Insertion sort, for sorting columns.
insert :: Ord a => a -> [a] -> [a]
insert x []     = [x]
insert x (y:ys) | x <= y    = x : y:ys
                | otherwise = y : insert x ys

insertionSort :: Ord a => [a] -> [a]
insertionSort = foldr insert []
-- Splits a list into k columns.

columnize :: Int -> [a] -> [[a]]
columnize k = transpose . takeWhile (not . null) . map (take k) . iterate (drop k)

-- Merges columns back into a single list.
decolumnize :: [[a]] -> [a]
decolumnize = concat . transpose

-- Each phase of the Shell sort breaks the list into k columns, sorts each with an
-- insertion sort, then merges those columns back into a list.
shellSortPhase :: (Ord a) => Int -> [a] -> [a]
shellSortPhase k = decolumnize . map insertionSort . columnize k 

-- The full Shell sort, applying phases with arbitrarily large gap sizes according to
-- R. Sedgewick, J. Algorithms 7 (1986), 159-173
shellSort :: (Ord a) => [a] -> [a]
shellSort xs = foldr shellSortPhase xs gaps
    where gaps = takeWhile (< length xs) sedgewick
          sedgewick = concat [[9 * 2^n - 9 * 2^(n `div` 2) + 1,
                               8 * 2^(n+1) - 6 * 2^(n `div` 2) + 1] | n <- [0..]]

[edit] Java

/** Shell sort using Shell's (original) gap sequence: n/2, n/4, ..., 1. */
public static <T extends Comparable<? super T>> void shellSort(T[] array) {
    // loop over the gaps
    for (int gap = array.length / 2; gap > 0; gap /= 2) {
        // do the insertion sort
        for (int i = gap; i < array.length; i++) {
            T val = array[i];
            int j;
            for (j = i; j >= gap && array[j - gap].compareTo(val) > 0; j -= gap) {
                array[j] = array[j - gap];
            }
            array[j] = val;
        }
    }
}

[edit] Python

 def shellSort(array):
     "Shell sort using Shell's (original) gap sequence: n/2, n/4, ..., 1."
     gap = len(array) // 2
     # loop over the gaps
     while gap > 0:
         # do the insertion sort
         for i in range(gap, len(array)):
             val = array[i]
             j = i
             while j >= gap and array[j - gap] > val:
                 array[j] = array[j - gap]
                 j -= gap
             array[j] = val
         gap //= 2