los Algoritmos de ordenación son formas de organizar una matriz de elementos de Menor a mayor. Estos algoritmos se pueden usar para organizar datos desordenados y facilitar su uso. Además, tener una comprensión de estos algoritmos y cómo funcionan es fundamental para una sólida comprensión de la informática que se está volviendo cada vez más crítica en un mundo de paquetes prefabricados. Este blog se centra en la velocidad, usos, ventajas y desventajas de Algoritmos de Ordenación específicos.,
aunque hay una amplia variedad de Algoritmos de Ordenación, este blog explica la inserción recta, la ordenación de Shell, La ordenación de burbuja, la ordenación rápida, La ordenación de selección y la ordenación de montón. Los dos primeros algoritmos (Straight Insertion y Shell Sort) ordenan matrices con inserción, que es cuando los elementos se insertan en el lugar correcto. Los siguientes 2 (Bubble Sort y Quick Sort) ordenan matrices con Intercambio que es cuando los elementos se mueven alrededor de la matriz. El último es heap sort que ordena a través de la selección donde se seleccionan los elementos correctos mientras el algoritmo corre por la matriz.,
Notación Big-O
antes de que este blog vaya más allá, es esencial explicar los métodos que utilizan los profesionales para analizar y evaluar la complejidad y el rendimiento del algoritmo. El estándar actual se llama «Notación Big O» nombrada de acuerdo a su notación que es una «O» seguida de una función como «O(n).»
definición Formal
Big O se usa para denotar la complejidad temporal de un algoritmo o cuánto espacio ocupa. Este blog se centra principalmente en la parte de complejidad temporal de esta notación., La forma en que la gente puede calcular esto es identificando el peor caso para el algoritmo objetivo y formulando una función de su rendimiento dada una cantidad n de elementos. Por ejemplo, si hubiera un algoritmo que buscara el número 2 en una matriz, entonces el peor caso sería si el 2 estuviera al final de la matriz. Por lo tanto, la notación o grande sería O(n) ya que tendría que correr a través de toda la matriz de n elementos antes de encontrar el número 2.
para ayudarlo, encuentre a continuación una tabla con algoritmos y su complejidad.,
Straight Insertion Sort
Straight insertion sort es uno de los Algoritmos de clasificación más básicos que esencialmente inserta un elemento en la posición correcta de una lista ya ordenada. Por lo general se añade al final de un nuevo array y se mueve hacia abajo hasta que encuentra un elemento más pequeño gracias a sí mismo (la posición deseada). El proceso se repite para todos los elementos de la matriz sin clasificar. Considere la matriz {3,1,2,5,4}, comenzamos en 3, y como no hay otros elementos en la matriz ordenada, la matriz ordenada se convierte en solo {3}., Después, insertamos 1 que es más pequeño que 3, por lo que se movería delante de 3 haciendo la matriz {1,3}. Este mismo proceso se repite en la línea hasta obtener el array {1,2,3,4,5}.
Las ventajas de este proceso son que es muy sencillo y fácil de implementar. Además, es relativamente rápido cuando hay pequeñas cantidades de elementos para ordenar. También puede convertirse en inserción binaria, que es cuando se compara a distancias más largas y se reduce al lugar correcto en lugar de comparar con cada elemento antes del lugar correcto., Sin embargo, una ordenación de inserción recta suele ser lenta cuando la lista se vuelve grande.
Características principales:
- Familia de ordenación por inserción
- directo y simple
- Worst case = o(n^2)
implementación de Python:
Shell Sort
Shell sort es un tipo de ordenación por inserción que primero ordena parcialmente sus datos y luego ordenar ejecutando un algoritmo de ordenación por inserción en toda la matriz. Generalmente comienza eligiendo pequeños subconjuntos de la matriz y ordenando esas matrices., Después, repite el mismo proceso con subconjuntos más grandes hasta que alcanza un punto donde el subconjunto es la matriz, y todo se ordena. La ventaja de hacer esto es que tener la matriz casi totalmente ordenada ayuda a que la clasificación de inserción final logre o esté cerca de su escenario más eficiente.
Además, el aumento del tamaño de los subconjuntos se logra a través de un término de incremento decreciente. El término incremento esencialmente elige cada elemento kth para poner en el subconjunto., Comienza grande, lo que lleva a grupos más pequeños (más dispersos), y se vuelve más pequeño hasta que se convierte en 1 (todo el array).
La principal ventaja de este algoritmo de ordenación es que es más eficiente que una de ordenación por inserción. Además, hay una variedad de algoritmos diferentes que buscan optimizar la ordenación del shell cambiando la forma en que disminuye el incremento, ya que la única restricción es que el último término en la secuencia de incrementos es 1. El más popular es generalmente el método de Knuth que utiliza la fórmula h = ((3^k) -1) / 2 que nos da una secuencia de intervalos de 1 (k=1), 4 (k=2), 13 (k=3), y así sucesivamente., Por otro lado, shell sort no es tan eficiente como otros algoritmos de ordenación como quicksort y merge sort.
Características principales:
- Ordenar por inserción
- puede optimizar el algoritmo cambiando incrementos
- Usando el método de Knuth, el peor caso es O(n^(3/2))
implementación de Python:
Bubble Sort
Bubble sort compara los elementos adyacentes de una matriz y organiza esos elementos. Su nombre proviene del hecho de que los grandes números tienden a «flotar» (burbuja) hasta la parte superior., Hace un bucle a través de una matriz y ve si el número en una posición es mayor que el número en la siguiente posición, lo que daría lugar a que el número se mueva hacia arriba. Este ciclo se repite hasta que el algoritmo ha pasado por la matriz sin tener que cambiar el orden. Este método es ventajoso porque es simple y funciona muy bien para listas en su mayoría ordenadas. Como resultado, los programadores pueden implementar rápida y fácilmente este algoritmo de clasificación. Sin embargo, la compensación es que este es uno de los Algoritmos de ordenación más lentos.,
Características principales: Exchange sortingEasy to implementWorst Case = o (n^2)
implementación de Python:
Quicksort
Quicksort es uno de los Algoritmos de ordenación más eficientes, y esto lo convierte en uno de los más utilizados también.Lo primero que debe hacer es seleccionar un número de pivote, este número separará los datos, a su izquierda están los números más pequeños que él y los números más grandes a la derecha. Con esto, tenemos toda la secuencia dividida.,Después de particionar los datos, podemos asegurar que las particiones están orientadas, sabemos que tenemos valores más grandes a la derecha y valores más pequeños a la izquierda.El quicksort utiliza este algoritmo divide y vencerás con recursión. Por lo tanto, ahora que tenemos los datos divididos usamos recursión para llamar al mismo método y pasar la mitad izquierda de los datos, y después de la mitad derecha para seguir separando y ordenando los datos. Al final de la ejecución, tendremos todos los datos ordenados.,
Características principales:
- De La Familia de Algoritmos de Ordenación de intercambio
- Divide y conquista paradigma
- complejidad del peor caso O(n2)
implementación de Python:
Heapsort
heapsort es un algoritmo de ordenación basado en la estructura de un montón. El montón es una estructura de datos especializada que se encuentra en un árbol vector.In la primera etapa del algoritmo, se crea un árbol con los valores a ordenar, comenzando por la izquierda, creamos el nodo raíz, con el primer valor., Ahora creamos un nodo secundario izquierdo e insertamos el siguiente valor, en este momento evaluamos si el valor establecido en el nodo secundario es mayor que el valor en el nodo raíz, si es así, cambiamos los valores. Hacemos esto a todo el árbol. La idea inicial es que los nodos padre siempre tienen valores más grandes que los nodos hijos.
al final del primer paso, creamos un vector comenzando con el valor raíz y caminando de izquierda a derecha llenando el vector.,
Ahora comenzamos a comparar los valores de los nodos padre e hijo buscando el valor más grande entre ellos, y cuando lo encontramos, cambiamos los lugares reordenando los valores. En el primer paso, comparamos el nodo raíz con la última hoja del árbol. Si el nodo raíz es más grande, entonces cambiamos los valores y continuamos repitiendo el proceso hasta que la última hoja sea el valor más grande. Cuando no hay más valores que reorganizar, agregamos la última hoja al vector y reiniciamos el proceso. Podemos ver esto en la imagen de abajo.,
Las principales características del algoritmo son:
- De la familia de ordenación por selección
- Comparaciones en el peor caso = O(n log n)
- No es estable
implementación de Python:
Referencia: ¿Cómo de rápido se están?
después del desarrollo de los algoritmos es bueno para nosotros probar lo rápido que pueden ser. En esta parte desarrollamos un programa simple usando el código anterior para generar un punto de referencia básico, solo para ver cuánto tiempo pueden usar para ordenar una lista de enteros.,Observaciones importantes sobre el código:
- El límite de llamada recursiva predeterminado de Python es 1,000, en esta prueba estamos utilizando números grandes, por lo que necesitamos mejorar ese número para ejecutar el benchmark sin errores. El límite se fijó en 10.000.
- este código solo mide el tiempo de ejecución de cada algoritmo.
- se hicieron 20 pruebas con diferentes tamaños de listas que van desde 2500 hasta 50000.
- Los números se generaron aleatoriamente variando de 1 a 10000.,Los resultados son los siguientes:los Algoritmos de Ordenación de Shell y ordenación de montón funcionaron bien a pesar de la longitud de las listas, en el otro lado encontramos que los Algoritmos de ordenación de inserción y ordenación de burbujas fueron mucho peores, aumentando en gran medida el tiempo de computación. Vea los resultados en la tabla de abajo.
conclusión
en este post, mostramos 5 de los Algoritmos de clasificación más comunes utilizados hoy en día. Antes de usar cualquiera de ellos es extremadamente importante saber qué tan rápido se ejecuta y cuánto espacio se va a utilizar. Así que es el equilibrio entre complejidad, velocidad y volumen., Otra característica crítica de los Algoritmos de ordenación que es importante conocer es su estabilidad. La estabilidad significa que el algoritmo mantiene el orden de los elementos con valores de clave iguales. El mejor algoritmo cambia para cada conjunto diferente de datos y, como resultado, comprender nuestros datos juega un papel importante en el proceso de elegir el algoritmo correcto.
Como podemos ver, entender nuestros datos juega un papel muy importante en el proceso de elegir el algoritmo correcto.,
si este post te llamó la atención, echa un vistazo al video a continuación, te dará una explicación concisa sobre 15 algoritmos de clasificación.
la Notación Big O – https://en.wikipedia.org/wiki/Big_O_notation
Knuth, Donald Ervin, 1938 – el arte de La programación de computadoras / Donald Ervin Knuth. xiv, 782 p. 24 cm.,d=»a5b60f8536″>
Quicksort – https://commons.wikimedia.org/wiki/File:Quicksort.gif
Quicksort – http://interactivepython.org/courselib/static/pythonds/SortSearch/TheQuickSort.html
Heapsort Algorithm – https://en.wikipedia.org/wiki/Heapsort
Heapsort Algorithm – https://www.geeksforgeeks.org/heap-sort/
Bubble sort – http://interactivepython.org/runestone/static/pythonds/SortSearch/TheBubbleSort.html
Sedgewick, R.,, & Wayne, K. (2011). Algorithms, 4th Edition. (p. I–XII, 1-955). Addison-Wesley. – https://algs4.cs.princeton.edu/20sorting/
Sorting algorithms – https://brilliant.org/wiki/sorting-algorithms/
