Métodos de Ordenamiento InsertionSort en C++ - Código Fuente

El ordenamiento por inserción (insertion sort en inglés) es una manera muy natural de ordenar para un ser humano, y puede usarse fácilmente para ordenar un mazo de cartas numeradas en forma arbitraria. Requiere O(n²) operaciones para ordenar una lista de n elementos.

Inicialmente se tiene un solo elemento, que obviamente es un conjunto ordenado. Después, cuando hay k elementos ordenados de menor a mayor, se toma el elemento k+1 y se compara con todos los elementos ya ordenados, deteniéndose cuando se encuentra un elemento menor (todos los elementos mayores han sido desplazados una posición a la derecha) o cuando ya no se encuentran elementos (todos los elementos fueron desplazados y este es el más pequeño). En este punto se inserta el elemento k+1 debiendo desplazarse los demás elementos.

Aplicaciones de Insertion Sort

Debido a que el algoritmo es útil sólo para ordenar arreglos pequeños, en la práctica no es muy utilizado como algoritmo central para ordenar un conjunto de datos, sino más bien se usa como complemento de otros tipos de ordenamientos más avanzados.

Por ejemplo, se puede utilizar Insertion Sort para mejorar el uso de Quicksort (uno de lo algoritmos de ordenamiento más usados y el más eficiente para uso general). En este caso, Insertion Sort se puede ocupar para ordenar los sub-arreglos pequeños que van quedando al finalizar la ejecución de Quicksort, optimizando de esta manera dicho algoritmo, ya que Insertion Sort es más eficiente ordenando arreglos de poco tamaño.


Insertion Sort fue también inspiración para la creación de Shell Sort por parte del informático Donald Shell. Shell Sort es una generalización que mejora el algoritmo de Insertion Sort que permite que el elemento a insertar avance varios espacios hacia su posición correcta, en lugar de uno solo como en Insertion Sort, lo cual lo hace más rápido y eficiente.

Métodos de Ordenamiento Insertion Sort en C++ - Código Fuente

DESCARGA | MEGA

LEER MÁS

Métodos de Ordenamiento SelectionSort en C++ - Código Fuente

Descripción

Este algoritmo mejora ligeramente el algoritmo de la burbuja. En el caso de tener que ordenar un vector de enteros, esta mejora no es muy sustancial, pero cuando hay que ordenar un vector de estructuras más complejas, la operación de intercambiar los elementos sería más costosa en este caso. Su funcionamiento se puede definir de forma general como:

• Buscar el mínimo elemento entre una posición i y el final de la lista
• Intercambiar el mínimo con el elemento de la posición i

Análisis del Costo Computacional

El ciclo externo se ejecuta n veces para una lista de n elementos, o sea que para ordenar un vector de n términos, tiene que realizar siempre el mismo número de comparaciones. c(n)= (n2-n)/2 Cada búsqueda requiere comparar todos los elementos no clasificados, de manera que el número de comparaciones c(n) no depende del orden de los términos, si no del número de términos; por lo que este algoritmo presenta un comportamiento constante independiente del orden de los datos. Luego la complejidad es del orden n2.

Estabilidad, Ventajas y Desventajas

Puede que exista algo de discrepancia en cuanto a si es o no estable este algoritmo, pero en realidad esta implementación parece ser bastante estable. Se puede verificar esto ordenando un conjunto de datos que tenga un par de ellos con la misma clave. Se vera claramente que el orden relativo entre ellos es conservado. Algunos autores no lo consideran asi, pero independientemente de esto, este algoritmo tienes entre sus ventajas: Es fácil su implementación. No requiere memoria adicional. Realiza pocos intercambios. Tiene un rendimiento constante, pues existe poca diferencia entre el peor y el mejor caso. Como todos también tiene algunas desventajas: Es lento y poco eficiente cuando se usa en listas grandes o medianas. Realiza numerosas comparaciones.

Métodos de Ordenamiento Selection Sort en C++ - Código Fuente

DESCARGA | MEGA

LEER MÁS

Método de Ordenamiento BubbleSort (Burbuja) en C++ - Código Fuente

Algoritmo de ordenamiento. 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. 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. 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 el más sencillo de implementar.

Aplicación

A pesar de que el ordenamiento de burbuja es uno de los algoritmos más sencillos de implementar, su orden O(n2) lo hace muy ineficiente para usar en listas que tengan más que un número reducido de elementos. Incluso entre los algoritmos de ordenamiento de orden O(n2), otros procedimientos como el ordenamiento por inserción son considerados más eficientes. Dada su simplicidad, el ordenamiento de burbuja es utilizado para introducir el concepto de algoritmo de ordenamiento para estudiantes de ciencias de la computación. A pesar de esto, algunos investigadores como Owen Astrachan han criticado su popularidad en la enseñanza de ciencias de la computación, llegando a recomendar su eliminación de los planes de estudio. Sumado a esto, Jargon File, un libro ampliamente citado en la cultura hacker, lo denomina "el mal algoritmo genérico", y Donald Knuth, uno de los mayores expertos en ciencias de la computación, afirma que el ordenamiento de burbuja "no parece tener nada para recomendar su uso, a excepción de un nombre pegajoso y el hecho de que conlleva a problemas teóricos interesantes". El ordenamiento de burbuja es asintóticamente equivalente, en tiempos de ejecución, con el ordenamiento por inserción en el peor de los casos, pero ambos algoritmos difieren principalmente en la cantidad de intercambios que son necesarios. Resultados experimentales como los descubiertos por Astrachan han demostrado que el ordenamiento por inserción funciona considerablemente mejor incluso con listas aleatorias. Por esta razón, muchos libros de algoritmos modernos evitan usar el ordenamiento de burbuja, reemplazándolo por el ordenamiento por inserción. El ordenamiento de burbuja interactúa vagamente con el hardware de las CPU modernas. Requiere al menos el doble de escrituras que el ordenamiento por inserción, el doble de pérdidas de cache, y asintóticamente más predicción de saltos. Varios experimentos de ordenamiento de cadenas en Java hechos por Astrachan muestran que el ordenamiento de burbuja es 5 veces más lento que el ordenamiento por inserción, y 40% más lento que el ordenamiento por selección.

Método de Ordenamiento BubbleSort (Burbuja) en C++ - Código Fuente

DESCARGA | MEGA

LEER MÁS