Algoritmos De Ordenamiento

Benchmarking de algoritmos de ordenamientos

Integrantes:

Anibal Jara

Sebastián Döll

Victor Gajardo

Profesor:

Rodrigo Pavez

Introducción

En el presente informe se analizan las pruebas realizadas sobre 7 algoritmos de ordenamiento, los cuales fueron sometidos a test con distinto número y formas de entrada de datos, pudiendo llegar a realizar un esbozo, basado en su funcionamiento y complejidad de cual era más efectivo dependiendo de las situaciones.

Se usó una máquina no estándar para la prueba, los detalles serán expuestos también a lo largo de este informe así como la explicación y posterior conclusión de por qué un algoritmo determinado es más rápido que otro y bajo que circunstancias.

Pruebas con algoritmos de búsqueda

Maquina de pruebas

El computador usado para realizar las pruebas fue un SAMSUNG RV511, sus especificaciones son las siguientes:

• Procesador Intel core I5 a 2,6 Ghz

• 6 GB de memoria RAM

• 3 MB de memoria cache L3

Burbuja:

Este es un algoritmo de búsqueda directo, es decir sólo usa comparaciones para realizar los intercambios. Este algoritmo efectúa el ordenamiento recorriendo la lista y compara si los datos están en el orden correcto, y si no lo están los intercambia, por ello es que necesita recorrer muchas veces la lista hasta que verifique que todos los datos estén ordenados correctamente. Es un algoritmo de relativamente fácil implementación ya que su lógica es simple y directa.

Selección:

Este algoritmo tiene orden O (n²) lo que lo hace ineficiente para listas de muchos datos, y generalmente peor que el ordenamiento de inserción (tercer ordenamiento), presenta algunos beneficios de uso frente al algoritmo de búsqueda de la Burbuja. Este algoritmo trabaja encontrando el menor valor en la lista, y lo ubica en la primera posición, luego sigue de esa posición + 1, buscando el menor, sucesivamente hasta terminar de recorrer los datos y ordenarlos.

Inserción:

Este algoritmo, al igual que selección, tiene orden O (n²), este algoritmo recorre la lista y va ordenando los elementos insertándolos en una sublista ya ordenada. Este algoritmo también es ineficiente para listas largas de muchos datos, aún así, menos que selección, puesto que requiere recorrer la lista hasta el punto que corresponde el dato ordenado.

Burbuja modificada:

El ordenamiento de la burbuja modificada, aunque surge de una mejor del ordenamiento de la burbuja, este efectúa el ordenamiento en 2 direcciones, también llamado burbuja bidireccional, puesto que toma los elementos igual que el ordenamiento burbuja clásico, en búsqueda ascendente y luego desde esa posición – 1 busca en forma descendente la posición correspondiente del dato a ordenar. Este algoritmo sigue siendo al igual que la burbuja de orden O (n²).

Intercambio:

Este ordenamiento, igual que los anteriores es un algoritmo de intercambio directo, de orden O (n²) que requiere recorrer varias veces la lista para ordenar todos los elementos, trabaja buscando los elementos menores de la lista en cada pasada y ubicándolos en el principio.

Quick Sort:

Este es un algoritmo de alta complejidad e implementación más elaborada que los algoritmos vistos anteriormente, puede tener 2 tipos de complejidad dependiendo del pivote que elija para realizar el ordenamiento. El pivote

...