Primeros pasos en programación con Python

Algoritmos de ordenamiento, ejemplos y eficiencia

¿Qué es un algoritmo de ordenamiento?

En computación y matemáticas un algoritmo de ordenamiento es un algoritmo que pone elementos de una lista o un vector en una secuencia dada por una relación de orden, es decir, el resultado de salida ha de ser una permutación —o reordenamiento— de la entrada que satisfaga la relación de orden dada. Las relaciones de orden más usadas son el orden numérico y el orden lexicográfico. Ordenamientos eficientes son importantes para optimizar el uso de otros algoritmos (como los de búsqueda y fusión) que requieren listas ordenadas para una ejecución rápida. También es útil para poner datos en forma canónica y para generar resultados legibles por humanos (Wikipedia).

Desde los comienzos de la computación, el problema del ordenamiento ha atraído gran cantidad de investigación, tal vez debido a la complejidad de resolverlo eficientemente a pesar de su planteamiento simple y familiar. Por ejemplo, BubbleSort fue analizado desde 1956.

Los algoritmos de ordenamiento son comunes en las clases introductorias a la computación, donde la abundancia de algoritmos para el problema proporciona una gentil introducción a la variedad de conceptos núcleo de los algoritmos, como notación de O mayúsculaalgoritmos divide y vencerásestructuras de datos, análisis de los casos peor, mejor, y promedio, y límites inferiores. (Wikipedia)

Bubblesort u ordenamiento burbuja, uno de los ordenamientos más simples que hay.

La Ordenación de burbuja (Bubble Sort en inglés) es un sencillo algoritmo de ordenamiento. Funciona revisando cada elemento de la lista que va a ser ordenada con el siguiente, intercambiándolos de posición si están en el orden equivocado. Es necesario revisar varias veces toda la lista hasta que no se necesiten más intercambios, lo cual significa que la lista está ordenada. (Wikipedia)

También es conocido como el método del intercambio directo. Dado que solo usa comparaciones para operar elementos, se lo considera un algoritmo de comparación, siendo uno de los más sencillos de implementar.

A continuación una animación sobre cómo se ordena, comenzando del elemento con índice cero de un arreglo, es decir, de la izquierda. Como es posible observar va cambiando los elementos comparados hacia la derecha cuando en la comparación se le identifica como mayor, esto se repite en lo sucesivo hasta que al comparar ya no encuentre más elementos mayores, repitiendo el paso hasta terminar.

Comparación: Quicksort vs. Mergesort (recuperado de hackernoon.com)

Se incluyen en este artículo dos algoritmos de ordenamiento adicionales, sobre los cuáles no se incluye descripción en texto, pues se trata de algortimos más avanzados, aunque se incluye de manera ilustrada cómo funcionan y una breve descripción de en qué consisten.

El ordenamiento rápido (quicksort en inglés) es un algoritmo de ordenación eficiente creado por el científico británico en computación C. A. R. Hoare en 1959, todavía es muy usado en la actualidad, pues en promedio es más dos o tres veces más rápido que su principal competidor, el método de ordeniamiento merge sort, una de sus ventajas competitivas es que sus subarreglos se ordenan mediante recursividad y en el mismo arreglo lo que requiere una menor cantidad de memoria.

Por otro lado, el algoritmo de ordenamiento por mezcla (merge sort en inglés) es un algoritmo de ordenamiento externo estable, al igual que quicksort está basado en la técnica divide y vencerás. Es de complejidad O(n log n).

¿Cuanto algoritmos de ordenamiento existen?

Existen cientos sino es que miles, inclusive estudiantes de tecnología lo suelen desarrollar sus propios algoritmos en sus clases de análisis de algoritmos.

Se presenta a continuación una comparativa con notación asíntotica de diferentes algoritmos de ordenamiento frente a la complejidad, son algunos de los más populares.

Se presenta los casos mejores, promedio y peor para la complejidad temporal, siendo el escenario peor cuando el algoritmo de ordenamiento demora mucho y el mejor cuando no demora en ordenar datos.

Igualmente, se incluye el tema de la complejidad espacial, la última columna, que se refiere a cuántos arreglos, ciclos y por tanto uso de memoria es preciso para lograr la finalidad de una de sus operaciones de ordenamiento.

Información recuperada el 25 de mayo de 2020 de:

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *