Sorting algorithms/Shell sort: Difference between revisions
Content added Content deleted
Line 845: | Line 845: | ||
=={{header|ATS}}== |
=={{header|ATS}}== |
||
===For arrays of elements that may be of linear type=== |
|||
<lang ATS>(* Shell sort with both the gap sequence and the order predicate |
<lang ATS>(* Shell sort with both the gap sequence and the order predicate |
||
Line 1,003: | Line 1,005: | ||
Because the value of a[i] ends up in a particular spot earlier in the array, it is common to store that value in a temporary variable, rather than use interchanges (swaps) to move the value through the array. Writing "safe" code to do it with a temporary variable, however, would have been tedious, so I used interchanges. One can always write the implementation "unsafely", however. This will still leave you with about as much "safety" as one would expect from most other languages. |
Because the value of a[i] ends up in a particular spot earlier in the array, it is common to store that value in a temporary variable, rather than use interchanges (swaps) to move the value through the array. Writing "safe" code to do it with a temporary variable, however, would have been tedious, so I used interchanges. One can always write the implementation "unsafely", however. This will still leave you with about as much "safety" as one would expect from most other languages. |
||
Furthermore, there is no difficulty in using the temporary-variable approach, if the elements of the array are assumed to be non-linear ('''t@ype''' instead of '''vt@ype'''). For example, the element type used in the demonstration ('''int''') is not linear. |
Furthermore, there is no difficulty in using the temporary-variable approach, if the elements of the array are assumed to be non-linear ('''t@ype''' instead of '''vt@ype'''). For example, the element type used in the demonstration ('''int''') is not linear. And so the next version of the sort ... |
||
===For arrays whose elements must be of non-linear type=== |
|||
The differences from the previous implementation are mainly in the '''gapped_sort''' function. |
|||
<lang ats>(* Shell sort with both the gap sequence and the order predicate |
|||
selected by templates. *) |
|||
(* This version is only for arrays of non-linear elements (whose |
|||
values may freely be copied). Thus the code looks more like what |
|||
one would write in most other programming languages. *) |
|||
#include "share/atspre_staload.hats" |
|||
(*------------------------------------------------------------------*) |
|||
(* Interface *) |
|||
extern fn {a : t@ype} (* The "less than" template. *) |
|||
shell_sort2$lt : (a, a) -<> bool |
|||
extern fn {} (* Maps array size to a gap sequence. *) |
|||
shell_sort2$gaps : {n : int} size_t n -<> List1 ([i : pos] size_t i) |
|||
extern fn {a : t@ype} |
|||
shell_sort2 {n : int} |
|||
(arr : &array (a, n) >> _, |
|||
n : size_t n) |
|||
:<!wrt> void |
|||
(*------------------------------------------------------------------*) |
|||
(* Implementation *) |
|||
implement {a} |
|||
shell_sort2 {n} (arr, n) = |
|||
let |
|||
macdef lt = shell_sort2$lt<a> |
|||
fun |
|||
gapped_sort {gap : pos | gap < n} |
|||
{i : int | gap <= i; i <= n} |
|||
.<n - i>. |
|||
(arr : &array (a, n) >> _, |
|||
gap : size_t gap, |
|||
i : size_t i) |
|||
:<!wrt> void = |
|||
if i <> n then |
|||
let |
|||
fun |
|||
move_elems {j : nat | j <= i} |
|||
.<j>. |
|||
(arr : &array (a, n) >> _, |
|||
temp : a, |
|||
j : size_t j) |
|||
:<!wrt> void = |
|||
if j < gap then |
|||
arr[j] := temp |
|||
else if ~(temp \lt arr[j - gap]) then |
|||
arr[j] := temp |
|||
else |
|||
begin |
|||
arr[j] := arr[j - gap]; |
|||
move_elems (arr, temp, j - gap) |
|||
end |
|||
in |
|||
move_elems (arr, arr[i], i); |
|||
gapped_sort (arr, gap, succ i) |
|||
end |
|||
fun |
|||
go_through_gaps |
|||
{num_gaps : nat} |
|||
.<num_gaps>. |
|||
(arr : &array (a, n) >> _, |
|||
gaps : list ([i : pos] size_t i, num_gaps)) |
|||
:<!wrt> void = |
|||
case+ gaps of |
|||
| list_nil () => () |
|||
| list_cons (gap, more_gaps) => |
|||
if n <= gap then |
|||
go_through_gaps (arr, more_gaps) |
|||
else |
|||
begin |
|||
gapped_sort (arr, gap, gap); |
|||
go_through_gaps (arr, more_gaps) |
|||
end |
|||
in |
|||
go_through_gaps (arr, shell_sort2$gaps<> n) |
|||
end |
|||
(*------------------------------------------------------------------*) |
|||
implement |
|||
shell_sort2$lt<int> (x, y) = |
|||
x < y |
|||
implement |
|||
main0 () = |
|||
let |
|||
(* Gaps by Marcin Ciura. https://oeis.org/A102549 *) |
|||
val ciura_gaps = |
|||
$list{[i : pos] size_t i} |
|||
(i2sz 1750, |
|||
i2sz 701, i2sz 301, |
|||
i2sz 132, i2sz 57, |
|||
i2sz 23, i2sz 10, |
|||
i2sz 4, i2sz 1) |
|||
implement |
|||
shell_sort2$gaps<> n = |
|||
(* Use Ciura's gaps, regardless of array size. *) |
|||
ciura_gaps |
|||
#define SIZE 30 |
|||
var i : [i : nat] int i |
|||
var arr : array (int, SIZE) |
|||
in |
|||
array_initize_elt<int> (arr, i2sz SIZE, 0); |
|||
for (i := 0; i < SIZE; i := succ i) |
|||
arr[i] := $extfcall (int, "rand") % 10; |
|||
for (i := 0; i < SIZE; i := succ i) |
|||
print! (" ", arr[i]); |
|||
println! (); |
|||
shell_sort2<int> (arr, i2sz SIZE); |
|||
for (i := 0; i < SIZE; i := succ i) |
|||
print! (" ", arr[i]); |
|||
println! () |
|||
end</lang> |
|||
{{out}} |
|||
<pre>$ patscc -DATS_MEMALLOC_GCBDW -O3 shell_sort_task_nonlinear.dats -lgc && ./a.out |
|||
3 6 7 5 3 5 6 2 9 1 2 7 0 9 3 6 0 6 2 6 1 8 7 9 2 0 2 3 7 5 |
|||
0 0 0 1 1 2 2 2 2 2 3 3 3 3 5 5 5 6 6 6 6 6 7 7 7 7 8 9 9 9</pre> |
|||
=={{header|AutoHotkey}}== |
=={{header|AutoHotkey}}== |