3

Es bien sabido que QUICKSORT es de lo mejor en cuanto algoritmos de ordenación. Mi duda es ¿No seria más eficiente leer de una pasada una lista, DESORDENADA, de enteros e ir formado un árbol binario? luego bastaría con leer el árbol en pre-orden y tendríamos la lista ordenada.

¿Esto no sería más rápido que Quicksort?

3
  • ¿Eres consciente que al construir el árbol binario también debes hacer comparaciones? Posiblemente más comparaciones que haciendo una ordenación. el 2 sep. 2019 a las 12:53
  • @PaperBirdMaster Suponiendo que sea un arbol binario de búsqueda, creo que se hacen exactamente las mismas comparaciones, aunque en diferente orden.
    – David DPG
    el 2 sep. 2019 a las 12:56
  • David DPG vuelve a dar en el clavo !!!! y van dos !!!! Graciasssssss
    – Cholo
    el 2 sep. 2019 a las 19:56

1 respuesta 1

3

NO

De hecho, hacer quicksort es imitar el comportamiento de un árbol binario, sin crear una estructura adicional.

Cuando eliges un pivote en quicksort, es análogo a haber definido un nodo en tu árbol. Subsecuentes valores insertados en el árbol (que formarán nuevos nodos) son iguales a fijar un pivote en tu lista por cada vez que ejecutas quicksort.

1
  • Gracias. Tiene mucho sentido lo que dices, Mayores a la derecha, Menores a la izquierda, y vuelta a empezar "imita" muy bien el arbol binario (sin necesidad de crear la estructura.) Bien visto !!!!
    – Cholo
    el 2 sep. 2019 a las 12:35

Tu Respuesta

Al pulsar en “Publica tu respuesta”, muestras tu consentimiento a nuestros términos de servicio, política de privacidad y política de cookies

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.