Shell sort
From CodeCodex
| Related content: |
| Image:Wikipedia-logo.png | See Wikipedia's Article for Shell sort. |
Contents |
[edit] Implementations
[edit] C
void shellSort(int numbers[], int array_size)
{
int i, j, increment, temp;
increment = array_size / 2;
while (increment > 0)
{
for (i=0; i < array_size; i++)
{
j = i;
temp = numbers[i];
while ((j >= increment) && (numbers[j-increment] > temp))
{
numbers[j] = numbers[j - increment];
j = j - increment;
}
numbers[j] = temp;
}
if (increment == 2)
increment = 1;
else
increment = increment * 5 / 11;
}
}
Original source: [1]
[edit] D
import std.stdio;
void shellSort(T)(T[] items) {
int inc = items.length / 2;
while (inc) {
for (int i; i < items.length; i++) {
int j = i;
T temp = items[i];
while (j >= inc && items[j-inc] > temp) {
items[j] = items[j - inc];
j -= inc;
}
items[j] = temp;
}
inc = inc/2 ? inc/2 : (inc==1 ? 0 : 1);
}
}
void main() {
auto a = [35, -8, 11, 1, 68, 0, 3];
shellSort(a);
writefln(a); // [-8,0,1,3,11,35,68]
}
[edit] Python
def shellSort(items):
inc = len(items) / 2
while inc:
for i in xrange(len(items)):
j = i
temp = items[i]
while j >= inc and items[j-inc] > temp:
items[j] = items[j - inc]
j -= inc
items[j] = temp
inc = inc/2 if inc/2 else (0 if inc==1 else 1)
a = [35, -8, 11, 1, 68, 0, 3];
shellSort(a)
print a # [-8, 0, 1, 3, 11, 35, 68]
[edit] Ruby
def shellSort(items)
inc = items.size / 2
while inc > 0
inc.upto(items.size-1){|i|
j = i
temp = items[i]
while j >= inc and items[j-inc] > temp
items[j] = items[j - inc]
j -= inc
end
items[j] = temp
}
inc = inc/2 ? inc/2 : (inc==1 ? 0 : 1)
end
end
a = [35, -8, 11, 1, 68, 0, 3]
shellSort(a)
a # [-8, 0, 1, 3, 11, 35, 68]
[edit] Seed7
const proc: shellSort (inout array elemType: arr) is func
local
var integer: i is 0;
var integer: j is 0;
var integer: increment is 0;
var elemType: help is elemType.value;
begin
increment := length(arr) div 2;
while increment > 0 do
for i range 1 to length(arr) do
j := i;
help := arr[i];
while j > increment and arr[j - increment] > help do
arr[j] := arr[j - increment];
j -:= increment;
end while;
arr[j] := help;
end for;
increment := increment div 2;
end while;
end func;
Original source: [2][[Category:D]
