Sort numbers lexicographically: Difference between revisions
Content added Content deleted
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
|||
Line 198: | Line 198: | ||
<pre>1 10 11 12 13 2 3 4 5 6 7 8 9</pre> |
<pre>1 10 11 12 13 2 3 4 5 6 7 8 9</pre> |
||
=={{header|ATS}}== |
|||
The program converts the integers to strings, sorts the strings, then converts the strings back to integers. |
|||
The method can be used to sort any sequence of non-negative integers. |
|||
(Radix sorting the numbers in their original form is another possible approach.) |
|||
<syntaxhighlight lang="ats"> |
|||
(* The Rosetta Code lexicographic sort task. *) |
|||
#include "share/atspre_staload.hats" |
|||
staload UN = "prelude/SATS/unsafe.sats" |
|||
#define NIL list_nil () |
|||
#define :: list_cons |
|||
fn |
|||
uint_to_digit (n : uint) |
|||
: char = |
|||
int2char0 (g0u2i n + char2int0 '0') |
|||
fn |
|||
int_to_string {n : nat} |
|||
(n : int n) |
|||
: string = |
|||
if iseqz n then |
|||
"0" |
|||
else |
|||
let |
|||
fun |
|||
loop {i : nat | i <= 20} |
|||
.<i>. |
|||
(buf : &array (char, 21), |
|||
i : int i, |
|||
n : uint) |
|||
: [j : nat | j <= 20] |
|||
int j = |
|||
if (i = 0) + (iseqz n) then |
|||
i |
|||
else |
|||
let |
|||
val i1 = pred i |
|||
in |
|||
buf[i1] := uint_to_digit (n mod 10u); |
|||
loop (buf, i1, n / 10u) |
|||
end |
|||
var buf = @[char][21] ('\0') |
|||
val j = loop (buf, 20, g0i2u n) |
|||
val p = ptr_add<char> (addr@ buf, j) |
|||
in |
|||
strptr2string (string0_copy ($UN.cast{string} p)) |
|||
end |
|||
fn |
|||
iota1 {n : pos} |
|||
(n : int n) |
|||
: list ([i : pos | i <= n] int i, n) = |
|||
let |
|||
typedef t = [i : pos | i <= n] int i |
|||
fun |
|||
loop {i : nat | i <= n} |
|||
.<i>. |
|||
(i : int i, |
|||
accum : list (t, n - i)) |
|||
: list (t, n) = |
|||
if i = 0 then |
|||
accum |
|||
else |
|||
loop (pred i, i :: accum) |
|||
in |
|||
loop (n, NIL) |
|||
end |
|||
fn |
|||
reverse_map_numbers_to_strings |
|||
{n : int} |
|||
(nums : list ([i : nat] int i, n)) |
|||
: list (string, n) = |
|||
let |
|||
typedef t = [i : nat] int i |
|||
fun |
|||
loop {i : nat | i <= n} |
|||
.<n - i>. |
|||
(nums : list (t, n - i), |
|||
accum : list (string, i)) |
|||
: list (string, n) = |
|||
case+ nums of |
|||
| NIL => accum |
|||
| head :: tail => |
|||
loop {i + 1} (tail, int_to_string head :: accum) |
|||
prval () = lemma_list_param nums |
|||
in |
|||
loop {0} (nums, NIL) |
|||
end |
|||
fn |
|||
reverse_map_strings_to_numbers |
|||
{n : int} |
|||
(strings : list (string, n)) |
|||
: list (int, n) = |
|||
let |
|||
macdef string_to_int (s) = |
|||
$extfcall (int, "atoi", ,(s)) |
|||
fun |
|||
loop {i : nat | i <= n} |
|||
.<n - i>. |
|||
(strings : list (string, n - i), |
|||
accum : list (int, i)) |
|||
: list (int, n) = |
|||
case+ strings of |
|||
| NIL => accum |
|||
| head :: tail => |
|||
loop {i + 1} (tail, string_to_int head :: accum) |
|||
prval () = lemma_list_param strings |
|||
in |
|||
loop {0} (strings, NIL) |
|||
end |
|||
fn |
|||
lexicographic_iota1 |
|||
{n : pos} |
|||
(n : int n) |
|||
: list (int, n) = |
|||
let |
|||
val numstrings = |
|||
reverse_map_numbers_to_strings (iota1 n) |
|||
(* One could use a MSB-first radix sort here, but I will use what |
|||
is readily available. *) |
|||
implement |
|||
list_mergesort$cmp<string> (x, y) = |
|||
~compare (x, y) |
|||
in |
|||
reverse_map_strings_to_numbers |
|||
(list_vt2t (list_mergesort<string> numstrings)) |
|||
end |
|||
implement |
|||
main0 () = |
|||
begin |
|||
println! (lexicographic_iota1 13); |
|||
println! (lexicographic_iota1 100) |
|||
end |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre>$ patscc -DATS_MEMALLOC_GCBDW lexicographic_sort.dats -lgc && ./a.out |
|||
1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9 |
|||
1, 10, 100, 11, 12, 13, 14, 15, 16, 17, 18, 19, 2, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 3, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 4, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 5, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 6, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 7, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 8, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 9, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99</pre> |
|||
=={{header|AutoHotkey}}== |
=={{header|AutoHotkey}}== |