Stooge sort

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
	Esta caixa: ver; discutir;

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.

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.^[1] 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(n^2.70)	O(n^2.70)	O(n^2.70)
Bubble Sort	O(n²)	O(n²)	O(n²)
Bubble Sort Melhorado	O(n²)	O(n)	O(n²)
Insertion Sort	O(n²)	O(n)	O(n²)
Selection Sort	O(n²)	O(n²)	O(n²)
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(n²)

Fonte^[2]

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

Ver também

Métodos de pesquisa

Galeria

↑ Fink, Eugene. «Analysis of Algorithms: Solutions 3» (PDF). Analysis of Algorithms: Solutions 3. Carnegie Mellon University. Consultado em 9 de julho de 2016
↑ Allain, Alex. «Sorting Algorithms Compared - Cprogramming.com». Sorting Algorithm Comparison. www.cprogramming.com. Consultado em 9 de julho de 2016

[1] Fink, Eugene. «Analysis of Algorithms: Solutions 3» (PDF). Analysis of Algorithms: Solutions 3. Carnegie Mellon University. Consultado em 9 de julho de 2016

[2] Allain, Alex. «Sorting Algorithms Compared - Cprogramming.com». Sorting Algorithm Comparison. www.cprogramming.com. Consultado em 9 de julho de 2016

[1]

[2]

v d e Algoritmos de ordenação
Teoria	Algoritmo de ordenação \| Pesquisa binária \| Busca linear \| Ordenação (computação) \| Lista \| Lista duplamente ligada
Exchange sorts	Bubble sort \| Cocktail sort \| Odd-even sort \| Comb sort \| Gnome sort \| Quicksort
Selection sorts	Selection sort \| Heapsort \| Smoothsort \| Cartesian tree sort \| Tournament sort
Insertion sorts	Insertion sort \| Shell sort \| Tree sort \| Library sort \| Patience sorting
Merge sorts	Merge sort \| Strand sort \| Timsort
Outros	Topological sorting \| Sorting network \| Bitonic sorter \| Batcher odd-even mergesort \| Pancake sorting
Ordenações ineficientes/humorísticas	Bogosort (ou "Estou com sort") \| Stooge sort