Sorting algorithms/Strand sort

This page uses content from Wikipedia. The original article was at Strand sort. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance)

Implement the Strand sort. This is a way of sorting numbers by extracting shorter sequences of already sorted numbers from an unsorted list.

C

Strand sort using singly linked list. C99, compiled with gcc -std=c99 <lang C>#include <stdio.h>

typedef struct node_t *node, node_t; struct node_t { int v; node next; };

void sort(int *ar, int len) { node_t all[len], head, shead, merged, *cur, *next, *stail;

/* linkify */ for (int i = 0; i < len; i++) { all[i].v = ar[i]; all[i].next = all + i + 1; } all[len - 1].next = 0; head.next = all; shead.next = merged.next = 0;

while (head.next) { /* take strand */ cur = &head; stail = shead.next = head.next;

while (next = cur->next) { if (next->v >= stail->v) { cur->next = next->next; stail = stail->next = next; } else cur = next; } stail->next = 0;

/* merge */ cur = merged.next; next = shead.next; stail = &merged;

/* while both lists contain elements, append the smaller one */ while (next && cur) { if (next->v <= cur->v) { stail = stail->next = next; next = next->next; } else { stail = stail->next = cur; cur = cur->next; } } /* append the rest of the survivor to the end of merged */ stail->next = next ? next : cur; } cur = &merged; len = 0; while (cur = cur->next) ar[len++] = cur->v; }

int main() { int x[] = {-2,0,-2,5,5,3,-1,-3,5,5,0,2,-4,4,2};

define SIZE sizeof(x)/sizeof(int)

printf("before sort:"); for (int i = 0; i < SIZE; i++) printf(" %3d", x[i]);

sort(x, sizeof(x)/sizeof(int));

printf("\nafter sort: "); for (int i = 0; i < SIZE; i++) printf(" %3d", x[i]); printf("\n"); }</lang>outout<lang>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</lang>

C++

<lang cpp>#include <list>

template <typename T> std::list<T> strandSort(std::list<T> lst) {

 if (lst.size() <= 1)
   return lst;
 std::list<T> result;
 std::list<T> sorted;
 while (!lst.empty()) {
   sorted.push_back(lst.front());
   lst.pop_front();
   for (typename std::list<T>::iterator it = lst.begin(); it != lst.end(); ) {
     if (sorted.back() <= *it) {
       sorted.push_back(*it);
       it = lst.erase(it);
     } else
       it++;
   }
   result.merge(sorted);
 }
 return result;

}</lang>

J

Generally, this task should be accomplished in J using /:~. Here we take an approach that's more comparable with the other examples on this page.

Using merge defined at Sorting algorithms/Merge sort#J:

