Tipos de algoritmos

Algoritmo de Selección

El método de ordenamiento por selección consiste en encontrar el menor de todos los elementos del arreglo e intercambiarlo con el que está en la primera posición y así excluirlo de la lista. Luego el segundo mas pequeño, y así sucesivamente hasta ordenar todo el arreglo.
Es un algoritmo lento, a pesar que sólo realiza un intercambio en cada ejecución del ciclo externo,puede ser una buena elección para listas con registros grandes y claves pequeñas.
Tiempo de Ejecución: El ciclo externo se ejecuta n veces para una lista de n elementos. Cada búsqueda requiere comparar todos los elementos no clasificados. Luego la complejidad es O(n2). Este algoritmo presenta un comportamiento constante independiente del orden de los datos.

Estabilidad: Puede que haya algo dediscrepancia pero esta implementación parece ser estable, puede verificar esto ordenando un conjunto de datos que tenga un par de ellos con la misma clave, el orden relativo entre ellos es conservado, pero algunos autores dicen que no es estable

Ventajas:
• Fácil implementación.
• No requiere memoria adicional.
• Realiza pocos intercambios.
• Rendimiento constante: pocadiferencia entre el peor y el mejor caso.

Desventajas:
• Lento.
• Realiza numerosas comparaciones.

Algoritmo Burbuja

Bubble Sort recorre el arreglo intercambiando los elementos adyacentes que estén desordenados. Recorre el arreglo tantas veces hasta que ya no haya cambios. Prácticamente lo que hace es tomar el elemento mayor y lo coloca en las últimas posiciones o tomar el menor ycolocarlo en las primeras posiciones.

Tiempo de ejecución: El ciclo interno se ejecuta n veces. El ciclo externo también se ejecuta n veces, la complejidad es n * n = O(n2). El comportamiento del caso promedio depende del orden de entrada de los datos, pero es sólo un poco mejor que el del peor caso, y sigue siendo O(n2).

Estabilidad: No intercambia registros con claves iguales.

Ventajas:• Fácil implementación.
• No requiere memoria adicional.

Desventajas:
• Muy lento.
• Muchas comparaciones.
• Muchos intercambios.

Algoritmo de Merge

El algoritmo Merge divide el arreglo original en dos arreglos y los coloca en arreglos separados. Cada arreglo es recursivamente ordenado y finalmente se unen los arreglos en un arreglo ordenado. Como cualquiera delos algoritmos de ordenamiento recursivo el algoritmo Merge tiene complejidad de O(n log n). Fue desarrollado por John Von Neumann.

Tiempo de Ejecución: El proceso del Merge es fusionar mitades de arreglos ordenados dentro de un arreglo. Sin embargo, estas mitades de arreglos tienen que ser ordenadas primero, por lo que se requiere de fusionar mitades de arreglos ya ordenados de estas mitades.Este proceso de partición de arreglos en dos mitades termina cuando el arreglo tiene por lo menos dos elementos.

Estabilidad: Este algoritmo es efectivo para grandes cantidades de datos los cuales están almacenados en arreglos. Se basa en lo siguiente:

La fusión de dos listas ordenadas.
Si se comienza con una colección pequeña de listas ordenadas, entonces se pueden fusionar repetidas veceslas listas pequeñas hasta que al final se fusionen en una lista ordenada final.
Cualquier lista de datos puede ser dividida en pequeñas piezas(con uno o más elementos por pieza), donde cada pieza es ordenada.

Ventajas:
• Mucho más rápido que el heap sort para grandes cantidades de datos

Desventajas:
• Uso de más memoria (varios arreglos), recursivo.
• Complejo

Algoritmo deInserción

Este método toma cada elemento del arreglo para ser ordenado y lo compara con los que se encuentran en posiciones anteriores a la de él dentro del arreglo. Si resulta que el elemento con el que se está comparando es mayor que el elemento a ordenar, se recorre hacia la siguiente posición superior. Si por el contrario, resulta que el elemento con el que se está comparando es menor que...