Sorting algorithms/Stooge sort: Difference between revisions

{{trans|Python}}

 

I l[j] < l[i]

swap(&l[i], &l[j])

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

stooge(&data)

 

{{out}}

=={{header|Action!}}==

Action! language does not support recursion. Therefore an iterative approach with a stack has been proposed.

INT ARRAY stack(MAX_COUNT)

INT stackSize

Test(c,8)

Test(d,12)

{{out}}

[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Stooge_sort.png Screenshot from Atari 8-bit computer]

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

 

procedure Stooge is

type Integer_Array is array (Positive range <>) of Integer;

end loop;

Ada.Text_IO.New_Line;

 

{{out}}

=={{header|ALGOL 68}}==

{{works with|ALGOL 68G|Any - tested with release 2.8.win32}}

PRIO =:= = 1;

OP =:= = ( REF INT a, b )VOID: ( INT t := a; a := b; b := t );

# test the stooge sort #

[]INT data = ( 67, -201, 0, 9, 9, 231, 4 );

{{out}}

<pre>

 

=={{header|AutoHotkey}}==

if !j

j := L.MaxIndex()

}

return L

return

 

res .= v ","

return trim(res, ",")

Outputs:<pre>-12,0,3,6,51,73,123</pre>

 

It ''definitely'' does '''not''' work with QBasic.

 

 

RANDOMIZE TIMER

stoogesort L(), i, j - t

END IF

 

{{out}}

 

=={{header|BBC BASIC}}==

test%() = 4, 65, 2, -31, 0, 99, 2, 83, 782, 1

PROCstoogesort(test%(), 0, DIM(test%(),1))

PROCstoogesort(l%(), i%, j%-t%)

ENDIF

{{out}}

<pre>

 

=={{header|BCPL}}==

 

let stoogesort(L, i, j) be

stoogesort(array, 0, length-1)

write("After: ", array, length)

{{out}}

<pre>Before: 4 65 2 -31 0 99 2 83 782 1

 

=={{header|C}}==

 

#define SWAP(r,s) do{ t=r; r=s; s=t; } while(0)

return 0;

 

=={{header|C sharp|C#}}==

if (list.Count > 1) {

StoogeSort(list, 0, list.Count - 1);

StoogeSort(L, i, j - t);

}

 

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

#include <iostream>

#include <time.h>

return system( "pause" );

}

{{out}}

<pre>

 

=={{header|Clojure}}==

(assoc! v y (v x) x (v y)))

 

(stooge-sort v (+ i t) j)

(stooge-sort v i (- j t))))

 

=={{header|COBOL}}==

{{works with|GNU Cobol}}

IDENTIFICATION DIVISION.

PROGRAM-ID. stooge-sort-test.

END-IF

.

 

{{out}}

 

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

(when (> (aref vector i) (aref vector j))

(rotatef (aref vector i) (aref vector j)))

(stooge-sort vector (+ i third) j)

(stooge-sort vector i (- j third))))

 

=={{header|D}}==

 

void stoogeSort(T)(T[] seq) pure nothrow {

data.stoogeSort();

writeln(data);

{{out}}

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

 

=={{header|Eiffel}}==

class

STOOGE_SORT

end

end

Test:

class

APPLICATION

 

end

{{out}}

<pre>

=={{header|Elena}}==

ELENA 4.x :

import system'routines;

console.printLine("before:", list.asEnumerable());

console.printLine("after:", list.stoogeSort().asEnumerable())

{{out}}

<pre>

 

=={{header|Elixir}}==

def stooge_sort(list) do

stooge_sort(List.to_tuple(list), 0, length(list)-1) |> Tuple.to_list

 

(for _ <- 1..20, do: :rand.uniform(20)) |> IO.inspect

 

{{out}}

 

=={{header|Euphoria}}==

object temp

integer t

 

? s

 

{{out}}

 

=={{header|Factor}}==

IN: rosetta-code.stooge-sort

 

{ 1 4 5 3 -6 3 7 10 -2 -5 } stooge-sort . ;

 

{{out}}

<pre>

=={{header|Fortran}}==

{{works with|Fortran|90 and later}}

implicit none

 

 

end subroutine

 

=={{header|FreeBASIC}}==

' compile with: fbc -s console

 

Print : Print "hit any key to end program"

Sleep

{{out}}

<pre>Unsorted

 

=={{header|Go}}==

 

import "fmt"

stoogesort(a[:len(a)-t])

}

 

=={{header|Haskell}}==

 

import Control.Arrow

import Control.Monad

xs'

| xs!!j < xs!!i = swapElems xs i j

Example:

 

=={{header|Icon}} and {{header|Unicon}}==

demosort(stoogesort,[3, 14, 1, 5, 9, 2, 6, 3],"qwerty")

end

}

return X # X must be returned and assigned to sort a string

 

