Want to make interactive content? It’s easy in Genially!

Over 30 million people build interactive content in Genially.

Check out what others have designed:

BEYONCÉ

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.