Rosetta Code

Sorting algorithms/Strand sort: Difference between revisions

Page Discussion

Sorting algorithms/Strand sort (view source)

Revision as of 16:29, 28 August 2022

1,532 bytes added ,  1 year ago
m
syntax highlighting fixup automation
m (syntax highlighting fixup automation)
Line 14:
{{trans|Python}}
 
<langsyntaxhighlight lang="11l">F merge_list(&a, &b)
[Int] out
L !a.empty & !b.empty
Line 41:
R out
 
print(strand_sort(&[1, 6, 3, 2, 1, 7, 5, 3]))</langsyntaxhighlight>
 
{{out}}
Line 50:
=={{header|AutoHotkey}}==
{{works with|AutoHotkey_L}}
<langsyntaxhighlight AutoHotkeylang="autohotkey">string =
(
-2 0 -2 5 5 3 -1 -3 5 5 0 2 -4 4 2
Line 76:
string := list, list = "", index := 0
}
esc::ExitApp</langsyntaxhighlight>outout<syntaxhighlight lang="text">
unsorted:-2 0 -2 5 5 3 -1 -3 5 5 0 2 -4 4 2
Sorted:-4 -3 -2 -2 -1 0 0 2 2 3 4 5 5 5 5</langsyntaxhighlight>
 
=={{header|C}}==
Strand sort using singly linked list. C99, compiled with <code>gcc -std=c99</code>
<langsyntaxhighlight Clang="c">#include <stdio.h>
 
typedef struct node_t *node, node_t;
Line 159:
 
return 0;
}</langsyntaxhighlight>outout<syntaxhighlight lang="text">before sort: -2 0 -2 5 5 3 -1 -3 5 5 0 2 -4 4 2
after sort: -4 -3 -2 -2 -1 0 0 2 2 3 4 5 5 5 5</langsyntaxhighlight>
 
=={{header|C++}}==
<langsyntaxhighlight lang="cpp">#include <list>
 
template <typename T>
Line 184:
}
return result;
}</langsyntaxhighlight>
 
=={{header|Clojure}}==
<langsyntaxhighlight Clojurelang="clojure">(ns rosettacode.strand-sort)
 
