/*
Shell sort in Picat.
See
* http://en.wikipedia.org/wiki/Shell_sort
* http://rosettacode.org/wiki/Sorting_algorithms/Shell_sort
Model created by Hakan Kjellerstrand, hakank@gmail.com
See also my Picat page: http://www.hakank.org/picat/
*/
main => go.
go =>
A = [23, 76, 99, 58, 97, 57, 35, 89, 51, 38, 95, 92, 24, 46, 31, 24, 14, 12, 57, 78],
println(A),
A2 = shell_sort(A),
println(A2),
nl.
go2 =>
R = 1000,
A = [random() mod R : _I in 1..10000],
statistics(runtime,_),
A2 = shell_sort(A),
statistics(runtime, [_,End]),
printf("It took %d millis to sort the array\n", End),
% assert that the array really is sorted
foreach(I in 2..A2.length)
if A2[I-1] > A2[I] then
printf("Not correct: %d should be < than %d\n", A2[I-1], A2[I])
end
end,
nl.
% using the built-in sort
go3 =>
R = 1000,
A = [random() mod R : _I in 1..10000],
statistics(runtime,_),
A2 = sort(A),
statistics(runtime, [_,End]),
printf("It took %d millis to sort the array\n", End),
% assert that the array really is sorted
foreach(I in 2..A2.length)
if A2[I-1] > A2[I] then
printf("Not correct: %d should be < than %d\n", A2[I-1], A2[I])
end
end,
nl.
% From Wikipedia's pseudo code
%
% Shell sort (inline)
%
shell_sort(A) = A2 =>
A2 = A,
Inc = round(A.length/2),
while (Inc > 0)
foreach(I in Inc+1..A.length)
Temp = A2[I],
J := I,
while (J > Inc, A[J-Inc] > Temp)
A2[J] := A2[J-Inc],
J := J - Inc
end,
A2[J] := Temp
end,
Inc := round(Inc/2.2)
end.