Algorithm Implementation/Sorting/Shell sort
Appearance
C
[edit | edit source] /* 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 | edit source]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 | edit source]/** 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
[edit | edit source]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
[edit | edit source]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
[edit | edit source] 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
[edit | edit source]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