📑 Table of Contents▼
Stooge sort

ClasseAlgoritmo de ordenação
Estrutura de dadosArray
Complexidade pior casoO(n2.709...) ou O(nlog3 / log1.5)
Complexidade de espaços pior casoO(n)

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(nlog 3 / log 1.5) = O(n2.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

editar

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

editar 
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

editar 
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(nc), 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(nlog3/2 (3)) ≈ O(n2.70).

Comparação com outros algoritmos

editar

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(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[2]

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

Características

editar
  • 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(n2.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

editar

VisualG

editar 
// 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

editar 
#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++

editar 
#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#

editar 
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

editar 
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

editar 
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

editar 
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

editar 
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

editar 
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

editar 
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

editar 
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

editar 
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

editar 
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

editar 
%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

editar 
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

editar 
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

editar 
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

editar

Ligações externas

editar

Ver também

editar

Métodos de pesquisa

editar

Galeria

editar
  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 

📚 Artikel Terkait di Wikipedia

Insertion sort

Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0262032937. Section 2.1: Insertion sort, pp. 15–21. Michael T Goodrich, Algorithm Desing:

Quicksort

Ordenação de vetor Merge sort Heapsort Selection sort Bubble sort Busca linear Rápida aula de quicksort Sorting algorithms/Quicksort - Implementação

Bubble sort

array_to_sort_len { for j in i + 1..array_to_sort_len { if compare(array_to_sort[i], array_to_sort[j]) { array_to_sort[i], array_to_sort[j] = array_to_sort[j]

Lista de algoritmos

classificada. Shell sort: uma tentativa de otimização do insertion sort. Smoothsort: É um variação do Heap sort. Stupid sort. Topological sort. Codificação aritmética:

Heapsort

Algorithms. Introduction to Design and Analysis (em inglês) 2ª ed. Reading, Massachusetts: Addison-Wesley. 71 páginas. ISBN 0-201-06035-3  HeapSort [1]

Heap sort adaptativo

O heap sort adaptativo é um algoritmo de ordenação que é semelhante ao heap sort, mas usa um árvore de busca binária aleatória para a estrutura da entrada

Timsort

Timsort é um algoritmo de ordenação híbrido derivado do merge sort e do insertion sort, projetado para ter boa performance em vários tipos de dados do

Ordenação adaptativa

caso que se comportam otimamente no pior caso, notavelmente o heap sort e o merge sort, não têm a ordem existente dentro de sua entrada em conta, apesar