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

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

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