Stooge sort

O Stooge Sort, ou ordenação "Pateta", é um algoritmo de ordenação que se faz do uso das técnicas de divisão e conquista, ou seja, recursivamente o algoritmo realiza partições virtuais da entrada e transforma o problema maior em pequenos subproblemas até que a ordenação seja mínima. A complexidade deste algoritmo é de O(n^{log 3 / log 1.5}) = O(n^2.7). Comparado a outros algoritmos de ordenação mais conhecidos, como o Insertion Sort e o Bubble Sort, ele chega a ser mais lento. Devido à sua ineficiência, recomenda-se que não seja usado na ordenação de grandes volumes de dados.

Stooge sort
classe	Algoritmo de ordenação
estrutura de dados	Array
complexidade pior caso	O(n2.709...) ou O(nlog3 / log1.5)
complexidade de espaços pior caso	O(n)
Algoritmos

O nome do algoritmo faz referência a uma comédia norte-americana chamada The Three Stooges (em português, Os Três Patetas), em que Moe batia repetidamente nos outros dois patetas, assim como o Stooge Sort repetidamente ordena 2/3 do array.

Ideia geral

Segue, abaixo, a explicação do algoritmo:

• Se o valor da esquerda é maior que o valor da direita, troca-se os dois;
• Se houver 3 ou mais elementos no array, então:
  • Realizar a chamada recursiva para os 2/3 iniciais do array.
  • Realizar a chamada recursiva para os 2/3 finais do array.
  • Realizar a chamada recursiva para os 2/3 iniciais do array.
• Caso contrário:
  • Retornar o array.

Observação: Para as chamadas recursivas, é necessário obter um arredondamento para cima (teto) de 2/3 do tamanho do array; caso contrário, o algoritmo pode entrar numa chamada infinita de recursão, para arrays de determinado comprimento.

Pseudocódigo

stoogeSort(A, inicio, fim)
if A[fim] < A[inicio]
	Object temp = A[inicio];
	A[inicio] = A[fim];
	A[fim] = temp;
if inicio + 1 >= fim
	return

k = (fim - inicio + 1) / 3
stoogeSort(A, inicio, fim-k)
stoogeSort(A, inicio+k, fim)
stoogeSort(A, inicio, fim -k)

Relação de Recorrência

stoogeSort(A, inicio, fim):
    if A[fim] < A[inicio] # C
    	Object temp = A[inicio]; # C
    	A[inicio] = A[fim]; # C
    	A[fim] = temp; # C
    if inicio + 1 >= fim # C
    	return # C

    k = (fim - inicio + 1) / 3 # C
    stoogeSort(A, inicio, fim - k) # T([(2/3) * n])
    stoogeSort(A, inicio + k, fim) # T([(2/3) * n])
    stoogeSort(A, inicio, fim - k) # T([(2/3) * n])

Como mostrado no pseudocódigo acima, a relação de recorrência do algoritmo é dada por: T(n) = 3 * T([(2/3) * n]) + O(1).

Aplicando o Teorema Mestre podemos chegar no custo do algoritmo.

Ex: F(n) = 1 = O(n^c), onde c = 0, a = 3, b = 3/2 ∴ log3/2 (3) =~ 2.70

Tendo c < log3/2 (3), chegamos no caso 1 do teorema, logo:

T(n) = O(n^{log3/2 (3)}) ≈ O(n^2.70).

Comparação com outros algoritmos

O tempo de execução do algoritmo é o mesmo tanto no melhor caso quanto no pior, pois seu desempenho independe da ordem dos elementos do array de entrada. Logo, quando comparado com outros algoritmos, é fácil perceber que este é o que possui o pior desempenho, como mostra a tabela abaixo:

Ordenação	Tempo
	Médio	Melhor	Pior
Stooge Sort	O(n2.70)	O(n2.70)	O(n2.70)
Bubble Sort	O(n2)	O(n2)	O(n2)
Bubble Sort Melhorado	O(n2)	O(n)	O(n2)
Insertion Sort	O(n2)	O(n)	O(n2)
Selection Sort	O(n2)	O(n2)	O(n2)
Heap Sort	O(n*log(n))	O(n*log(n))	O(n*log(n))
Merge Sort	O(n*log(n))	O(n*log(n))	O(n*log(n))
Quicksort	O(n*log(n))	O(n*log(n))	O(n2)

