Algoritmos de ordenamiento

Estructura de datos III
TP 1: Algoritmos de ordenamiento

____________________________________________________________

_______ Estructura de datos III Algoritmos de ordenamiento_byPerses.doc Página 1 de 33

Autor: Love4Programming@gmail.com Sede: San Isidro

____________________________________________________________

_______ Estructura de datos III Algoritmos deordenamiento_byPerses.doc Página 2 de 33

Algoritmos de ordenamiento
Resumen
El siguiente trabajo desarrolla el tema de la performance en distintos algoritmos de ordenamiento y presenta una comparativa de cada uno de ellos, como también el órden de complejidad de los mismos. Los algoritmos analizados son: • • • • • • • Bubble sort Selection sort Insertion sort Shell sort Heap sort Merge sort Quick sort

Lasimplementaciones de los algoritmos han sido realizadas en c++.

____________________________________________________________

_______ Estructura de datos III Algoritmos de ordenamiento_byPerses.doc Página 3 de 33

Indice

Introducción.......................................................................................................................................... 4 Análisis de losalgoritmos ................................................................................................................ 5 Bubble sort........................................................................................................................................ 5 Selection sort................................................................................................................................... 6 Insertion sort ................................................................................................................................... 7 Merge sort......................................................................................................................................... 9 Quick sort........................................................................................................................................ 14 Heap Sort ........................................................................................................................................ 16 Shell sort ......................................................................................................................................... 17 Conclusiones....................................................................................................................................... 20 Apéndice ............................................................................................................................................... 21 Apéndice 1 - Código fuente del Trabajo Práctico ............................................................. 21Apendice 2 - Análisis de Algoritmos...................................................................................... 30 Apendice 3 - Referencias........................................................................................................... 33

____________________________________________________________

_______ Estructura de datos III Algoritmos de ordenamiento_byPerses.docPágina 4 de 33

Introducción.
Uno de los problemas fundamentales en la ciencia de la computación es ordenar una lista de items. Existen una infinidad de métodos de ordenamiento, algunos son simples e intuitivos, como el bubble sort, y otros como son extremadamente complicados, pero producen los resultados mucho más rápido. En este trabajo se presentan los algoritmos de ordenamiento más comunes,entre los cuales están los siguientes: Bubble sort, Heap sort, Insertion sort, Merge sort, Quick sort, Selection sort y Shell sort. Los algoritmos de ordenamiento pueden ser divididos en dos clases de acuerdo a la complejidad de los mismos. La complejidad del algoritmo se denota según la notación Big-O. Por ejemplo, O(n) significa que el algoritmo tiene una complejidad lineal. En otras palabras,...