Algoritmo de ordenamiento rápido
samay ileis
Created on March 23, 2024
Over 30 million people build interactive content in Genially.
Check out what others have designed:
BEYONCÉ
Horizontal infographics
DEMOCRATIC CANDIDATES NOV DEBATE
Horizontal infographics
ONE MINUTE ON THE INTERNET
Horizontal infographics
SITTING BULL
Horizontal infographics
RUGBY WORLD CUP 2019
Horizontal infographics
GRETA THUNBERG
Horizontal infographics
FIRE FIGHTER
Horizontal infographics
Transcript
Algoritmo de ordenamiento rápido
Grupo 6
Quicksort
Presiona para conocer más
Concepto y objetivos
Presiona para conocer más
Funciones del algoritmo
Presiona para conocer más
Método de implementación
Ejemplo de situación de aplicación
Presiona para conocer más
Elección del pivote: Aunque no es una función en sí misma, la elección del pivote (elemento de referencia) es crucial. Dependiendo de la implementación esta puede ser una función independiente o integrada. Y, las estrategias empleadas pueden influir significativamente en rendimiento del algoritmo.
Función principal
Funciones específicas
Función de partición: Una vez seleccionado el pivote, se reorganiza la lista de manera que los elementos menores o iguales a él queden a su izquierda, y los mayores a su derecha.
Función de ordenamiento: Una vez separado en dos partes, se aplican recursivamente las funciones anteriores hasta que la lista queda completamente ordenada de manera ascente o descendente
Dividir el problema principal en pequeños subproblemas, ordenándolos de manera que sean sencillos de resolver, y a su vez, combina los resultados para obtener la solución final completa y ordenada.
- Algoritmo Ordenar
- Función Quicksort
- Variables i, j, pivote: Estas variables son usadas para controlar los índices y el valor del pivote.
- Pivote: Es el valor medio entre el primer y último elemento del segmento de la lista que estamos ordenando. Este valor es usado como referencia para dividir la lista en dos partes.
- Bucles Mientras: Estos bucles se utilizan para mover los elementos menores que el pivote a la izquierda y los mayores a la derecha.
- Intercambio: Si i es menor o igual a j, se intercambian los elementos en las posiciones i y j.
- Recursión: La función se llama a sí misma para ordenar las dos nuevas listas resultantes después de usar el pivote.
Explicación:
Esta función es una implementación del algoritmo de ordenamiento rápido Quicksort.
Este algoritmo utiliza la función quicksort para ordenar un arreglo de números aleatorios.
- Variables i, j, pivote: Estas variables son usadas para controlar los índices y el valor del pivote.
- Pivote: Es el valor medio entre el primer y último elemento del segmento de la lista que estamos ordenando. Este valor es usado como referencia para dividir la lista en dos partes.
- Bucles Mientras: Estos bucles se utilizan para mover los elementos menores que el pivote a la izquierda y los mayores a la derecha.
- Intercambio: Si i es menor o igual a j, se intercambian los elementos en las posiciones i y j.
- Recursión: La función se llama a sí misma para ordenar las dos nuevas listas resultantes después de usar el pivote.
- Generación de Números Aleatorios: Se crea un arreglo números de 10 elementos y se llena con números aleatorios del 1 al 100.
- Impresión de Números Desordenados: Se imprime el arreglo antes de ordenarlo.
- Llamada a Quicksort: Se ordena el arreglo con la función quicksort.
- Impresión de Números Ordenados: Se imprime el arreglo después de ordenarlo.
Para su implementación, el programador debe de decidir: 1-Cúal será el pivote o número de referencia. 2-Partir y reordenar los elementos de la lista. 3-Aplicar el mismo proceso de forma recursiva. 4-terminar el proceso.
Metodos de implementación
Partir y reordenar los datos de modo que a la izquierda del pivote queden los números menores que el pivote y a su derecha los números mayores al pivote. En caso de tener números iguales al pivote, pueden ir junto a este a su izquierda o derecha.
Se utiliza recursividad para así repetir el proceso y ordenar los valores en orden creciente tanto a la izquierda como derecha del pivote
El algoritmo termina cuando los subconjuntos a ambos lados del pivote se encuentran ya ordenados. De esta manera se da punto final al código.
La escogencia del pivote es el pilar del inicio del algoritmo, dado que a partir de este es donde se toma la referencia para distribuir el resto de los datos.
Eficiencia: : El Quicksort busca ordenar una lista de elementos minimizando el tiempo de ejecución y el número de comparaciones necesarias para lograr la ordenación.
Este algoritmo, también llamado "Quicksort" fue desarrollado por Tony Hoare en 1960, es muy utilizado debido a su rapidez en la mayoría de los casos. Es un método eficiente para ordenar elementos que utiliza la técnica de dividir y conquistar, seleccionando un pivote para dividir la lista en subconjuntos y ordenarlos recursivamente.
Concepto
Objetivos
Optimización de recursos: Busca minimizar el uso de memoria adicional durante el proceso de ordenamiento. Ideal para trabajar con grandes conjuntos de datos.
Versatilidad: El algoritmo de ordenamiento rápido busca ser aplicable a una amplia gama de tipos de datos y situaciones.
Robustez: El algoritmo debe funcionar correctamente y producir resultados precisos para todo tipo de listas de entrada.