Scribd
Cargar
429 vistas5 páginas

Algoritmo StoogeSort: Definición y Análisis

StoogeSort es un algoritmo recursivo de ordenamiento que realiza tres particiones recursivas para ordenar una lista. Tiene una complejidad de O(n^2.7095) y funciona intercambiando elementos si el final es menor que el comienzo, y luego ordenando recursivamente las dos terceras partes iniciales, las dos terceras partes finales, y nuevamente las dos terceras partes iniciales. Es un algoritmo ineficiente en comparación con otros como MergeSort.

Cargado por

Jhoner Esteban Silva
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PPTX, PDF, TXT o lee en línea desde Scribd
429 vistas5 páginas

Algoritmo StoogeSort: Definición y Análisis

StoogeSort es un algoritmo recursivo de ordenamiento que realiza tres particiones recursivas para ordenar una lista. Tiene una complejidad de O(n^2.7095) y funciona intercambiando elementos si el final es menor que el comienzo, y luego ordenando recursivamente las dos terceras partes iniciales, las dos terceras partes finales, y nuevamente las dos terceras partes iniciales. Es un algoritmo ineficiente en comparación con otros como MergeSort.

Cargado por

Jhoner Esteban Silva
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PPTX, PDF, TXT o lee en línea desde Scribd

StoogeSort

Jhoner Esteban Silva Kelly Katterine Ceballos

StoogeSort es un algoritmo recursivo que realiza una particin 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 ms pequeo que el valor del comienzo, entonces, se intercambian. Si hay dos o ms 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. Adems 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
2 2 2 3

de los
2

elementos totales ( primer 3, ltimo 3, primer 3 ) y el tamao 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 ejecucin es por lo tanto muy lento en comparacin de algoritmos de ordenacin eficaces como MergeSort (Ordenamiento por mezcla), y es incluso mas lento que el ordenamiento de burbuja.

También podría gustarte