Fonte

Assim o Stooge sort é um dos piores algoritmos de ordenação, em tempo de execução, tendo como concorrente o Bogosort.

Características

• O Stooge Sort é um algoritmo que realiza a ordenação no mesmo local que estão armazenados os dados, logo, defini-se o mesmo como In-Place.
• Este algoritmo não é estável em alguns casos. Define-se por estável, se dados dois elementos R e S, os quais possuem mesmo valor, se R aparece antes de S na lista original, R aparecerá antes de S na lista ordenada final. No entanto, dependendo de como é realizado o swap - troca entre elementos do array -, a estabilidade não é preservada, característico deste algoritmo.
• O algoritmo possui baixa eficiência, observado em sua complexidade O(n^2.7), sendo característico que independente da lista está ordenada ou não, o tempo de execução do mesmo, no melhor e no pior caso, preservará sua complexidade.
• O algoritmo não é tão simples (implementação, leitura e manutenção) quando comparado com o Bubble sort, o Selection sort e o Insertion sort, pois o mesmo realiza várias chamadas recursivas que dificultam sua compreensão. Logo, a implementação do mesmo não é indicada para utilização na prática.
• O Stooge Sort não é confiável, pois há possibilidades de que, em alguns casos, suas chamadas recursivas não tenham fim.
• O algoritmo não faz uso de estruturas auxiliares para realizar a ordenação, fazendo assim com que sua complexidade de espaço adicional não seja maior que O(n).

Implementações

VisualG

// exemplo de ordenação por Stooge Sort

Algoritmo "Stooge Sort"

procedimento stoogeSort (a: vetor [] de inteiro; ini, fim: inteiro)
//declarando variaveis
k, aux: inteiro

inicio

se a[fim] < a[ini] entao
	aux <- a[ini]
	a[ini] <- a[fim]
	a[fim] <- aux
fimse

se ini + 1 > fim entao
	fimprocedimento
fimse

k <- (fim - ini + 1) / 3
stoogeSort(a; ini; fim - k)
stoogeSort(a; ini + k; fim)
stoogeSort(a; ini; fim - k)

fimprocedimento

Fimalgoritmo

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;
}

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" );
}

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);
    }
}

Fortran

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

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);
        }
    }
}

JavaScript

function stoogeSort (array, i, j) {
    if (j === undefined) {
        j = array.length - 1;
    }

    if (i === undefined) {
        i = 0;
    }

    if (array[j] < array[i]) {
        var aux = array[i];
        array[i] = array[j];
        array[j] = aux;
    }

    if (j - i > 1) {
        var t = Math.floor((j - i + 1) / 3);
        stoogeSort(array, i, j-t);
        stoogeSort(array, i+t, j);
        stoogeSort(array, i, j-t);
    }
};

Lua

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}))

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.

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);
	}
}

Python

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

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])
    }
}

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

MATLAB

%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

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";

R

stoogesort = function(vect) {
	i = 1
	j = length(vect)
	if(vect[j] < vect[i])  vect[c(j, i)] = vect[c(i, j)]
	if(j - i > 1) {
		t = (j - i + 1) %/% 3
		vect[i:(j - t)] = stoogesort(vect[i:(j - t)])
		vect[(i + t):j] = stoogesort(vect[(i + t):j])
		vect[i:(j - t)] = stoogesort(vect[i:(j - t)])
	}
	vect
}

v = sample(21, 20)
k = stoogesort(v)
v
k

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

Referências

• Black, Paul E. «stooge sort». Dictionary of Algorithms and Data Structures. National Institute of Standards and Technology. Consultado em 8 de julho de 2016 
• Cormen, Thomas H. «stooge sort». Introduction to Algorithms 2 ed. MIT Press and McGraw-Hill. pp. 161–162. ISBN 0-262-03293-7. Consultado em 8 de julho de 2016 

Ligações externas

• Stooge Sort Algorithm Animation - algostructure.com
• Stooge Sort - xlinux.nist.gov
• Sorting algorithms/Stooge sort - Rosetta Code

Ver também

• Merge sort
• Quicksort
• Selection sort
• Radix sort
• Pesquisa binária
• Heapsort
• Shell sort

Métodos de pesquisa

• Algoritmos de ordenação
• Ordenação por comparação