Si nos detenemos a pensar un momento, día a día el ser humano recurre a mantener un orden especifico para ciertas actividades y datos, usualmente las aulas en la universidad están enumeradas ascendentemente, los padrones electorales están ordenados alfabéticamente, el número de cedula de cada uno de nosotros asciende conforme aumenta el numero de nacimientos. Usualmente vemos orden en esto y demás y no cuestionamos las razones, sin embargo, la principal es que se logran hacer búsquedas de manera optima en la que se pueden tomar ciertas características para acortar el tiempo de búsqueda de un dato o una persona. Por ello también es necesario en los sistemas computacionales, en este caso específico, los que poseen estructuras de datos dinámicas como las listas, ordenar los datos según lo amerite la situación, esto quiere decir que puede variar el orden por el factor de relevancia de cierto atributo y el orden también puede ser ascendente, decentemente entre otros.
Ordenación
Es una operación consistente en disponer un conjunto —estructura— de datos en algún determinado orden con respecto a uno de los campos de los elementos del conjunto. Por ejemplo, cada elemento del conjunto de datos de una guía telefónica tiene un campo nombre, un campo dirección y un campo número de teléfono; la guía telefónica está dispuesta en orden alfabético de nombres. Los elementos numéricos se pueden ordenar en orden creciente o decreciente de acuerdo con el valor numérico del elemento.
Ordenar una lista de elementos en orden ascendente o descendente puede ayudarle a un ser humano o a una computadora a encontrar elementos rápidamente en esa lista, tal vez al usar un algoritmo como una búsqueda binaria.
(Joyanes, s.f.) ha mencionado en su libro que Los métodos (algoritmos) de ordenación son numerosos, por ello se debe prestar especial atención en su elección. ¿Cómo se sabe cuál es el mejor algoritmo? La eficiencia es el factor que mide la calidad y rendimiento de un algoritmo. En el caso de la operación de ordenación, dos criterios se suelen seguir a la hora de decidir qué algoritmo —de entre los que resuelven la ordenación— es el más eficiente: el mejor criterio para medir la eficiencia de un algoritmo es aislar una operación específica clave en la ordenación y contar el número de veces que se realiza.
Para este artículo se hará estudio de los algoritmos directos como burbuja, selección e inserción.
Algoritmo de inserción
EcuRed (s.f.-d) ha mencionado en un estudio que supóngase que se desea ordenar los siguientes claves del arreglo (A) utilizando el método de inserción directa el cual consiste en insertar un elemento del arreglo en la parte izquierda del mismo que ya se encuentra ordenada. Este proceso se repite desde el segundo hasta el n-esimo elemento.
Si tratáramos de ordenar un mazo de cartas en un determinado orden, itera sobre las posiciones en el arreglo, comenzando con el índice 1. Cada nueva posición es como la nueva carta que tomas del mazo, y necesitas insertarla en el sitio correcto en el sub-arreglo ordenado a la izquierda de esa posición.
Algoritmo por burbuja
(Joyanes, s.f.) ha mencionado en su libro que el método de ordenación por burbuja es el más conocido y popular entre estudiantes y aprendices de programación, por su facilidad de comprender y programar; por el contrario, es el menos eficiente y por ello, normalmente, se aprende su técnica, pero no suele utilizarse.
EcuRed (s.f.-d) ha mencionado en un estudio que 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. Este algoritmo obtiene su nombre de la forma con la que suben por la lista los elementos durante los intercambios, como si fueran pequeñas burbujas.
Algoritmo por selección
EcuRed (s.f.-d) ha mencionado en un estudio que consiste en encontrar el menor de todos los elementos del arreglo o vector e intercambiarlo con el que está en la primera posición. Luego el segundo más pequeño, y así sucesivamente hasta ordenarlo todo. Su implementación requiere O(n2) comparaciones e intercambios para ordenar una secuencia de elementos.
(Joyanes, s.f.) ha mencionado en su libro que el análisis del algoritmo, con el fin de determinar la función tiempo de ejecución t(n), es sencillo y claro, ya que requiere un número fijo de comparaciones que sólo dependen del tamaño del array y no de la distribución inicial de los datos. El término dominante del algoritmo es el bucle externo que anida a un bucle interno.
Referencias Bibliográficas
Imágenes para este trabajo:
- Zetta, J. Z. C. M.S. (s.f.). 5.9. El ordenamiento por inserción — Solución de problemas con algoritmos y estructuras de datos. Recuperado 23 mayo, 2019, de http://interactivepython.org/runestone/static/pythoned/SortSearch/ElOrdenamientoPorInsercion.html
- Bolívar, J. M. B. (s.f.). Redes Productivas: Dependencia Frente a Subordinación | Óptima Infinito | Efectividad centrada en las personas. Recuperado 24 mayo, 2019, de https://www.optimainfinito.com/2014/05/redes-productivas-dependencia-frente-a-subordinacion.html
Información:
- (s.f.-b). Algoritmo de ordenamiento por selección - EcuRed. Recuperado 23 mayo, 2019, de https://www.ecured.cu/Algoritmo_de_ordenamiento_por_selecci%C3%B3n
- (s.f.-c). Ordenamiento por Inserción - EcuRed. Recuperado 25 mayo, 2019, de https://www.ecured.cu/Ordenamiento_por_Inserci%C3%B3n
- (s.f.-d). Ordenamiento de burbuja - EcuRed. Recuperado 24 mayo, 2019, de https://www.ecured.cu/Ordenamiento_de_burbuja
- Joyanes Aguilar, L., Sánchez García, L., & Zahonero Martínez, I. (2007). Estructura de datos en C++. McGraw-Hill.