StoogeSortJhoner Esteban Silva

Kelly Katterine Ceballos

StoogeSort es un algoritmo recursivo que realiza una partición en tres llamadas recursivas para llevar a cabo el ordenamiento.

Fue propuesto por los profesores Howard, Fine, Besser *.

Posee un orden de complejidad de O( nlog 3 / log 1.5 ) O( n2.7095.. ).

Si el valor del final es más pequeño que el valor del comienzo, entonces, se intercambian. Si hay dos o más elementos en la lista actual, entonces:

Ordena los dos tercios iniciales de la lista.

Ordena los dos tercios finales de la lista.

Ordena los dos tercios iniciales de la lista nuevamente.

* El algoritmo obtiene su nombre de las rutinas de “The Three Stooges” (Los Tres Chiflados) en la que cada chiflado (stooge) golpea a los otros dos. Además los apellidos nombrados anteriormente son iguales a los de los actores interpretes.

StogeSort es un algoritmo de dividir y conquistar. El caso general para el algoritmo tiene el siguiente principio base:

“El arreglo se clasifica en pedazos de de los elementos totales ( primer , último , primer ) y el tamaño del arreglo que es calificado se trae abajo a dos elementos recursivamente”

El algoritmo StoogeSort es ineficiente, cambia los elementos de la parte superior e inferior si es necesario, luego recursivamente ordena las dos terceras partes inferiores, las dos terceras partes superiores, y nuevamente las dos terceras partes inferiores.

El tiempo de ejecución es por lo tanto muy lento en comparación de algoritmos de ordenación eficaces como MergeSort (Ordenamiento por mezcla), y es incluso mas lento que el ordenamiento de burbuja.

Gracias