Sorting algorithms/Stooge sort

From Rosetta Code
Jump to: navigation, search
Task
Sorting algorithms/Stooge sort
You are encouraged to solve this task according to the task description, using any language you may know.

Sorting Algorithm
This is a sorting algorithm. It may be applied to a set of data in order to sort it.

For other sorting algorithms, see Category:Sorting Algorithms, or:
O(n logn) Sorts
Heapsort | Mergesort | Quicksort
O(n log2n) Sorts
Shell Sort
O(n2) Sorts
Bubble sort | Cocktail sort | Comb sort | Gnome sort | Insertion sort | Selection sort | Strand sort
Other Sorts
Bead sort | Bogosort | Counting sort | Pancake sort | Permutation sort | Radix sort | Sleep sort | Stooge sort
This page uses content from Wikipedia. The original article was at Stooge 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)
Show the Stooge Sort for an array of integers. The Stooge Sort algorithm is as follows: 
algorithm stoogesort(array L, i = 0, j = length(L)-1)
     if L[j] < L[i] then
         L[i] ↔ L[j]
     if j - i > 1 then
         t := (j - i + 1)/3
         stoogesort(L, i  , j-t)
         stoogesort(L, i+t, j  )
         stoogesort(L, i  , j-t)
     return L

Contents

[edit] Ada

Using slices and 'First / 'Last removes the need for I / J parameters. 

with Ada.Text_IO;
procedure Stooge is
   type Integer_Array is array (Positive range <>) of Integer;
   procedure Swap (Left, Right : in out Integer) is
      Temp : Integer := Left;
   begin
      Left  := Right;
      Right := Temp;
   end Swap;
   procedure Stooge_Sort (List : in out Integer_Array) is
      T : Natural := List'Length / 3;
   begin
      if List (List'Last) < List (List'First) then
         Swap (List (List'Last), List (List'First));
      end if;
      if List'Length > 2 then
         Stooge_Sort (List (List'First     .. List'Last - T));
         Stooge_Sort (List (List'First + T .. List'Last));
         Stooge_Sort (List (List'First     .. List'Last - T));
      end if;
   end Stooge_Sort;
   Test_Array : Integer_Array := (1, 4, 5, 3, -6, 3, 7, 10, -2, -5, 7, 5, 9, -3, 7);
