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:
|
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
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(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
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
- 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
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
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