Sorting algorithms/Strand sort: Difference between revisions

{{task|Sorting Algorithms}}

{{Sorting Algorithm}}

{{Wikipedia|Strand sort}}

 

=={{header|C}}==

Strand sort using singly linked list. C99, compiled with <code>gcc -std=c99</code>

 

typedef struct node_t *node, node_t;

 

return 0;

 

=={{header|C++}}==

 

template <typename T>

}

return result;

 

=={{header|Clojure}}==

 

(defn merge-join

(strand-sort [1, 6, 3, 2, 1, 7, 5, 3])

;;=> (1 1 2 3 3 5 6 7)

 

=={{header|CMake}}==

Only for lists of integers.

function(strand_sort var)

# Strand sort moves elements from _ARGN_ to _answer_.

 

set("${var}" ${answer} PARENT_SCOPE)

 

 

=={{header|Common Lisp}}==

(if l

(let* ((l (reverse l))

(let ((r (loop repeat 15 collect (random 10))))

(print r)

 

=={{header|D}}==

 

=== Using doubly linked lists ===

 

DList!T strandSort(T)(DList!T list) {

foreach (e; strandSort(lst))

write(e, " ");

{{out}}

<pre>-4 -3 -2 -2 -1 0 0 2 2 3 4 5 5 5 5 </pre>

 

=== Faster version using slices ===

 

T[] res;

while (!left.empty && !right.empty) {

auto sorted = list[0 .. 1];

list.popFront;

(sorted.back <= item ? sorted : leftover) ~= item;

result = merge(sorted, result);

 

void main() {

arr.strandSort.writeln;

{{out}}

<pre>[-4, -3, -2, -2, -1, 0, 0, 2, 2, 3, 4, 5, 5, 5, 5]</pre>

 

=={{header|Euphoria}}==

sequence result

result = {}

? s

puts(1,"After: ")

 

Output:

After: {18,51,340,346,417,502,551,746,903,940}</pre>

 

=={{header|Go}}==

 

import "fmt"

}

return

Output:

<pre>

=={{header|Haskell}}==

 

merge :: (Ord a) => [a] -> [a] -> [a]

merge [] ys = ys

extractStrand x (x1 : xs)

| x <= x1 = let (strand, rest) = extractStrand x1 xs in (x : strand, rest)

 

=={{header|J}}==

Using <code>merge</code> defined at [[Sorting algorithms/Merge sort#J]]:

 

 

Example use:

 

 

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.

Also note that the individual strands can be seen by using <code>;</code> instead of <code>merge</code>.

 

┌───┬───┬─┬┐

│3 5│1 4│2││

┌─────────┬─────┬┐

│3 3 4 5 6│1 2 3││

 

=={{header|Java}}==

{{works with|Java|1.6+}}

import java.util.LinkedList;

 

System.out.println(strandSort(new LinkedList<Integer>(Arrays.asList(3,3,1,2,4,3,5,6))));

}

Output:

<pre>[1, 2, 3, 4, 5]

[1, 2, 3, 3, 3, 4, 5, 6]</pre>

 

While[Length@A > 0,

sublist = {A[[1]]}; A = A[[2;;All]];

];

results = #[[Ordering@#]]&@Join[sublist, results];];

 

=={{header|NetRexx}}==

options replace format comments java crossref savelog symbols binary

 

 

return result

;Output

<pre>

US Washington

</pre>

 

=={{header|OCaml}}==

{{trans|Haskell}}

[] -> []

| x::xs ->

in

let strand, rest = extract_strand x xs in

usage

<pre>

 

=={{header|PARI/GP}}==

my(sorted=[],unsorted=v,remaining,working);

while(#unsorted,

);

ret

 

=={{header|Pascal}}==

type

end;

writeln;

 

=={{header|Perl}}==

sub merge {

}

 

sub strand {

}

 

sub strand_sort {

}

 

say "Before @a";

@a = strand_sort(@a);

 

{{out}}

 

=={{header|PHP}}==

{{trans|D}}

{{works with|PHP 5.3.0+}}

foreach (array(1,20,64,72,48,75,96,55,42,74) as $v)

$lst->push($v);

foreach ($right as $v) $res->push($v);

return $res;

<pre>1 20 42 48 55 64 72 74 75 96</pre>

 

=={{header|PicoLisp}}==

(let Res NIL # Result list

(while Lst

(pop 'Res)

(fifo 'Sub) ) ) ) ) ) ) )

Test:

<pre>: (strandSort (3 1 5 4 2))

 

=={{header|PL/I}}==

declare A(100) fixed, used(100) bit (1), sorted fixed controlled;

declare (temp, work) fixed controlled;

end move;

 

Generated data:

<pre>

 

=={{header|PureBasic}}==

Protected NewList subList()

Protected NewList results()

Print(#CRLF$ + #CRLF$ + "Press ENTER to exit"): Input()

CloseConsole()

Sample output:

<pre>List 1:

 

=={{header|Python}}==

out = []

while len(a) and len(b):

return out

 

 

=={{header|Racket}}==

#lang racket

(require mzlib/list)

 

(strand-sort (build-list 10 (λ(_) (random 15))))

 

=={{header|REXX}}==

This REXX program was written to generate a specified amount of random numbers as

 

</pre>

 

</pre>

<br><br>

 

=={{header|Ruby}}==

def strandsort

result = []

end

end

result

end

def strandsort!

end

end

 

 

<pre>[1, 1, 2, 3, 3, 5, 6, 7]</pre>

 

=={{header|Tcl}}==

upvar 1 $listVar v

set i [set j 0]

}

 

 

=={{header|Ursala}}==

 

 

@NiX -+

:-0 ~&B^?a\~&Y@a "r"?abh/~&alh2faltPrXPRC ~&arh2falrtPXPRC,

 

 

{{omit from|GUISS}}