begin
   Stooge_Sort (Test_Array);
   for I in Test_Array'Range loop
      Ada.Text_IO.Put (Integer'Image (Test_Array (I)));
      if I /= Test_Array'Last then
         Ada.Text_IO.Put (", ");
      end if;
   end loop;
   Ada.Text_IO.New_Line;
end Stooge;

Output: 

-6, -5, -3, -2,  1,  3,  3,  4,  5,  5,  7,  7,  7,  9,  10

[edit] BASIC

Works with: QuickBASIC version 7.1

This might work with older versions of QB, but that is untested. It definitely does not work with QBasic. 

DECLARE SUB stoogesort (L() AS LONG, i AS LONG, j AS LONG)
 
RANDOMIZE TIMER
 
CONST arraysize = 10
 
DIM x(arraysize) AS LONG
DIM i AS LONG
 
PRINT "Before: ";
FOR i = 0 TO arraysize
    x(i) = INT(RND * 100)
    PRINT x(i); " ";
NEXT
PRINT
 
stoogesort x(), 0, arraysize
 
PRINT "After: ";
FOR i = 0 TO arraysize
    PRINT x(i); " ";
NEXT
PRINT
 
SUB stoogesort (L() AS LONG, i AS LONG, j AS LONG)
    IF L(j) < L(i) THEN SWAP L(i), L(j)
    IF (j - i) > 1 THEN
        DIM t AS LONG
        t = (j - i + 1) / 3
        stoogesort L(), i, j - t
        stoogesort L(), i + t, j
        stoogesort L(), i, j - t
    END IF
END SUB

Sample outputs: 

Before:  15   42   21   50   33   65   40   43   20   25   19
After:  15   19   20   21   33   25   40   42   43   50   65
Before:  99   21   84   55   32   26   86   27   8   45   11
After:  8   11   21   26   27   32   45   55   84   86   99
Before:  11   50   11   37   97   94   92   70   92   57   88
After:  11   11   37   50   57   70   88   92   92   94   97

[edit] BBC BASIC

      DIM test%(9)
      test%() = 4, 65, 2, -31, 0, 99, 2, 83, 782, 1
      PROCstoogesort(test%(), 0, DIM(test%(),1))
      FOR i% = 0 TO 9
        PRINT test%(i%) ;
      NEXT
      PRINT
      END
 
      DEF PROCstoogesort(l%(), i%, j%)
      LOCAL t%
      IF l%(j%) < l%(i%) SWAP l%(i%), l%(j%)
      IF j% - i% > 1 THEN
        t% = (j% - i% + 1)/3
        PROCstoogesort(l%(), i%, j%-t%)
        PROCstoogesort(l%(), i%+t%, j%)
        PROCstoogesort(l%(), i%, j%-t%)
      ENDIF
      ENDPROC

Output: 

       -31         0         1         2         2         4        65        83        99       782

[edit] C

#include <stdio.h>
 
#define SWAP(r,s)  do{ t=r; r=s; s=t; } while(0)
 
void StoogeSort(int a[], int i, int j) 
{
   int t;
 
   if (a[j] < a[i]) SWAP(a[i], a[j]);
   if (j - i > 1)
   {
       t = (j - i + 1) / 3;
       StoogeSort(a, i, j - t);
       StoogeSort(a, i + t, j);
       StoogeSort(a, i, j - t);
   }
}
 
int main(int argc, char *argv[])
{
   int nums[] = {1, 4, 5, 3, -6, 3, 7, 10, -2, -5, 7, 5, 9, -3, 7};
   int i, n;
 
   n = sizeof(nums)/sizeof(int);
   StoogeSort(nums, 0, n-1);
 
   for(i = 0; i <= n-1; i++)
      printf("%5d", nums[i]);
 
   return 0;
}

[edit] C#

    public static void Sort<T>(List<T> list) where T : IComparable {
        if (list.Count > 1) {
            StoogeSort(list, 0, list.Count - 1);
        }
    }
    private static void StoogeSort<T>(List<T> L, int i, int j) where T : IComparable {
        if (L[j].CompareTo(L[i])<0) {
            T tmp = L[i];
            L[i] = L[j];
            L[j] = tmp;
        }
        if (j - i > 1) {
            int t = (j - i + 1) / 3;
            StoogeSort(L, i, j - t);
            StoogeSort(L, i + t, j);
            StoogeSort(L, i, j - t);
        }
    }

[edit] D

import std.stdio, std.algorithm, std.array;
 
void stoogeSort(T)(T[] seq) pure nothrow {
    if (seq.back < seq.front)
        swap(seq.front, seq.back);
 
    if (seq.length > 2) {
        immutable m = seq.length / 3;
        seq[0 .. $ - m].stoogeSort();
        seq[m .. $].stoogeSort();
        seq[0 .. $ - m].stoogeSort();
    }
}
 
void main() {
    auto data = [1, 4, 5, 3, -6, 3, 7, 10, -2, -5];
    data.stoogeSort();
    writeln(data);
}
Output:
[-6, -5, -2, 1, 3, 3, 4, 5, 7, 10]

[edit] Euphoria

function stooge(sequence s, integer i, integer j)
    object temp
    integer t
    if compare(s[j], s[i]) < 0 then
        temp = s[i]
        s[i] = s[j]
        s[j] = temp
    end if
    if j - i > 1 then
        t = floor((j - i + 1)/3)
        s = stooge(s, i  , j-t)
        s = stooge(s, i+t, j  )
        s = stooge(s, i  , j-t)
    end if
    return s
end function
 
function stoogesort(sequence s)
    return stooge(s,1,length(s))
end function
 
constant s = rand(repeat(1000,10))
 
? s
? stoogesort(s)

Output: 

{875,616,725,922,463,740,949,476,697,455}
{455,463,476,616,697,725,740,875,922,949}

[edit] Fortran

Works with: Fortran version 90 and later
program Stooge
  implicit none
 
  integer :: i
  integer :: array(50) = (/ (i, i = 50, 1, -1) /) ! Reverse sorted array
 
  call Stoogesort(array)
  write(*,"(10i5)") array
 
contains
 
recursive subroutine Stoogesort(a)
  integer, intent(in out) :: a(:)
  integer :: j, t, temp
 
   j = size(a)
   if(a(j) < a(1)) then
     temp = a(j)
     a(j) = a(1)
     a(1) = temp
   end if
 
  if(j > 2) then
    t = j / 3
    call Stoogesort(a(1:j-t))
    call Stoogesort(a(1+t:j))
    call Stoogesort(a(1:j-t)) 
  end if
 
end subroutine
end program

[edit] Go

package main
 
import "fmt"
 
var a = []int{170, 45, 75, -90, -802, 24, 2, 66}
 
func main() {
    fmt.Println("before:", a)
    stoogesort(a)
    fmt.Println("after: ", a)
    fmt.Println("nyuk nyuk nyuk")
}
 
func stoogesort(a []int) {
    last := len(a) - 1
    if a[last] < a[0] {
        a[0], a[last] = a[last], a[0]
    }
    if last > 1 {
        t := len(a) / 3
        stoogesort(a[:len(a)-t])
        stoogesort(a[t:])
        stoogesort(a[:len(a)-t])
    }
}

[edit] Haskell

import Data.List
import Control.Arrow
import Control.Monad
 
insertAt e k = uncurry(++).second ((e:).drop 1). splitAt k
 
swapElems :: [a] -> Int -> Int -> [a]
swapElems xs i j = insertAt (xs!!j) i $ insertAt (xs!!i) j xs 
 
stoogeSort [] = []
stoogeSort [x] = [x]
stoogeSort xs = doss 0 (length xs - 1) xs
doss :: (Ord a) => Int -> Int -> [a] -> [a]
doss i j xs
      | j-i>1 = doss i (j-t) $ doss (i+t) j $ doss i (j-t) xs'
      | otherwise = xs'
    where t = (j-i+1)`div`3
	  xs'
	    | xs!!j < xs!!i = swapElems xs i j
	    | otherwise = xs

Example: 

*Main> stoogeSort [1, 4, 5, 3, -6, 3, 7, 10, -2, -5, 7, 5, 9, -3, 7]
[-6,-5,-3,-2,1,3,3,4,5,5,7,7,7,9,10]

[edit] Icon and Unicon

procedure main()              #: demonstrate various ways to sort a list and string 
   demosort(stoogesort,[3, 14, 1, 5, 9, 2, 6, 3],"qwerty")
end
 
procedure stoogesort(X,op,i,j)           #: return sorted list ascending(or descending)
local t 
 
   if /i := 0 then {
      j := *X
      op := sortop(op,X)                 # select how and what we sort
      }
 
   if op(X[j],X[i]) then
      X[i] :=: X[j]
   if j - i > 1 then {
      t := (j - i + 1) / 3
      X := stoogesort(X,op,i,j-t) 
      X := stoogesort(X,op,i+t,j)
      X := stoogesort(X,op,i,j-t)
      }
   return X                              # X must be returned and assigned to sort a string
end

Note: This example relies on the supporting procedures 'sortop', and 'demosort' in Bubble Sort. The full demosort exercises the named sort of a list with op = "numeric", "string", ">>" (lexically gt, descending),">" (numerically gt, descending), a custom comparator, and also a string.

Abbreviated sample output:
Sorting Demo using procedure stoogesort
  on list : [ 3 14 1 5 9 2 6 3 ]
    with op = &null:         [ 1 2 3 3 5 6 9 14 ]   (0 ms)
  ...
  on string : "qwerty"
    with op = &null:         "eqrtwy"   (0 ms)

[edit] J

swapElems=: |.@:{`[`]}
 
