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
Output:
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++

 
#include <iostream>
#include <time.h>
 
//------------------------------------------------------------------------------
using namespace std;
 
//------------------------------------------------------------------------------
class stooge
{
public:
void sort( int* arr, int start, int end )
{
if( arr[start] > arr[end - 1] ) swap( arr[start], arr[end - 1] );
int n = end - start; if( n > 2 )
{
n /= 3; sort( arr, start, end - n );
sort( arr, start + n, end ); sort( arr, start, end - n );
}
}
};
//------------------------------------------------------------------------------
int main( int argc, char* argv[] )
{
srand( static_cast<unsigned int>( time( NULL ) ) ); stooge s; int a[80], m = 80;
cout << "before:\n";
for( int x = 0; x < m; x++ ) { a[x] = rand() % 40 - 20; cout << a[x] << " "; }
s.sort( a, 0, m ); cout << "\n\nafter:\n";
for( int x = 0; x < m; x++ ) cout << a[x] << " "; cout << "\n\n";
return system( "pause" );
}
 
Output:
before:
5 -15 11 18 -14 -20 6 -4 -1 -8 12 -18 -12 -4 -10 -8 13 4 0 16 7 -13 -13 -1 11 -9
 13 -14 9 -19 -1 14 6 -4 7 -8 -15 -11 -9 3 10 3 -2 -5 12 -8 -2 10 -10 9 14 9 -12
 19 -16 -6 -13 -18 -3 -13 -12 8 -8 -10 -16 5 8 -10 -10 6 -14 -20 -16 7 15 11 -19
 -18 10 -15

after:
-20 -20 -19 -19 -18 -18 -18 -16 -16 -16 -15 -15 -15 -14 -14 -14 -13 -13 -13 -13
-12 -12 -12 -11 -10 -10 -10 -10 -10 -9 -9 -8 -8 -8 -8 -8 -6 -5 -4 -4 -4 -3 -2 -2
 -1 -1 -1 0 3 3 4 5 5 6 6 6 7 7 7 8 8 9 9 9 10 10 10 11 11 11 12 12 13 13 14 14
15 16 18 19

[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] COBOL

Works with: GNU Cobol
       >>SOURCE FREE
IDENTIFICATION DIVISION.
PROGRAM-ID. stooge-sort-test.
 
DATA DIVISION.
WORKING-STORAGE SECTION.
01 Arr-Len CONSTANT 7.
 
01 arr-area VALUE "00004001000020000005000230000000000".
03 arr-elt PIC 9(5) OCCURS Arr-Len TIMES
INDEXED BY arr-idx.
 
PROCEDURE DIVISION.
DISPLAY "Unsorted: " NO ADVANCING
PERFORM VARYING arr-idx FROM 1 BY 1 UNTIL Arr-Len < arr-idx
DISPLAY arr-elt (arr-idx) " " NO ADVANCING
END-PERFORM
DISPLAY SPACE
 
CALL "stooge-sort" USING arr-area, OMITTED, OMITTED
 
DISPLAY "Sorted: " NO ADVANCING
PERFORM VARYING arr-idx FROM 1 BY 1 UNTIL Arr-Len < arr-idx
DISPLAY arr-elt (arr-idx) " " NO ADVANCING
END-PERFORM
DISPLAY SPACE
.
END PROGRAM stooge-sort-test.
 
 
IDENTIFICATION DIVISION.
PROGRAM-ID. stooge-sort RECURSIVE.
 
DATA DIVISION.
LOCAL-STORAGE SECTION.
01 Arr-Len CONSTANT 7.
 
01 i PIC 99 COMP.
01 j PIC 99 COMP.
 
01 temp PIC 9(5).
 
01 t PIC 99 COMP.
 
LINKAGE SECTION.
01 arr-area.
03 arr-elt PIC 9(5) OCCURS Arr-Len TIMES.
 
01 i-val PIC 99 COMP.
01 j-val PIC 99 COMP.
 
PROCEDURE DIVISION USING arr-area, OPTIONAL i-val, OPTIONAL j-val.
IF i-val IS OMITTED
MOVE 1 TO i
ELSE
MOVE i-val TO i
END-IF
IF j-val IS OMITTED
MOVE Arr-Len TO j
ELSE
MOVE j-val TO j
END-IF
 
IF arr-elt (j) < arr-elt (i)
MOVE arr-elt (i) TO temp
MOVE arr-elt (j) TO arr-elt (i)
MOVE temp TO arr-elt (j)
END-IF
 
IF j - i + 1 >= 3
COMPUTE t = (j - i + 1) / 3
SUBTRACT t FROM j
CALL "stooge-sort" USING arr-area, CONTENT i, j
ADD t TO i, j
CALL "stooge-sort" USING arr-area, CONTENT i, j
SUBTRACT t FROM i, j
CALL "stooge-sort" USING arr-area, CONTENT i, j
END-IF
.
END PROGRAM stooge-sort.
Output:
Unsorted: 00004 00100 00200 00005 00023 00000 00000
Sorted:   00000 00000 00004 00005 00023 00100 00200

[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.

Output:
Abbreviated sample
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
Output:
>> stoogeSort([1 -6 4 -9],1,4)
 
ans =
 
-9 -6 1 4

[edit] MAXScript

fn stoogeSort arr i: j: =
(
if i == unsupplied do i = 1
if j == unsupplied do j = arr.count
 
if arr[j] < arr[i] do
(
swap arr[j] arr[i]
)
if j - i > 1 do
(
local t = (j - i+1)/3
arr = stoogeSort arr i:i j:(j-t)
arr = stoogeSort arr i:(i+t) j:j
arr = stoogeSort arr i:i j:(j-t)
)
return arr
)
Output:
a = for i in 1 to 15 collect random 1 20
#(10, 2, 1, 19, 18, 20, 18, 5, 13, 2, 13, 9, 7, 10, 6)
stoogeSort a
#(1, 2, 2, 5, 6, 7, 9, 10, 10, 13, 13, 18, 18, 19, 20)
 

[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] Nimrod

proc stoogeSort[T](a: var openarray[T], i, j: int) =
if a[j] < a[i]: swap a[i], a[j]
if j - i > 1:
let t = (j - i + 1) div 3
stoogeSort(a, i, j - t)
stoogeSort(a, i + t, j)
stoogeSort(a, i, j - t)
 
var a = @[4, 65, 2, -31, 0, 99, 2, 83, 782]
stoogeSort a, 0, a.high
echo a
Output:
@[-31, 0, 2, 2, 4, 65, 83, 99, 782]

[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).

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
Output:
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] Sidef

func stooge(x, i, j) {
x[j] < x[i] && (
x[i, j] = x[j, i];
);
 
j-i > 1 && (
var t = ((j - i + 1) / 3);
stooge(x, i, j - t);
stooge(x, i + t, j );
stooge(x, i, j - t);
);
}
 
var a = 20.of { 100.rand.int };
 
say "Before #{a}";
stooge(a, 0, a.offset);
say "After #{a}";

[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]
Personal tools
Namespaces

Variants
Actions
Community
Explore
Misc
Toolbox