<lang j>strandSort=: (#~ merge $:^:(0<#)@(#~ -.)) (= >./\)</lang>

Example use:

<lang j> strandSort 3 1 5 4 2 1 2 3 4 5</lang>

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 ; instead of merge.

<lang j> ((#~ ; $:^:(0<#)@(#~ -.)) (= >./\)) 3 1 5 4 2 ┌───┬───┬─┬┐ │3 5│1 4│2││ └───┴───┴─┴┘

  ((#~ ; $:^:(0<#)@(#~ -.)) (= >./\)) 3 3 1 2 4 3 5 6

┌─────────┬─────┬┐ │3 3 4 5 6│1 2 3││ └─────────┴─────┴┘</lang>

Java

Works with: Java version 1.6+

<lang java5>import java.util.Arrays; import java.util.LinkedList;

public class Strand{ // note: the input list is destroyed public static <E extends Comparable<? super E>> LinkedList<E> strandSort(LinkedList<E> list){ if(list.size() <= 1) return list;

LinkedList<E> result = new LinkedList<E>(); while(list.size() > 0){ LinkedList<E> sorted = new LinkedList<E>(); sorted.add(list.removeFirst()); //same as remove() or remove(0) for(Iterator<E> it = list.iterator(); it.hasNext(); ){ E elem = it.next(); if(sorted.peekLast().compareTo(elem) <= 0){ sorted.addLast(elem); //same as add(elem) or add(0, elem) it.remove(); } } result = merge(sorted, result); } return result; }

private static <E extends Comparable<? super E>> LinkedList<E> merge(LinkedList<E> left, LinkedList<E> right){ LinkedList<E> result = new LinkedList<E>(); while(!left.isEmpty() && !right.isEmpty()){ //change the direction of this comparison to change the direction of the sort if(left.peek().compareTo(right.peek()) <= 0) result.add(left.remove()); else result.add(right.remove()); } result.addAll(left); result.addAll(right); return result; }

public static void main(String[] args){ System.out.println(strandSort(new LinkedList<Integer>(Arrays.asList(3,1,2,4,5)))); System.out.println(strandSort(new LinkedList<Integer>(Arrays.asList(3,3,1,2,4,5)))); System.out.println(strandSort(new LinkedList<Integer>(Arrays.asList(3,3,1,2,4,3,5,6)))); } }</lang> Output:

[1, 2, 3, 4, 5]
[1, 2, 3, 3, 4, 5]
[1, 2, 3, 3, 3, 4, 5, 6]

PARI/GP

<lang parigp>strandSort(v)={ my(sorted=[],unsorted=v,remaining,working); while(#unsorted, remaining=working=List(); listput(working, unsorted[1]); for(i=2,#unsorted, if(unsorted[i]<working[#working], listput(remaining, unsorted[i]) , listput(working, unsorted[i]) ) ); unsorted=Vec(remaining); sorted=merge(sorted, Vec(working)) ); sorted }; merge(u,v)={ my(ret=vector(#u+#v),i=1,j=1); for(k=1,#ret, if(i<=#u & (j>#v | u[i]<v[j]), ret[k]=u[i]; i++ , ret[k]=v[j]; j++ ) ); ret };</lang>

Perl

<lang Perl>use 5.10.0; # for given/when sub merge {

       my ($x, $y) = @_;
       my @out;
       while (@$x and @$y) {
               given ($x->[-1] <=> $y->[-1]) {
                       when( 1) { unshift @out, pop @$x }
                       when(-1) { unshift @out, pop @$y }
                       default  { splice @out, 0, 0, pop(@$x), pop(@$y) }
               }
       }
       return @$x, @$y, @out

}

sub strand {

       my $x = shift;
       my @out = shift @$x // return;
       if (@$x) {
               for (-@$x .. -1) {
                       if ($x->[$_] >= $out[-1]) {
                               push @out, splice @$x, $_, 1
                       }
               }
       }
       return @out

}

sub strand_sort {

       my @x = @_;
       my @out;
       while (my @strand = strand(\@x)) {
               @out = merge(\@out, \@strand)
       }
       @out

}

my @a = map (int rand(100), 1 .. 10); say "Before @a"; @a = strand_sort(@a); say "After @a";</lang>

PicoLisp

<lang PicoLisp>(de strandSort (Lst)

  (let Res NIL  # Result list
     (while Lst
        (let Sub (circ (car Lst))  # Build sublist as fifo
           (setq
              Lst (filter
                 '((X)
                    (or
                       (> (car Sub) X)
                       (nil (fifo 'Sub X)) ) )
                 (cdr Lst) )
              Res (make
                 (while (or Res Sub)  # Merge
                    (link
                       (if2 Res Sub
                          (if (>= (car Res) (cadr Sub))
                             (fifo 'Sub)
                             (pop 'Res) )
                          (pop 'Res)
                          (fifo 'Sub) ) ) ) ) ) ) )
     Res ) )</lang>

Test:

: (strandSort (3 1 5 4 2))
-> (1 2 3 4 5)

: (strandSort (3 abc 1 (d e f) 5 T 4 NIL 2))
-> (NIL 1 2 3 4 5 abc (d e f) T)

PureBasic

<lang PureBasic>Procedure strandSort(List a())

 Protected NewList subList()
 Protected NewList results()
 
 While ListSize(a()) > 0
   ClearList(subList())
   AddElement(subList())
   FirstElement(a())
   subList() = a()
   DeleteElement(a())
   ForEach a()
     If a() >= subList()
       AddElement(subList())
       subList() = a()
       DeleteElement(a())
     EndIf
   Next
   
   ;merge lists
   FirstElement(subList())
   If Not FirstElement(results())
     ;copy all of sublist() to results()
     MergeLists(subList(), results(), #PB_List_Last)
   Else
     Repeat
       If subList() < results()
         InsertElement(results())
         results() = subList()
         DeleteElement(subList())
         If Not NextElement(subList())
           Break
         EndIf
       ElseIf Not NextElement(results())
         ;add remainder of sublist() to end of results()
         MergeLists(subList(), results(), #PB_List_Last)
         Break 
       EndIf
     ForEver
   EndIf 
   
 Wend 
 CopyList(results(), a())

EndProcedure

Procedure.s listContents(List a())

 Protected output.s
 PushListPosition(a())
 ForEach a()
   output + Str(a()) + ","
 Next
 PopListPosition(a())
 ProcedureReturn Left(output, Len(output) - 1)

EndProcedure

Procedure setupList(List a())

 ClearList(a())
 Protected elementCount, i
 
 elementCount = Random(5) + 10
 For i = 1 To elementCount
   AddElement(a())
   a() = Random(10) - 5
 Next

EndProcedure

If OpenConsole()

 NewList sample()
 Define i
 
 For i = 1 To 3
   setupList(sample())
   PrintN("List " + Str(i) + ":")
   PrintN("  Before:  " + listContents(sample()))
   strandSort(sample())
   PrintN("  After :  " + listContents(sample()))
   PrintN("")
 Next
 
 Print(#CRLF$ + #CRLF$ + "Press ENTER to exit"): Input()
 CloseConsole()

EndIf</lang> Sample output:

List 1:
  Before:  3,-2,-4,4,-1,-3,-2,-2,2,2,0
  After :  -4,-3,-2,-2,-2,-1,0,2,2,3,4

List 2:
  Before:  -4,4,3,-2,3,-2,5,0,-1,0,5,1
  After :  -4,-2,-2,-1,0,0,1,3,3,4,5,5

List 3:
  Before:  -2,0,-2,5,5,3,-1,-3,5,5,0,2,-4,4,2
  After :  -4,-3,-2,-2,-1,0,0,2,2,3,4,5,5,5,5

Python

<lang Python>def merge_list(a, b): out = [] while len(a) and len(b): if a[0] < b[0]: out.append(a.pop(0)) else: out.append(b.pop(0)) out[len(out):] = a out[len(out):] = b return out

def strand(a): i, s = 0, [a.pop(0)] while i < len(a): if a[i] > s[-1]: s.append(a.pop(i)) else: i = i + 1 return s

def strand_sort(a): out = strand(a) while len(a): out = merge_list(out, strand(a)) return out

print strand_sort([1, 6, 3, 2, 1, 7, 5, 3])</lang> Output:<lang>[1, 1, 2, 3, 3, 5, 6, 7]</lang>

Tcl

<lang tcl>proc merge {listVar toMerge} {

   upvar 1 $listVar v
   set i [set j 0]
   set out {}
   while {$i<[llength $v] && $j<[llength $toMerge]} {

if {[set a [lindex $v $i]] < [set b [lindex $toMerge $j]]} { lappend out $a incr i } else { lappend out $b incr j }

   }
   # Done the merge, but will be one source with something left
   # This will handle all that by doing a merge of the remnants onto the end
   set v [concat $out [lrange $v $i end] [lrange $toMerge $j end]]
   return

}

proc strandSort A {

   set results {}
   while {[llength $A]} {

set sublist [lrange $A 0 0] # We build a list of items that weren't filtered rather than removing "in place" # because this fits better with the way Tcl values work (the underlying data # structure is an array, not a linked list). set newA {} foreach a [lrange $A 1 end] { if {$a > [lindex $sublist end]} { lappend sublist $a } else { lappend newA $a } } set A $newA merge results $sublist

   }
   return $results

}

puts [strandSort {3 1 5 4 2}]</lang>

Ursala

<lang 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+-</lang>

demonstration code:<lang Ursala>#cast %nL

x = (strand_sort nat-nleq) <3,1,5,4,2></lang>output:

<1,2,3,4,5>