stoogeSort=: 3 : 0
  (0,<:#y) stoogeSort y
:
  if. >/x{y do. y=.x swapElems y end.
  if. 1<-~/x do.
    t=. <.3%~1+-~/x
    (x-0,t) stoogeSort (x+t,0) stoogeSort (x-0,t) stoogeSort y
  else. y end.
)

Example: 

   (,: stoogeSort) ?~13
3 10 8 4 7 12 1 2 11 6  5  9  0
0  1 2 3 4  5 6 7  8 9 10 11 12
 

[edit] Java

import java.util.Arrays;
 
public class Stooge {
    public static void main(String[] args) {
        int[] nums = {1, 4, 5, 3, -6, 3, 7, 10, -2, -5};
        stoogeSort(nums);
        System.out.println(Arrays.toString(nums));
    }
 
    public static void stoogeSort(int[] L) {
        stoogeSort(L, 0, L.length - 1);
    }
 
    public static void stoogeSort(int[] L, int i, int j) {
        if (L[j] < L[i]) {
            int tmp = L[i];
            L[i] = L[j];
            L[j] = tmp;
        }
        if (j - i > 1) {
            int t = (j - i + 1) / 3;
            stoogeSort(L, i, j - t);
            stoogeSort(L, i + t, j);
            stoogeSort(L, i, j - t);
        }
    }
}

Output: 

[-6, -5, -2, 1, 3, 3, 4, 5, 7, 10]

[edit] Lua

An example using a Y combinator for anonymous recursion and made generic with an optional predicate parameter. 

 
local Y = function (f)
  return (function(x) return x(x) end)(function(x) return f(function(...) return x(x)(...) end) end)
end
 
function stoogesort(L, pred)
 
  pred = pred or function(a,b) return a < b end
 
  Y(function(recurse)
    return function(i,j)
      if pred(L[j], L[i]) then
        L[j],L[i] = L[i],L[j]
      end
      if j - i > 1 then
        local t = math.floor((j - i + 1)/3)
        recurse(i,j-t)
        recurse(i+t,j)
        recurse(i,j-t)
      end
    end
  end)(1,#L)
 
  return L
end
 
print(unpack(stoogesort{9,7,8,5,6,3,4,2,1,0}))
 
 

[edit] Mathematica

stoogeSort[lst_, I_, J_] := Module[{i = I, j = J, list = lst},
 
 If[list[[j]] < list[[i]], list[[{i,j}]] = list[[{j,i}]];] 
 
 If[(j-i) > 1, t = Round[(j-i+1)/3];
  list=stoogeSort[list,i,j-t];
  list=stoogeSort[list,i+t,j];
  list=stoogeSort[list,i,j-t];];
 
 list
]
stoogeSort[{3,2,9,6,8},1,5]
{2,3,6,8,9}

[edit] MATLAB / Octave

%Required inputs:
%i = 1
%j = length(list)
%
function list = stoogeSort(list,i,j)
 
    if list(j) < list(i)
        list([i j]) = list([j i]);
    end
 
    if (j - i) > 1
        t = round((j-i+1)/3);
        list = stoogeSort(list,i,j-t);
        list = stoogeSort(list,i+t,j);
        list = stoogeSort(list,i,j-t);
    end
 
end

Sample Output: 

>> stoogeSort([1 -6 4 -9],1,4)
 
ans =
 
    -9    -6     1     4

[edit] NetRexx

/* NetRexx */
options replace format comments java crossref savelog symbols binary
 
iList = [int 1, 4, 5, 3, -6, 3, 7, 10, -2, -5, 7, 5, 9, -3, 7]
sList = Arrays.copyOf(iList, iList.length)
 
sList = stoogeSort(sList)
 
lists = [iList, sList]
loop ln = 0 to lists.length - 1
  cl = lists[ln]
  rpt = Rexx('')
  loop ct = 0 to cl.length - 1
    rpt = rpt cl[ct]
    end ct
    say '['rpt.strip().changestr(' ', ',')']'
  end ln
 
return
 
method stoogeSort(L_ = int[], i_ = 0, j_ = L_.length - 1) public static returns int[]
 
  if L_[j_] < L_[i_] then do
    Lt     = L_[i_]
    L_[i_] = L_[j_]
    L_[j_] = Lt
    end
  if j_ - i_ > 1 then do
    t_ = (j_ - i_ + 1) % 3
    L_ = stoogeSort(L_, i_, j_ - t_)
    L_ = stoogeSort(L_, i_ + t_, j_)
    L_ = stoogeSort(L_, i_, j_ - t_)
    end
 
  return L_
 
Output 
[1,4,5,3,-6,3,7,10,-2,-5,7,5,9,-3,7]
[-6,-5,-3,-2,1,3,3,4,5,5,7,7,7,9,10]

[edit] Objeck

 
bundle Default {
  class Stooge {
    function : Main(args : String[]) ~ Nil {
      nums := [1, 4, 5, 3, -6, 3, 7, 10, -2, -5];
      StoogeSort(nums);
      each(i : nums) {
        IO.Console->Print(nums[i])->Print(",");
      };
      IO.Console->PrintLine();
    }
 
    function : native : StoogeSort(l : Int[]) ~ Nil {
      StoogeSort(l, 0, l->Size() - 1);
    }
 
    function : native : StoogeSort(l : Int[], i : Int, j : Int) ~ Nil {
       if(l[j] < l[i]) {
        tmp := l[i];
        l[i] := l[j];
        l[j] := tmp;
      };
 
      if(j - i > 1) {
        t := (j - i + 1) / 3;
        StoogeSort(l, i, j - t);
        StoogeSort(l, i + t, j);
        StoogeSort(l, i, j - t);
      };
    }
  }
}  
 

[edit] OCaml

let swap ar i j =
  let tmp = ar.(i) in
  ar.(i) <- ar.(j);
  ar.(j) <- tmp
 
let stoogesort ar =
  let rec aux i j =
    if ar.(j) < ar.(i) then
      swap ar i j
    else if j - i > 1 then begin
      let t = (j - i + 1) / 3 in
      aux (i) (j-t);
      aux (i+t) (j);
      aux (i) (j-t);
    end
  in
  aux 0 (Array.length ar - 1)

testing: 

let () =
  let ar = [| 3; 1; 7; 2; 6; 5; 4; 9; 8 |] in
  stoogesort ar;
  Array.iter (Printf.printf " %d") ar;
  print_newline()

[edit] ooRexx

Translation of: NetRexx
/* Rexx */
 
call demo
return
exit
 
-- -----------------------------------------------------------------------------
--  Stooge sort implementation
-- -----------------------------------------------------------------------------
::routine stoogeSort
  use arg rL_, i_ = 0, j_ = .nil
  if j_ = .nil then j_ = rL_~items() - 1
 
  if rL_~get(j_) < rL_~get(i_) then do
    Lt = rL_~get(i_)
    rL_~set(i_, rL_~get(j_))
    rL_~set(j_, Lt)
    end
  if j_ - i_ > 1 then do
    t_ = (j_ - i_ + 1) % 3
    rL_ = stoogeSort(rL_, i_, j_ - t_)
    rL_ = stoogeSort(rL_, i_ + t_, j_)
    rL_ = stoogeSort(rL_, i_, j_ - t_)
    end
 
  return rL_
 
-- -----------------------------------------------------------------------------
-- Demonstrate the implementation
-- -----------------------------------------------------------------------------
::routine demo
 
  iList = .nlist~of(1, 4, 5, 3, -6, 3, 7, 10, -2, -5, 7, 5, 9, -3, 7)
  sList = iList~copy()
 
  placesList = .nlist~of( -
      "UK  London",     "US  New York",   "US  Boston",     "US  Washington" -
    , "UK  Washington", "US  Birmingham", "UK  Birmingham", "UK  Boston"     -
  )
 
  sList = stoogeSort(sList)
  sortedList = stoogeSort(placesList~copy())
 
  iLists = .list~of(iList, sList)
  loop ln = 0 to iLists~items() - 1
    icl = iLists[ln]
    rpt = ''
    loop ct = 0 to icl~items() - 1
      rpt = rpt icl[ct]
      end ct
      say '['rpt~strip()~changestr(' ', ',')']'
    end ln
 
  say
  sLists = .list~of(placesList, sortedList)
  loop ln = 0 to sLists~items() - 1
    scl = sLists[ln]
    loop ct = 0 to scl~items() - 1
      say right(ct + 1, 3)':' scl[ct]
      end ct
      say
    end ln
 
  return
 
-- -----------------------------------------------------------------------------
-- Helper class.  Map get and set methods for easier conversion from java.util.List
-- -----------------------------------------------------------------------------
::class NList mixinclass List public
 
-- Map get() to at()
::method get
  use arg ix
  return self~at(ix)
 
-- Map set() to put()
::method set
  use arg ix, item
  self~put(item, ix)
  return
 

Output: 

[1,4,5,3,-6,3,7,10,-2,-5,7,5,9,-3,7]
[-6,-5,-3,-2,1,3,3,4,5,5,7,7,7,9,10]

  1: UK  London
  2: US  New York
  3: US  Boston
  4: US  Washington
  5: UK  Washington
  6: US  Birmingham
  7: UK  Birmingham
  8: UK  Boston

  1: UK  Birmingham
  2: UK  Boston
  3: UK  London
  4: UK  Washington
  5: US  Birmingham
  6: US  Boston
  7: US  New York
  8: US  Washington

[edit] Oz

declare
  proc {StoogeSort Arr}
     proc {Swap I J}
        Tmp = Arr.I
     in
        Arr.I := Arr.J
        Arr.J := Tmp
     end
 
     proc {Sort I J}
        Size = J-I+1
     in
        if Arr.J < Arr.I then
           {Swap I J}
        end
        if Size >= 3 then
           Third = Size div 3
        in
           {Sort I J-Third}
           {Sort I+Third J}
           {Sort I J-Third}
        end
     end
  in
     {Sort {Array.low Arr} {Array.high Arr}}
  end
 
  Arr = {Tuple.toArray unit(1 4 5 3 ~6 3 7 10 ~2 ~5 7 5 9 ~3 7)}
in
  {System.printInfo "\nUnsorted: "}
  for I in {Array.low Arr}..{Array.high Arr} do
     {System.printInfo Arr.I#", "}
  end
 
  {StoogeSort Arr}
 
  {System.printInfo "\nSorted  : "}
  for I in {Array.low Arr}..{Array.high Arr} do
     {System.printInfo Arr.I#", "}
  end

Output: 

Unsorted: 1, 4, 5, 3, -6, 3, 7, 10, -2, -5, 7, 5, 9, -3, 7, 
Sorted  : -6, -5, -3, -2, 1, 3, 3, 4, 5, 5, 7, 7, 7, 9, 10,

[edit] PARI/GP

stoogeSort(v)={
  local(v=v); \\ Give children access to v
  ss(1,#v);   \\ Sort
  v
}
 
ss(i,j)={
  my(t);
  if(v[j]<v[i],
    t=v[i];
    v[i]=v[j];
    v[j]=t
  );
  if(j-i > 1,
    t=(1+j-i)\3;
    ss(i,j-t);
    ss(i+t,j);
    ss(i,j-t)
  )
};

[edit] Pascal

program StoogeSortDemo;
 
type
  TIntArray = array of integer;
 
procedure stoogeSort(var m: TIntArray; i, j: integer);
  var
    t, temp: integer;
  begin
    if m[j] < m[i] then
    begin
      temp := m[j];
      m[j] := m[i];
      m[i] := temp;
    end;
    if j - i > 1 then
    begin
      t := (j - i + 1) div 3;
      stoogesort(m, i, j-t);
      stoogesort(m, i+t, j);
      stoogesort(m, i, j-t);
    end;
  end;
 
var
  data: TIntArray;
  i: integer;
 
begin
  setlength(data, 8);
  Randomize;
  writeln('The data before sorting:');
  for i := low(data) to high(data) do
  begin
    data[i] := Random(high(data));
    write(data[i]:4);
  end;
  writeln;
  stoogeSort(data, low(data), high(data));
  writeln('The data after sorting:');
  for i := low(data) to high(data) do
  begin
    write(data[i]:4);
  end;
  writeln;
end.

Output: 

./StoogeSort
The data before sorting:
   6   1   2   1   5   2   1   5
The data after sorting:
   1   1   1   2   2   5   5   6

[edit] Perl

sub stooge {
        use integer;
        my ($x, $i, $j) = @_;
 
        $i //= 0;
        $j //= $#$x;
 
        if ( $x->[$j] < $x->[$i] ) {
                @$x[$i, $j] = @$x[$j, $i];
        }
        if ( $j - $i > 1 ) {
                my $t = ($j - $i + 1) / 3;
                stooge( $x, $i,      $j - $t );
                stooge( $x, $i + $t, $j      ); 
                stooge( $x, $i,      $j - $t );
        }
}
 
 
my @a = map (int rand(100), 1 .. 10);
print "Before @a\n";
stooge(\@a);
print "After  @a\n";
 

[edit] Perl 6

sub stoogesort( @L is rw, $i = 0, $j = @L.end ) {
    @L[$j,$i] = @L[$i,$j] if @L[$i] > @L[$j];
 
    my $interval = $j - $i;
 
    if $interval > 1 {
         my $t = ( $interval + 1 ) div 3;
         stoogesort( @L, $i   , $j-$t );
         stoogesort( @L, $i+$t, $j    );
         stoogesort( @L, $i   , $j-$t );
    }
    return @L;
}
 
my @L = 1, 4, 5, 3, -6, 3, 7, 10, -2, -5;
 
stoogesort(@L).Str.say;
 

[edit] PHP

 
function stoogeSort(&$arr, $i, $j)
{
	if($arr[$j] < $arr[$i])
	{
		list($arr[$j],$arr[$i]) = array($arr[$i], $arr[$j]);
	}
	if(($j - $i) > 1)
	{
		$t = ($j - $i + 1) / 3;
		stoogesort($arr, $i, $j - $t);
		stoogesort($arr, $i + $t, $j);
		stoogesort($arr, $i, $j - $t);
	}
}
 

[edit] PicoLisp

(de stoogeSort (L N)
   (default N (length L))
   (let P (nth L N)
      (when (> (car L) (car P))
         (xchg L P) ) )
   (when (> N 2)
      (let D (/ N 3)
         (stoogeSort L (- N D))
         (stoogeSort (nth L (inc D)) (- N D))
         (stoogeSort L (- N D)) ) )
   L )

Test: 

: (apply < (stoogeSort (make (do 100 (link (rand))))))
-> T

[edit] PL/I

stoogesort: procedure (L) recursive; /* 16 August 2010 */
   declare L(*) fixed binary;
   declare (i, j, t, temp) fixed binary;
 
   j = hbound(L,1);
   do i = lbound(L, 1) to j;
     if L(j) < L(i) then
         do; temp = L(i); L(i) = L(j); L(j) = temp; end;
     if j - i > 1 then
         do;
            t = (j - i + 1)/3;
            call stoogesort(L, i  , j-t);
            call stoogesort(L, i+t, j  );
            call stoogesort(L, i  , j-t);
         end;
   end;
end stoogesort;

[edit] PowerBASIC

PowerBASIC for DOS can use the BASIC code above, by removing CONST and changing all instances of arraysize to %arraysize (note the percent sign).

Works with: PowerBASIC for Windows
Works with: PowerBASIC Console Compiler

This version is closely based on the BASIC code above. 

%arraysize = 10
 
SUB stoogesort (L() AS LONG, i AS LONG, j AS LONG)
    IF L(j) < L(i) THEN SWAP L(i), L(j)
    IF (j - i) > 1 THEN
        DIM t AS LONG
        t = (j - i + 1) / 3
        stoogesort L(), i, j - t
        stoogesort L(), i + t, j
        stoogesort L(), i, j - t
    END IF
END SUB
 
FUNCTION PBMAIN () AS LONG
    RANDOMIZE TIMER
 
    DIM x(%arraysize) AS LONG
    DIM i AS LONG, s AS STRING
 
    s = "Before: "
    FOR i = 0 TO %arraysize
        x(i) = INT(RND * 100)
        s = s & STR$(x(i)) & " "
    NEXT
 
    stoogesort x(), 0, %arraysize
 
    #IF %DEF(%PB_CC32)
        PRINT s
        s = ""
    #ELSE
        s = s & $CRLF
    #ENDIF
 
    s = s & "After: "
    FOR i = 0 TO %arraysize
        s = s & STR$(x(i)) & " "
    NEXT
 
    ? s
END FUNCTION

Sample outputs: 

Before:  88  32  82  88  0  82  65  87  40  1  69
After:  0  1  32  40  65  69  82  82  87  88  88
Before:  60  64  95  11  52  26  7  4  51  67  47
After:  4  7  11  26  47  51  52  60  64  67  95
Before:  47  88  67  76  60  66  69  86  92  41  6
After:  6  41  47  60  66  67  69  76  88  86  92

[edit] PowerShell

Function StoogeSort( [Int32[]] $L )
{
	$i = 0
	$j = $L.length-1
	if( $L[$j] -lt $L[$i] )
	{
		$L[$i] = $L[$i] -bxor $L[$j]
		$L[$j] = $L[$i] -bxor $L[$j]
		$L[$i] = $L[$i] -bxor $L[$j]
	}
	if( $j -gt 1 )
	{
		$t = [int] ( ( $j + 1 ) / 3 )
		$k = $j - $t + 1
		[Array]::Copy( [Int32[]] ( StoogeSort( $L[0..( $j - $t ) ] ) ), $L, $k )
		[Array]::ConstrainedCopy( [Int32[]] ( StoogeSort( $L[$t..$j ] ) ), 0, $L, $t, $k )
		[Array]::Copy( [Int32[]] ( StoogeSort( $L[0..( $j - $t ) ] ) ), $L, $k )
	}
	$L
}
 
StoogeSort 9, 7, 5, 3, 1, 2, 4, 6, 8

[edit] PureBasic

Procedure Stooge_Sort(Array L.i(1), i=0 , j=0)
  If j=0
    j=ArraySize(L())
  EndIf
  If L(i)>L(j)
    Swap L(i), L(j)
  EndIf
  If j-i>1
    Protected t=(j-i+1)/3
    Stooge_Sort(L(), i,   j-t)
    Stooge_Sort(L(), i+t, j )
    Stooge_Sort(L(), i,   j-t)
  EndIf
EndProcedure
Implementation may be as
Define AmountOfPosts=(?Stop_Data-?Start_data)/SizeOf(Integer)
Dim    Xyz.i(AmountOfPosts)
CopyMemory(?Start_data, @Xyz(), ?Stop_Data-?Start_data)
 
Stooge_Sort(Xyz())
 
For i=0 To ArraySize(Xyz())
  Debug Xyz(i)
Next i
 
DataSection
  Start_data:
  Data.i  1, 4, 5, 3, -6, 3, 7, 10, -2, -5, 7, 5, 9, -3, 7
  Stop_Data:
EndDataSection

[edit] Python

>>> data = [1, 4, 5, 3, -6, 3, 7, 10, -2, -5, 7, 5, 9, -3, 7]
>>> def stoogesort(L, i=0, j=None):
	if j is None:
		j = len(L) - 1
	if L[j] < L[i]:
		L[i], L[j] = L[j], L[i]
	if j - i > 1:
		t = (j - i + 1) // 3
		stoogesort(L, i  , j-t)
		stoogesort(L, i+t, j  )
		stoogesort(L, i  , j-t)
	return L
 
>>> stoogesort(data)
[-6, -5, -3, -2, 1, 3, 3, 4, 5, 5, 7, 7, 7, 9, 10]

This alternate solution uses a wrapper function to compute the initial value of j rather than detecting the sentinel value None. 

>>> def stoogesort(L, i, j):
	if L[j] < L[i]:
		L[i], L[j] = L[j], L[i]
	if j - i > 1:
		t = (j - i + 1) // 3
		stoogesort(L, i  , j-t)
		stoogesort(L, i+t, j  )
		stoogesort(L, i  , j-t)
	return L
 
>>> def stooge(L): return stoogesort(L, 0, len(L) - 1)
 
>>> data = [1, 4, 5, 3, -6, 3, 7, 10, -2, -5, 7, 5, 9, -3, 7]
>>> stooge(data)
[-6, -5, -3, -2, 1, 3, 3, 4, 5, 5, 7, 7, 7, 9, 10]

[edit] Racket

 
#lang racket
(define (stooge-sort xs [i 0] [j (- (vector-length xs) 1)])
  (define (x i) (vector-ref xs i))
  (define (x! i v) (vector-set! xs i v))
  (define (swap! i j) (define t (x i)) (x! i (x j)) (x! j t))
  (when (> (x i) (x j)) (swap! i j))
  (when (> (- j i) 1)
    (define t (quotient (+ j (- i) 1) 3))
    (stooge-sort xs i (- j t))
    (stooge-sort xs (+ i t) j)
    (stooge-sort xs i (- j t)))
  xs)
 

[edit] REXX

This REXX example starts an array at element zero (but any integer could be used);
zero was used because the algorithm shown in the task used zero. 

/*REXX program to sort an integer array   L   [elements start at zero]. */
highItem=19                            /*define  0 ──► 19  elements.    */
widthH=length(highItem)                /*width of biggest element number*/
widthL=0                               /*width of largest element value.*/
 
    do k=0  to highItem                /*populate the array with stuff. */
    L.k=2*k + (k * -1**k)              /*kinda generate randomish nums. */
    if L.k==0  then L.k=-100-k         /*if zero, make a negative number*/
    widthL=max(widthL,length(L.k))     /*compute maximum width so far.  */
    end   /*k*/
 
call showL 'before sort'               /*show the before array elements.*/
call stoogeSort 0,highItem             /*invoke the Stooge Sort.        */
call showL ' after sort'               /*show the  after array elements.*/
exit                                   /*stick a fork in it, we're done.*/
/*──────────────────────────────────SHOWL subroutine────────────────────*/
showL: sepLength=22+widthH+widthL      /*compute separator width.       */
say copies('-',sepLength)              /*show the 1st separator line.   */
 
               do j=0  to highItem
               say 'element' right(j,widthH) arg(1)":" right(L.j,widthL)
               end    /*j*/
 
say copies('=', sepLength)             /*show the 2nd separator line.   */
return
/*──────────────────────────────────STOOGESORT subroutine───────────────*/
stoogeSort: procedure expose L.;  parse arg i,j     /*sort from I ──> J.*/
if L.j<L.i then parse value L.i L.j  with  L.j L.i  /*swap  L.i with L.j*/
if j-i>1  then do
               t=(j-i+1) % 3           /* %  is REXX integer division.  */
               call stoogesort i  , j-t
               call stoogesort i+t, j
               call stoogesort i  , j-t
               end
return

output 

----------------------------
element  0 before sort: -100
element  1 before sort:    1
element  2 before sort:    6
element  3 before sort:    3
element  4 before sort:   12
element  5 before sort:    5
element  6 before sort:   18
element  7 before sort:    7
element  8 before sort:   24
element  9 before sort:    9
element 10 before sort:   30
element 11 before sort:   11
element 12 before sort:   36
element 13 before sort:   13
element 14 before sort:   42
element 15 before sort:   15
element 16 before sort:   48
element 17 before sort:   17
element 18 before sort:   54
element 19 before sort:   19
============================
----------------------------
element  0  after sort: -100
element  1  after sort:    1
element  2  after sort:    3
element  3  after sort:    5
element  4  after sort:    6
element  5  after sort:    7
element  6  after sort:    9
element  7  after sort:   11
element  8  after sort:   12
element  9  after sort:   13
element 10  after sort:   15
element 11  after sort:   17
element 12  after sort:   18
element 13  after sort:   19
element 14  after sort:   24
element 15  after sort:   30
element 16  after sort:   36
element 17  after sort:   42
element 18  after sort:   48
element 19  after sort:   54
============================

[edit] Ruby

class Array
  def stoogesort
    self.dup.stoogesort!
  end
 
  def stoogesort!(i = 0, j = self.length-1)
    if self[j] < self[i]
      self[i], self[j] = self[j], self[i]
    end
    if j - i > 1
      t = (j - i + 1)/3
      stoogesort!(i, j-t)
      stoogesort!(i+t, j)
      stoogesort!(i, j-t)
    end
    self
  end
end
 
p [1,4,5,3,-6,3,7,10,-2,-5].stoogesort

output 

[-6, -5, -2, 1, 3, 3, 4, 5, 7, 10]

[edit] Smalltalk

Works with: GNU Smalltalk
OrderedCollection extend [
    stoogeSortFrom: i to: j [
	(self at: j) < (self at: i)
	  ifTrue: [ self swapElement: i with: j ].
	j - i > 1
          ifTrue: [
	      |t| t := (j - i + 1)//3.
	      self stoogeSortFrom: i to: (j-t).
	      self stoogeSortFrom: (i+t) to: j.
	      self stoogeSortFrom: i to: (j-t)
          ]
    ]
    stoogeSort [ self stoogeSortFrom: 1 to: (self size) ]
    swapElement: i with: j [
	|t| t := self at: i.
        self at: i put: (self at: j).
	self at: j put: t
    ]
].
 
|test|
test := #( 1 4 5 3 -6 3 7 10 -2 -5) asOrderedCollection.
test stoogeSort.
test printNl.

[edit] Tcl

Works with: Tcl version 8.5
package require Tcl 8.5
 
proc stoogesort {L {i 0} {j -42}} {
   if {$j == -42} {# Magic marker
      set j [expr {[llength $L]-1}]
   }
   set Li [lindex $L $i]
   set Lj [lindex $L $j]
   if {$Lj < $Li} {
      lset L $i $Lj
      lset L $j $Li
   }      
   if {$j-$i > 1} {
      set t [expr {($j-$i+1)/3}]
      set L [stoogesort $L $i [expr {$j-$t}]]
      set L [stoogesort $L [expr {$i+$t}] $j]
      set L [stoogesort $L $i [expr {$j-$t}]]
   }
   return $L
}
 
stoogesort {1 4 5 3 -6 3 7 10 -2 -5}

Output: 

-6 -5 -2 1 3 3 4 5 7 10

[edit] XPL0

code ChOut=8, IntOut=11;        \intrinsic routines
 
proc StoogeSort(L, I, J);       \Sort array L
int L, I, J;
int  T;
[if L(J) < L(I) then
    [T:= L(I);  L(I):= L(J);  L(J):= T]; \swap
if J-I > 1 then
    [T:= (J-I+1)/3;
    StoogeSort(L, I, J-T);
    StoogeSort(L, I+T, J);
    StoogeSort(L, I, J-T);
    ];
];
 
int A, I;
[A:= [3, 1, 4, 1, -5, 9, 2, 6, 5, 4];
StoogeSort(A, 0, 10-1);
for I:= 0 to 10-1 do [IntOut(0, A(I));  ChOut(0, ^ )];
]
Output:
-5 1 1 2 3 4 4 5 6 9

[edit] Yorick

Based on pseudocode, except using Yorick's 1-based arrays. Sorts in place. 

func stoogesort(&L, i, j) {
  if(is_void(i)) i = 1;
  if(is_void(j)) j = numberof(L);
  if(L(j) < L(i))
    L([i,j]) = L([j,i]);
  if(j - i > 1) {
    t = (j - i + 1)/3;
    stoogesort, L, i, j-t;
    stoogesort, L, i+t, j;
    stoogesort, L, i, j-t;
  }
}

Example interactive use: 

> foo = [1,4,5,3,-6,3,7,10,-2,-5]
> stoogesort, foo
> foo
[-6,-5,-2,1,3,3,4,5,7,10]
Retrieved from "http://rosettacode.org/mw/index.php?title=Sorting_algorithms/Stooge_sort&oldid=157136"
Personal tools
Namespaces

Variants
Actions
Community
Explore
Misc
Toolbox