Note: This example relies on [[Sorting_algorithms/Bubble_sort#Icon| the supporting procedures 'sortop', and 'demosort' in Bubble Sort]].

 

=={{header|IS-BASIC}}==

110 RANDOMIZE

120 NUMERIC ARRAY(5 TO 16)

350 CALL STOOGESORT(A,I,J-T)

360 END IF

 

=={{header|J}}==

 

stoogeSort=: 3 : 0

(x-0,t) stoogeSort (x+t,0) stoogeSort (x-0,t) stoogeSort y

else. y end.

Example:

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

 

=={{header|Java}}==

 

public class Stooge {

}

}

{{out}}

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

 

=={{header|JavaScript}}==

if (j === undefined) {

j = array.length - 1;

stoogeSort(array, i, j-t);

}

Example:

stoogeSort(arr);

{{out}}

<pre>[1, 2, 3, 4, 9, 10, 13]</pre>

=={{header|jq}}==

{{works with|jq|1.4}}

def swap(i;j): .[i] as $t | .[i] = .[j] | .[j] = $t;

end;

 

'''Example'''

[1],

[1,2],

[1,3,2,4],

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

{{out}}

[]

[1]

[1,2]

[1,2,3,4]

 

=={{header|Julia}}==

{{works with|Julia|0.6}}

{{trans|Matlab}}

if a[j] < a[i]

a[[i, j]] = a[[j, i]];

 

x = randn(10)

 

{{out}}

 

=={{header|Kotlin}}==

 

fun stoogeSort(a: IntArray, i: Int, j: Int) {

stoogeSort(a, 0, a.size - 1)

println("Sorted : ${a.asList()}")

 

{{out}}

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)

print(unpack(stoogesort{9,7,8,5,6,3,4,2,1,0}))

 

 

=={{header|Maple}}==

local temp := arr[a];

arr[a] := arr[b];

 

arr := Array([4, 2, 6, 1, 3, 7, 9, 5, 8]):

{{out}}

<pre>

 

=={{header|Mathematica}}/{{header|Wolfram Language}}==

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

{{out}}

<pre>stoogeSort[{3,2,9,6,8},1,5]

 

=={{header|MATLAB}} / {{header|Octave}}==

%i = 1

%j = length(list)

end

 

{{out}}

 

ans =

 

 

=={{header|MAXScript}}==

(

if i == unsupplied do i = 1

)

return arr

{{out}}

#(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)

 

=={{header|NetRexx}}==

options replace format comments java crossref savelog symbols binary

 

 

return L_

{{out}}

<pre>

 

=={{header|Nim}}==

if a[j] < a[i]: swap a[i], a[j]

if j - i > 1:

var a = @[4, 65, 2, -31, 0, 99, 2, 83, 782]

stoogeSort a, 0, a.high

{{out}}

<pre>@[-31, 0, 2, 2, 4, 65, 83, 99, 782]</pre>

 

=={{header|Objeck}}==

bundle Default {

class Stooge {

}

}

 

=={{header|OCaml}}==

 

let tmp = ar.(i) in

ar.(i) <- ar.(j);

end

in

 

testing:

let ar = [| 3; 1; 7; 2; 6; 5; 4; 9; 8 |] in

stoogesort ar;

Array.iter (Printf.printf " %d") ar;

 

=={{header|ooRexx}}==

{{Trans|NetRexx}}

 

call demo

self~put(item, ix)

return

{{out}}

<pre>

 

=={{header|Oz}}==

proc {StoogeSort Arr}

proc {Swap I J}

for I in {Array.low Arr}..{Array.high Arr} do

{System.printInfo Arr.I#", "}

 

{{out}}

 

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

local(v=v); \\ Give children access to v

ss(1,#v); \\ Sort

ss(i,j-t)

)

 

=={{header|Pascal}}==

type

end;

writeln;

{{out}}

<pre>./StoogeSort

 

=={{header|Perl}}==

use integer;

my ($x, $i, $j) = @_;

stooge(\@a);

print "After @a\n";

 

=={{header|Phix}}==

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #0000FF;">?</span><span style="color: #000000;">stoogesort</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>

{{out}}

<pre>

 

=={{header|PHP}}==

function stoogeSort(&$arr, $i, $j)

{

}

}

 

=={{header|PicoLisp}}==

(default N (length L))

(let P (nth L N)

(stoogeSort (nth L (inc D)) (- N D))

(stoogeSort L (- N D)) ) )

Test:

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

 

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

declare L(*) fixed binary;

declare (i, j, t, temp) fixed binary;

end;

end;

 

=={{header|PowerBASIC}}==

This version is closely based on the BASIC code above.

 

 

SUB stoogesort (L() AS LONG, i AS LONG, j AS LONG)

 

? s

 

{{out}}

 

=={{header|PowerShell}}==

{

$i = 0

}

 

 

=={{header|PureBasic}}==

If j=0

