Algorithm Implementation/Sorting/Shell sort

From Wikibooks, open books for an open world
Jump to: navigation, search

C[edit]

 /* 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     
 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]);
 }

Haskell[edit]

import Data.List (transpose, insert, unfoldr)
 
-- Insertion sort, for sorting columns.
insertionSort :: Ord a => [a] -> [a]
insertionSort = foldr insert []
 
-- Splits a list into k columns.
columnize :: Int -> [a] -> [[a]]
columnize k = transpose . takeWhile (not . null) . unfoldr (Just . splitAt 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..]]

Java[edit]

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

Ruby[edit]

module ShellSort
  def self.sort(keys)
    sort!(keys.clone)
  end
 
  def self.sort!(keys)
    gap = keys.size/2
    while gap > 0
      for j in gap...keys.size
        key = keys[j]
        i = j
        while (i >= gap and keys[i-gap] > key)
          keys[i] = keys[i-gap]
          i -= gap
        end
        keys[i] = key
      end
      gap /= 2
    end
    keys
  end
end

Python[edit]

 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