presentación ordenacion quichsort
TRANSCRIPT
![Page 1: PresentacióN Ordenacion Quichsort](https://reader036.vdocumento.com/reader036/viewer/2022082811/558984f9d8b42a4f748b466e/html5/thumbnails/1.jpg)
Quicksort
![Page 2: PresentacióN Ordenacion Quichsort](https://reader036.vdocumento.com/reader036/viewer/2022082811/558984f9d8b42a4f748b466e/html5/thumbnails/2.jpg)
Definición:
Algoritmo basado en la técnica de divide y vencerás, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n. Esta es la técnica de ordenamiento más rápida conocida. Fue desarrollada por C. Anthony R. Hoare en 1960.
![Page 3: PresentacióN Ordenacion Quichsort](https://reader036.vdocumento.com/reader036/viewer/2022082811/558984f9d8b42a4f748b466e/html5/thumbnails/3.jpg)
Procedimiento1. Elegir un elemento de la lista de elementos a ordenar, al que llamaremos pivote.
Elemento del arreglo
Pivote
2323 1616 44151588 42421616
![Page 4: PresentacióN Ordenacion Quichsort](https://reader036.vdocumento.com/reader036/viewer/2022082811/558984f9d8b42a4f748b466e/html5/thumbnails/4.jpg)
2.Resituar los demás elementos de la lista a cada lado del pivote, de manera que a un lado queden todos los menores que él, y al otro los mayores. En este momento, el pivote ocupa exactamente el lugar que le corresponderá en la lista ordenada.
Elemento del arreglo
Pivote
424215152323 88 1616 44 2323161644 1515 88 4242
![Page 5: PresentacióN Ordenacion Quichsort](https://reader036.vdocumento.com/reader036/viewer/2022082811/558984f9d8b42a4f748b466e/html5/thumbnails/5.jpg)
3.Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados
Elemento del arreglo
Pivote
88 1616151544 4242 2323
Elemento bien acomodado
88 1616151544
88 1616151544 42422323
1515 4242
151588 4242 232342422323 4242
![Page 6: PresentacióN Ordenacion Quichsort](https://reader036.vdocumento.com/reader036/viewer/2022082811/558984f9d8b42a4f748b466e/html5/thumbnails/6.jpg)
Eficiencia del algoritmo
• En el caso mejor, el pivote termina en el centro del array, dividiéndola en dos subarrays de igual tamaño. En este caso, el orden de complejidad del algoritmo es O(n•log(n)). • En el caso peor, el pivote termina en un extremo del array. El orden de complejidad del algoritmo es entonces de 0(n²). El peor caso dependerá de la implementación del algoritmo, aunque habitualmente ocurre en arrays que se encuentran ordenados, o casi ordenados. • En el caso medio, el orden es O(n•log(n)). No es extraño, pues, que la mayoría de optimizaciones que se aplican al algoritmo se centren en la elección del pivote.
![Page 7: PresentacióN Ordenacion Quichsort](https://reader036.vdocumento.com/reader036/viewer/2022082811/558984f9d8b42a4f748b466e/html5/thumbnails/7.jpg)
Ventajas Y DesventajasVentajas Muy rápido No requiere memoria adicional.
Desventajas Implementación un poco más complicada. Recursividad. Mucha diferencia entre el peor y el mejor caso.
![Page 8: PresentacióN Ordenacion Quichsort](https://reader036.vdocumento.com/reader036/viewer/2022082811/558984f9d8b42a4f748b466e/html5/thumbnails/8.jpg)
Pseudocodigo
![Page 9: PresentacióN Ordenacion Quichsort](https://reader036.vdocumento.com/reader036/viewer/2022082811/558984f9d8b42a4f748b466e/html5/thumbnails/9.jpg)
Demostración
![Page 10: PresentacióN Ordenacion Quichsort](https://reader036.vdocumento.com/reader036/viewer/2022082811/558984f9d8b42a4f748b466e/html5/thumbnails/10.jpg)
Gracias por su Atención