Download - Comparativa entre Algoritmos de Ordenamiento
Algoritmos de OrdenamientoComparativa
Alumno : Víctor Hugo Orellana Jaque"Análisis de Algoritmos Sección 112"Profesora : Sra. Pilar Pardo Hidalgo"
5-junio-2014"
Burbuja Burbuja Bidireccional
Quicksort Heapsort Shellsort Inserción
Descripción Se basa en el principio de comparar pares de elementos adyacentes e intercambiarlos entre sí hasta que estén todos ordenados.
La manera de trabajar de este algoritmo es ir ordenando al mismo <empo por los dos extremos del vector. Hacemos un recorrido ascendente (del primer elemento al úl<mo), cogemos el primer elemento y lo comparamos con el siguiente, si el siguiente es menor lo pasamos al puesto anterior, de esta forma al final de la lista nos queda el mayor. Se conoce también como “cocktail s
Funciona según el principio de divide y vencerás. Se divide la lista de elementos en dos sublistas, basado en un elemento pivote. Todos los elementos de la primera sublista se acomodan para ser menores que el pivote (mismo caso con los mayores). El mismo proceso de par<ción y organización se realiza repe<damente, hasta que se ordena la lista completa de elementos.
Basaso en comparaciones de elementos que u<liza un heap para ordenarlos. Almacena todos los elementos del vector a ordenar en un monPculo y luego extrae el nodo que queda como raíz en sucesivas iteraciones obteniendo el conjunto ordenado. La cima siempre contendra el mayor o el menor elemento del monPculo
Ordena la estructura de una manera similar a la de burbuja, pero no ordena entre los elementos adyacentes, sino que segmenta los datos. La segmentación puede ser de cualquier tamaño de acuerdo a una secuencia de valores que empiezan con un valor grande y van disminuyendo hasta llegar al “1”.
Construye una lista ordenada en el interior del array a ordenar. Hace comparaciones, así que para que realice su trabajo de ordenación son imprescindibles dos cosas: un array o estructura similar de elementos comparables y un criterio claro de comparación, tal que dados dos elementos nos diga si están en orden o no. Se realizan varias pasadas sobre el array. En cada pasada se analiza un elemento, y se intenta encontrar su orden rela<vo entre los analizados en pasadas anteriores.
Mejor Caso n n n log n n log n n n
Caso Promedio n2
n2
n log n n log n
n log2 n o n3/2
n2
Peor Caso n2
n2
n2 n log n
n log2 n n2
Burbuja Burbuja Bidireccional
Quicksort Heapsort Shellsort Inserción
Ventajas • Fácil implementación
• No requiere memoria adicional
• Fácil implementación (un poco mayor de dificultad que burbuja)
• Demora menos de lo que demora burbuja
• No requiere memoria adicional
• Muy rápido • No
requiere memoria adicional
• El método funciona mejor con datos desordenados.
• No u<liza memoria adicional
• Su desempeño en promedio es como Quicksort pero se comporta mejor que éste en peor caso.
• Muy simple, <empo de ejecución aceptable
• Muy rápido • No requiere
memoria adicional
• Fácil Implementación
• Requerimientos mínimos de memoria
Desventajas • Muy lento • Realiza
muchas comparaciones
• Realiza muchos intercambios
• Muy lento • Realiza muchas
comparaciones • Realiza muchos
intercambios
• Implementación un poco complicada
• Recursividad (muchos recursos)
• Mucha diferencia entre el mejor y el peor caso
• No es estable, se comporta de manera ineficaz con datos del mismo valor
• Método complejo
• Diacil de calcular su complejidad, depende de la secuencia de incrementos que use
• No es estable porque puede perder el orden rela<vo con facilidad
• Lento • Realiza
muchas comparaciones
F I N
Gracias por su atención"