Stooge Sort

O Stooge Sort, ou ordenação "fantoche", é 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), que comparado a outros algoritmos de ordenação muito conhecidos como o Insertion Sort e o Bubble Sort, ele chega a ser um pouco mais lento, devido sua ineficiência não recomenenda-se o uso para a ordenação de grandes volumes de dados.

Stooge Sort
classe	Algoritmo de ordenação
estrutura de dados	Arrays e Listas
complexidade pior caso	O(n2.7) ou O(nlog3 / log1.5)
complexidade de espaços pior caso	O(n)
Algoritmos

Passos

A execução do algoritmo é dada nas seguintes instruções:

1. Se o elemento da esquerda for maior do que o da direita, trocam-se os dois.
2. Se houver uma quantidade de elementos maior ou igual a 3 no array:
   1. Realizar a chamada recursiva para os 2/3 iniciais do array.
   2. Realizar a chamada recursiva para os 2/3 finais do array.
   3. Realizar a chamada recursiva para os 2/3 iniciais do array.
3. Retornar o array.

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

Ao analisarmos o algoritmo através do pseudocódigo acima, tiramos que a sua relação de recorrência pode ser escrita da seguinte forma:

T(n) = 3 * T([(2/3) * n]) + C.

E através desta relação, podemos calcular a complexidade do algoritmo.

Calculo de Complexidade

Dada a relação de recorrência, usaremos o Método Mestre para o calculo da complexidade do algoritmo.

∴ F(n) = 1; a = 3; b = 3/2

∴ F(n) = 1 < n ^{log3/2 (3)}

Portanto, T(n) = O(n ^{log3/2 (3)}) ≈ O(n^2.7).

Implementações

Código em 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);
        }
    }
}

Código em 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ódigo em Python

def stooge_sort(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

Código em 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);
	}
}

Código em 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);
    }
};

Referências

• Cormen, Thomas H. «Introduction to Algorithms». Dictionary of Algorithms and Data Structures. ISBN 0-262-03293-7. Consultado em 8 de julho de 2016 
• «Stooge sort». Stooge sort. Consultado em 8 de julho de 2016 
• «Sorting algorithms/Stooge sort». Consultado em 8 de julho de 2016