j=ArraySize(L())

Stooge_Sort(L(), i, j-t)

EndIf

Dim Xyz.i(AmountOfPosts)

CopyMemory(?Start_data, @Xyz(), ?Stop_Data-?Start_data)

Data.i 1, 4, 5, 3, -6, 3, 7, 10, -2, -5, 7, 5, 9, -3, 7

Stop_Data:

 

=={{header|Python}}==

>>> def stoogesort(L, i=0, j=None):

if j is None:

 

>>> stoogesort(data)

 

This alternate solution uses a wrapper function

to compute the initial value of ''j''

rather than detecting the sentinel value ''None''.

if L[j] < L[i]:

L[i], L[j] = L[j], L[i]

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

>>> stooge(data)

 

=={{header|Quackery}}==

 

 

[ dup 0 peek over -1 peek

[] 33 times [ 90 random 10 + join ]

dup echo cr

 

{{out}}

 

=={{header|R}}==

i = 1

j = length(vect)

k = stoogesort(v)

v

{{out}}

<pre>

 

=={{header|Racket}}==

#lang racket

(define (stooge-sort xs [i 0] [j (- (vector-length xs) 1)])

(stooge-sort xs i (- j t)))

xs)

 

=={{header|Raku}}==

(formerly Perl 6)

@L[$j,$i] = @L[$i,$j] if @L[$i] > @L[$j];

 

 

stoogesort(@L).Str.say;

 

=={{header|REXX}}==

This REXX example starts an array at element zero &nbsp; (but any integer could be used); &nbsp; a zero-

<br>based index was used because the algorithm shown in the Rosetta Code task used zero.

parse arg N . /*obtain an optional argument from C.L.*/

if N=='' | N=="," then N=19 /*Not specified? Then use the default.*/

call stoogeSort i , j-t /* " " */

end

{{out|output|text=&nbsp; when using the default (internal generated) inputs:}}

 

 

=={{header|Ring}}==

test = [4, 65, 2, -31, 0, 99, 2, 83, 782, 1]

stoogeSort(test, 1, len(test))

stoogeSort(list, i, j-t) ok

return list

Output:

<pre>

 

=={{header|Ruby}}==

def stoogesort

self.dup.stoogesort!

end

 

 

{{out}}

 

=={{header|Rust}}==

where E: PartialOrd

{

stoogesort(&mut numbers);

println!("After: {:?}", &numbers);

 

=={{header|Scala}}==

def stoogeSort(a: Array[Int], i: Int, j: Int) {

if (a(j) < a(i)) {

stoogeSort(a, 0, a.length - 1)

println(s"Sorted : ${a.mkString(", ")}")

 

See it running in your browser by [https://scastie.scala-lang.org/QTCrb5SNTVqDNC6oRQRmZw Scastie (JVM)].

 

=={{header|Sidef}}==

if (x[j] < x[i]) {

x.swap(i, j)

say "Before #{a}"

stooge(a, 0, a.end)

 

=={{header|Smalltalk}}==

{{works with|GNU Smalltalk}}

stoogeSortFrom: i to: j [

(self at: j) < (self at: i)

test := #( 1 4 5 3 -6 3 7 10 -2 -5) asOrderedCollection.

test stoogeSort.

 

Here is a "functional" variation (a 1:1 adaption of the original algorithm):

(L at:i) > (L at:j) ifTrue:[

L swap:i with:j

a := #(1 4 5 3 -6 3 7 10 -2 -5 7 5 9 -3 7) copy.

stoogesort value:a value:1 value:a size.

 

Output:

 

=={{header|Swift}}==

if j == -1 {

j = arr.count - 1

stoogeSort(&a)

 

{{out}}

<pre>

=={{header|Tcl}}==

{{works with|Tcl|8.5}}

 

proc stoogesort {L {i 0} {j -42}} {

}

 

{{out}}

<pre>-6 -5 -2 1 3 3 4 5 7 10</pre>

=={{header|uBasic/4tH}}==

{{trans|BBC BASIC}}

n = FUNC (_InitArray)

PROC _ShowArray (n)

PRINT

 

=={{header|Wren}}==

stoogeSort = Fn.new { |a, i, j|

if (a[j] < a[i]) {

System.print("After : %(a)")

System.print()

 

{{out}}

 

=={{header|XPL0}}==

 

proc StoogeSort(L, I, J); \Sort array L

StoogeSort(A, 0, 10-1);

for I:= 0 to 10-1 do [IntOut(0, A(I)); ChOut(0, ^ )];

 

{{out}}

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

Sorts in place.

if(is_void(i)) i = 1;

if(is_void(j)) j = numberof(L);

stoogesort, L, i, j-t;

}

 

Example interactive use:

 

=={{header|zkl}}==

if(list[j]<list[i]) list.swap(i,j);

if(j - i >1){

}

list

{{out}}

<pre>