Algorithm Implementation/Sorting/Shell sort

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

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

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

Pascal

const maxA = 1000;
type TElem = integer;
     TArray = array[1..maxA]of TElem;

(*Shell sort with Knuth's gap sequence*)

procedure ShellSort(var A:TArray;n:integer);
var i,j,h:integer;
    key:TElem;
begin
  h := 1;
  while h <= n do
  begin
    h := h * 3;
    h := h + 1;
  end;
  repeat
    h := h div 3;
    (* Insertion sort with gap = h *)
    for j := h + 1 to n do
    begin
      key := A[j];
      i := j - h;
      while(i > 0)and(A[i] > key)do
      begin
        A[i + h] := A[i];
        i := i - h;
      end;
      A[i + h] := key;
    end;
  until h <= 1;
end;

Generating Pratt gap sequence

const maxI = 100;
type TIndexArray = array[1..maxI]of integer;

procedure generatePratt(var P:TIndexArray;n:integer);
var j,k,pow3:integer;
begin
  P[1] := 1;
  j := 1;
  pow3 := 3;
  k := 1;
  while P[k] <= n do
  begin
    k := k + 1;
    if 2 * P[k - j] < pow3 then
      P[k] := 2 * P[k - j]
    else
    begin
      P[k] := pow3;
      j := j + 1;
      pow3 := pow3 * 3;
    end;
  end;
end;

Phix

function shell_sort(sequence s)
integer gap = floor(length(s)/2), j
object temp
    while gap>0 do
        for i=gap to length(s) do
            temp = s[i]
            j = i-gap
            while j>=1 and temp<=s[j] do
                s[j+gap] = s[j]
                j -= gap
            end while
            s[j+gap] = temp
        end for
        gap = floor(gap/2)
    end while
    return s
end function

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

Ruby

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