Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 60 vistas

    TareaP07 KevinFúnez 31311897

    Cargado por

    Yair Fúnez
    Quicksort y heapsort son algoritmos de ordenamiento comúnmente usados. Quicksort es más rápido en promedio que heapsort, pero heapsort tiene un tiempo de ejecución garantizado de O(n log n) y no requiere memoria adicional. Aunque quicksort tiene un caso peor, pequeñas mejoras en la selección del pivote pueden evitarlo. Quicksort intercambia menos elementos que heapsort, especialmente si los datos ya están parcialmente ordenados.

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd

    TareaP07 KevinFúnez 31311897

    Cargado por

    Yair Fúnez
    60 vistas3 páginas
    Quicksort y heapsort son algoritmos de ordenamiento comúnmente usados. Quicksort es más rápido en promedio que heapsort, pero heapsort tiene un tiempo de ejecución garantizado de O(n log n) y no requiere memoria adicional. Aunque quicksort tiene un caso peor, pequeñas mejoras en la selección del pivote pueden evitarlo. Quicksort intercambia menos elementos que heapsort, especialmente si los datos ya están parcialmente ordenados.

    Descripción original:

    .

    Título original

    TareaP07_KevinFúnez_31311897

    Derechos de autor

    © © All Rights Reserved

    Formatos disponibles

    PDF, TXT o lea en línea desde Scribd

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    Quicksort y heapsort son algoritmos de ordenamiento comúnmente usados. Quicksort es más rápido en promedio que heapsort, pero heapsort tiene un tiempo de ejecución garantizado de O(n log n) y no requiere memoria adicional. Aunque quicksort tiene un caso peor, pequeñas mejoras en la selección del pivote pueden evitarlo. Quicksort intercambia menos elementos que heapsort, especialmente si los datos ya están parcialmente ordenados.

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    60 vistas3 páginas

    TareaP07 KevinFúnez 31311897

    Cargado por

    Yair Fúnez
    Quicksort y heapsort son algoritmos de ordenamiento comúnmente usados. Quicksort es más rápido en promedio que heapsort, pero heapsort tiene un tiempo de ejecución garantizado de O(n log n) y no requiere memoria adicional. Aunque quicksort tiene un caso peor, pequeñas mejoras en la selección del pivote pueden evitarlo. Quicksort intercambia menos elementos que heapsort, especialmente si los datos ya están parcialmente ordenados.

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    Está en la página 1de 3

    Clase:

    Estructura de Datos I

    Alumno:

    Kevin Yair Fúnez Ordoñez

    Ingeniero:

    Carlos Alberto Vigil Verde

    Tarea:

    Tarea Practica 07

    Cuenta:

    31311897

    Sección:

    1056
    ACTIVIDAD 01

    1. ¿Cuál es la diferencia entre quicksort y heapsort?


    Heapsort está garantizado por O (N log N), lo que es mucho mejor que el peor de los
    casos en Quicksort. Heapsort no necesita más memoria para que otra matriz coloque
    datos ordenados como lo necesita Mergesort.
    Quicksort tiene algo realmente especial. Se ejecuta rápido, mucho más rápido que los
    algoritmos Heapsort.
    El secreto de Quicksort es: casi no realiza intercambios de elementos innecesarios. El
    intercambio lleva mucho tiempo.
    Con Heapsort, incluso si todos sus datos ya están ordenados, intercambiará el 100% de
    los elementos para ordenar la matriz.

    2. ¿Cuál es la importancia de los métodos quicksort y heapsort?


    Debido a que las estructuras de datos son utilizadas para almacenar información, para
    poder recuperar esa información de manera eficiente es deseable que aquella esté
    ordenada.

    3. Para la realización de ordenamientos, ¿Cuál método usaría y por qué?


    Usaría Quicksort ya que no intercambia lo que ya está ordenado. Si sus datos están
    completamente ordenados, ¡no intercambia casi nada! Aunque hay mucho alboroto
    sobre el peor de los casos, una pequeña mejora en la elección del pivote, que no sea
    obtener el primer o el último elemento de la matriz, puede evitarlo. Si obtiene un pivote
    del elemento intermedio entre el primero, el último y el medio, es suficiente para evitar
    el peor de los casos.
    Lo que es superior en Quicksort no es el peor de los casos, ¡sino el mejor de los casos!
    En el mejor de los casos, haces la misma cantidad de comparaciones, está bien, pero no
    cambias casi nada. En el caso medio, intercambia parte de los elementos, pero no todos
    los elementos, como en Heapsort y Mergesort. Eso es lo que le da a Quicksort el mejor
    momento. Menos intercambio, más velocidad.
    EJERCICIO 01
    Aplique Quicksort y Heapsort (paso a paso) para ordenar el siguiente conjunto de
    datos.
    S = {25, 15, 20, 3, 5, 10}
    Quicksort
    25 15 20 3 5 10
    Pivote
    <10 >=10

    3 5 10 25 15 20
    Pivote Pivote
    <=5 <20 >=20

    3 5 10 15 20 25

    Ordenado queda: [3, 5, 10, 15, 20, 25]

    Heapsort

    1 25 2 20 3 15

    15 20 15 10 5 10

    3 5 10 3 5 25 3 20 25

    4 10 5 5 6
    3
    5 3
    10 5 10
    3
    15 20 25 15 20 25 25
    15 20

    Ordenado queda: [3, 5, 10, 15, 20, 25]

    También podría gustarte