(defn merge-join
Line 222:
(strand-sort [1, 6, 3, 2, 1, 7, 5, 3])
;;=> (1 1 2 3 3 5 6 7)
</syntaxhighlight>
</lang>
 
=={{header|CMake}}==
Only for lists of integers.
<langsyntaxhighlight lang="cmake"># strand_sort(<output variable> [<value>...]) sorts a list of integers.
function(strand_sort var)
# Strand sort moves elements from _ARGN_ to _answer_.
Line 287:
 
set("${var}" ${answer} PARENT_SCOPE)
endfunction(strand_sort)</langsyntaxhighlight>
 
<langsyntaxhighlight lang="cmake">strand_sort(result 11 55 55 44 11 33 33 44 22 22)
message(STATUS "${result}") # -- 11;11;22;22;33;33;44;44;55;55</langsyntaxhighlight>
 
=={{header|Common Lisp}}==
<langsyntaxhighlight lang="lisp">(defun strand-sort (l cmp)
(if l
(let* ((l (reverse l))
Line 303:
(let ((r (loop repeat 15 collect (random 10))))
(print r)
(print (strand-sort r #'<)))</langsyntaxhighlight>output<syntaxhighlight lang="text">(5 8 6 0 6 8 4 7 0 7 1 5 3 3 6)
(0 0 1 3 3 4 5 5 6 6 6 7 7 8 8)</langsyntaxhighlight>
 
=={{header|D}}==
 
=== Using doubly linked lists ===
<langsyntaxhighlight lang="d">import std.stdio, std.container;
 
DList!T strandSort(T)(DList!T list) {
Line 352:
foreach (e; strandSort(lst))
write(e, " ");
}</langsyntaxhighlight>
{{out}}
<pre>-4 -3 -2 -2 -1 0 0 2 2 3 4 5 5 5 5 </pre>
 
=== Faster version using slices ===
<langsyntaxhighlight lang="d">import std.stdio, std.array;
 
T[] strandSort(T)(const(T)[] list) pure nothrow {
Line 391:
const arr = [-2, 0, -2, 5, 5, 3, -1, -3, 5, 5, 0, 2, -4, 4, 2];
arr.strandSort.writeln;
}</langsyntaxhighlight>
{{out}}
<pre>[-4, -3, -2, -2, -1, 0, 0, 2, 2, 3, 4, 5, 5, 5, 5]</pre>
Line 397:
=={{header|Elixir}}==
{{trans|Ruby}}
<langsyntaxhighlight lang="elixir">defmodule Sort do
def strand_sort(args), do: strand_sort(args, [])
Line 410:
end
 
IO.inspect Sort.strand_sort [7, 17, 6, 20, 20, 12, 1, 1, 9]</langsyntaxhighlight>
 
{{out}}
Line 418:
 
=={{header|Euphoria}}==
<langsyntaxhighlight lang="euphoria">function merge(sequence left, sequence right)
sequence result
result = {}
Line 460:
? s
puts(1,"After: ")
? strand_sort(s)</langsyntaxhighlight>
 
Output:
Line 467:
 
=={{header|Go}}==
<langsyntaxhighlight lang="go">package main
 
import "fmt"
Line 559:
}
return
}</langsyntaxhighlight>
Output:
<pre>
Line 568:
=={{header|Haskell}}==
 
<langsyntaxhighlight lang="haskell">-- Same merge as in Merge Sort
merge :: (Ord a) => [a] -> [a] -> [a]
merge [] ys = ys
Line 583:
extractStrand x (x1 : xs)
| x <= x1 = let (strand, rest) = extractStrand x1 xs in (x : strand, rest)
| otherwise = let (strand, rest) = extractStrand x xs in (strand, x1 : rest)</langsyntaxhighlight>
 
=={{header|J}}==
Line 589:
Using <code>merge</code> defined at [[Sorting algorithms/Merge sort#J]]:
 
<langsyntaxhighlight lang="j">strandSort=: (#~ merge $:^:(0<#)@(#~ -.)) (= >./\)</langsyntaxhighlight>
 
Example use:
 
<langsyntaxhighlight lang="j"> strandSort 3 1 5 4 2
1 2 3 4 5</langsyntaxhighlight>
 
Note: the order in which this J implementation processes the strands differs from the pseudocode currently at the wikipedia page on strand sort and matches the haskell implementation currently at the wikipedia page.
Line 600:
Also note that the individual strands can be seen by using <code>;</code> instead of <code>merge</code>.
 
<langsyntaxhighlight lang="j"> ((#~ ; $:^:(0<#)@(#~ -.)) (= >./\)) 3 1 5 4 2
┌───┬───┬─┬┐
│3 5│1 4│2││
Line 607:
┌─────────┬─────┬┐
│3 3 4 5 6│1 2 3││
└─────────┴─────┴┘</langsyntaxhighlight>
 
=={{header|Java}}==
{{works with|Java|1.6+}}
<langsyntaxhighlight lang="java5">import java.util.Arrays;
import java.util.LinkedList;
 
Line 656:
System.out.println(strandSort(new LinkedList<Integer>(Arrays.asList(3,3,1,2,4,3,5,6))));
}
}</langsyntaxhighlight>
Output:
<pre>[1, 2, 3, 4, 5]
Line 663:
 
=={{header|jq}}==
Most of the implementation is the "merge" function for merging two arrays. Notice that the helper function, strand, is defined here as an inner function.<langsyntaxhighlight lang="jq"># merge input array with array x by comparing the heads of the arrays
# in turn; # if both arrays are sorted, the result will be sorted:
def merge(x):
Line 701:
| ($s[0] | merge( $s[1] | strand_sort))
end ;
</syntaxhighlight>
</lang>
Example:
[1,3,5,2,4,6] | strand_sort
Line 707:
=={{header|Julia}}==
{{trans|Python}}
<langsyntaxhighlight lang="julia">function mergelist(a, b)
out = Vector{Int}()
while !isempty(a) && !isempty(b)
Line 736:
println(strandsort([1, 6, 3, 2, 1, 7, 5, 3]))
</langsyntaxhighlight>{{output}}<pre>
[1, 1, 2, 3, 3, 5, 6, 7]
</pre>
Line 742:
=={{header|Kotlin}}==
{{trans|D}}
<langsyntaxhighlight lang="scala">// version 1.1.2
 
fun <T : Comparable<T>> strandSort(l: List<T>): List<T> {
Line 783:
val l = listOf(-2, 0, -2, 5, 5, 3, -1, -3, 5, 5, 0, 2, -4, 4, 2)
println(strandSort(l))
}</langsyntaxhighlight>
 
{{out}}
Line 791:
 
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<langsyntaxhighlight Mathematicalang="mathematica">StrandSort[ input_ ] := Module[ {results = {}, A = input},
While[Length@A > 0,
sublist = {A[[1]]}; A = A[[2;;All]];
Line 799:
results = #[[Ordering@#]]&@Join[sublist, results];];
results ]
StrandSort[{2, 3, 7, 5, 1, 4, 7}]</langsyntaxhighlight>
{{out}}
<pre>{1, 2, 3, 4, 5, 7, 7}</pre>
 
=={{header|MAXScript}}==
<langsyntaxhighlight MAXScriptlang="maxscript">fn strandSort arr =
(
arr = deepcopy arr
Line 828:
return results
 
)</langsyntaxhighlight>
Output:
<syntaxhighlight lang="maxscript">
<lang MAXScript>
a = for i in 1 to 20 collect random 1 40
#(19, 26, 14, 31, 11, 33, 2, 14, 32, 28, 12, 38, 2, 37, 27, 18, 31, 24, 39, 28)
strandSort a
#(2, 2, 11, 12, 14, 14, 18, 19, 24, 26, 27, 28, 28, 31, 31, 32, 33, 37, 38, 39)
</syntaxhighlight>
</lang>
 
=={{header|NetRexx}}==
<langsyntaxhighlight NetRexxlang="netrexx">/* NetRexx */
options replace format comments java crossref savelog symbols binary
 
Line 911:
 
return result
</syntaxhighlight>
</lang>
;Output
<pre>
Line 934:
 
=={{header|Nim}}==
<langsyntaxhighlight lang="nim">proc mergeList[T](a, b: var seq[T]): seq[T] =
result = @[]
while a.len > 0 and b.len > 0:
Line 965:
 
var a = @[1, 6, 3, 2, 1, 7, 5, 3]
echo a.strandSort</langsyntaxhighlight>
Output:
<pre>@[1, 1, 2, 3, 3, 5, 6, 7]</pre>
Line 971:
=={{header|OCaml}}==
{{trans|Haskell}}
<langsyntaxhighlight lang="ocaml">let rec strand_sort (cmp : 'a -> 'a -> int) : 'a list -> 'a list = function
[] -> []
| x::xs ->
Line 982:
in
let strand, rest = extract_strand x xs in
List.merge cmp strand (strand_sort cmp rest)</langsyntaxhighlight>
usage
<pre>
Line 990:
 
=={{header|PARI/GP}}==
<langsyntaxhighlight lang="parigp">strandSort(v)={
my(sorted=[],unsorted=v,remaining,working);
while(#unsorted,
Line 1,019:
);
ret
};</langsyntaxhighlight>
 
=={{header|Pascal}}==
<langsyntaxhighlight Pascallang="pascal">program StrandSortDemo;
type
Line 1,100:
end;
writeln;
end.</langsyntaxhighlight>
 
=={{header|Perl}}==
<langsyntaxhighlight Perllang="perl">use strict;
use warnings;
use feature 'say';
Line 1,138:
say "Before @a";
@a = strand_sort(@a);
say "After @a";</langsyntaxhighlight>
 
=={{header|Phix}}==
<!--<langsyntaxhighlight Phixlang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
Line 1,180:
<span style="color: #0000FF;">?</span><span style="color: #000000;">strand_sort</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">shuffle</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)))</span>
<!--</langsyntaxhighlight>-->
{{out}}
<pre>
Line 1,189:
{{trans|D}}
{{works with|PHP 5.3.0+}}
<langsyntaxhighlight lang="php">$lst = new SplDoublyLinkedList();
foreach (array(1,20,64,72,48,75,96,55,42,74) as $v)
$lst->push($v);
Line 1,226:
foreach ($right as $v) $res->push($v);
return $res;
}</langsyntaxhighlight>
<pre>1 20 42 48 55 64 72 74 75 96</pre>
 
=={{header|PicoLisp}}==
<langsyntaxhighlight PicoLisplang="picolisp">(de strandSort (Lst)
(let Res NIL # Result list
(while Lst
Line 1,250:
(pop 'Res)
(fifo 'Sub) ) ) ) ) ) ) )
Res ) )</langsyntaxhighlight>
Test:
<pre>: (strandSort (3 1 5 4 2))
Line 1,259:
 
=={{header|PL/I}}==
<langsyntaxhighlight PLlang="pl/Ii">strand: procedure options (main); /* 27 Oct. 2012 */
declare A(100) fixed, used(100) bit (1), sorted fixed controlled;
declare (temp, work) fixed controlled;
Line 1,349:
end move;
 
end strand;</langsyntaxhighlight>
Generated data:
<pre>
Line 1,365:
 
=={{header|PureBasic}}==
<langsyntaxhighlight PureBasiclang="purebasic">Procedure strandSort(List a())
Protected NewList subList()
Protected NewList results()
Line 1,446:
Print(#CRLF$ + #CRLF$ + "Press ENTER to exit"): Input()
CloseConsole()
EndIf</langsyntaxhighlight>
Sample output:
<pre>List 1:
Line 1,461:
 
=={{header|Python}}==
<langsyntaxhighlight Pythonlang="python">def merge_list(a, b):
out = []
while len(a) and len(b):
Line 1,487:
return out
 
print strand_sort([1, 6, 3, 2, 1, 7, 5, 3])</langsyntaxhighlight>
Output:<syntaxhighlight lang="text">[1, 1, 2, 3, 3, 5, 6, 7]</langsyntaxhighlight>
 
=={{header|Racket}}==
<langsyntaxhighlight lang="racket">
#lang racket
(require mzlib/list)
Line 1,509:
 
(strand-sort (build-list 10 (λ(_) (random 15))))
</syntaxhighlight>
</lang>
 
=={{header|Raku}}==
(formerly Perl 6)
{{Works with|Rakudo|2018.04.01}}
<syntaxhighlight lang="raku" perl6line>sub infix:<M> (@x-in, @y-in) {
my @x = | @x-in;
my @y = | @y-in;
Line 1,549:
say "Before {@a}";
@a = strand_sort(@a);
say "After {@a}";</langsyntaxhighlight>
{{out}}
<pre>Before 1 20 64 72 48 75 96 55 42 74
Line 1,561:
 
It can handle integers, floating point numbers, exponentiated numbers, and/or character strings.
<langsyntaxhighlight lang="rexx">/*REXX program sorts a random list of words (or numbers) using the strand sort algorithm*/
parse arg size minv maxv old /*obtain optional arguments from the CL*/
if size=='' | size=="," then size=20 /*Not specified? Then use the default.*/
Line 1,591:
#=1+(word(a.1,1) >= word(a.2,1)); p=p word(a.#,1); a.#=subword(a.#,2)
end /*forever*/
return space(p a.1 a.2)</langsyntaxhighlight>
'''output''' &nbsp; when using the input of: &nbsp; <tt> 25 -9 30 1000 2000 3000 </tt>
<pre>
Line 1,615:
 
=={{header|Ring}}==
<langsyntaxhighlight lang="ring">
# Project : Sorting algorithms/Strand sort
 
Line 1,660:
svect = left(svect, len(svect) - 1)
see svect + nl
</syntaxhighlight>
</lang>
Output:
<pre>
Line 1,670:
 
=={{header|Ruby}}==
<langsyntaxhighlight lang="ruby">class Array
def strandsort
a = dup
Line 1,692:
end
 
p [1, 6, 3, 2, 1, 7, 5, 3].strandsort</langsyntaxhighlight>
 
{{out}}
Line 1,699:
=={{header|Sidef}}==
{{trans|Perl}}
<langsyntaxhighlight lang="ruby">func merge(x, y) {
var out = [];
while (x && y) {
Line 1,734:
var a = 10.of { 100.irand };
say "Before: #{a}";
say "After: #{strand_sort(a)}";</langsyntaxhighlight>
 
{{out}}
Line 1,743:
 
=={{header|Tcl}}==
<langsyntaxhighlight lang="tcl">proc merge {listVar toMerge} {
upvar 1 $listVar v
set i [set j 0]
Line 1,783:
}
 
puts [strandSort {3 1 5 4 2}]</langsyntaxhighlight>
 
=={{header|Ursala}}==
 
<langsyntaxhighlight Ursalalang="ursala">strand_sort "r" = # parameterized by a relational predicate "r"
 
@NiX -+
:-0 ~&B^?a\~&Y@a "r"?abh/~&alh2faltPrXPRC ~&arh2falrtPXPRC,
~&r->l ^|rlPlCrrPX/~& @hNCNXtX ~&r->lbx "r"?rllPXh/~&llPrhPlrPCXrtPX ~&rhPllPClrPXrtPX+-</langsyntaxhighlight>
demonstration code:<langsyntaxhighlight Ursalalang="ursala">#cast %nL
 
x = (strand_sort nat-nleq) <3,1,5,4,2></langsyntaxhighlight>output:<pre><1,2,3,4,5></pre>
 
=={{header|Wren}}==
{{trans|Kotlin}}
<langsyntaxhighlight lang="ecmascript">var merge = Fn.new { |left, right|
var res = []
while (!left.isEmpty && !right.isEmpty) {
Line 1,837:
System.print("Unsorted: %(a)")
a = strandSort.call(a)
System.print("Sorted : %(a)")</langsyntaxhighlight>
 
{{out}}
Line 1,846:
 
=={{header|zkl}}==
<langsyntaxhighlight lang="zkl">fcn strandSort(A){ //--> new list, A is cleared, should add A=A.copy()
sublist:=List.createLong(A.len()); results:=List.createLong(A.len());
while(A){
Line 1,856:
}
results
}</langsyntaxhighlight>
The createLong list method creates a new list with pre-allocated space
<langsyntaxhighlight lang="zkl">strandSort(L(3,1,5,4,2)).println();
strandSort("azbfe".split("")).println();</langsyntaxhighlight>
{{out}}
<pre>
Thundergnat
10,327

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/328456"