Jla computadoras

Estructuras de Datos y Algoritmos
Algoritmos de ordenamiento

Contenido
§ Algoritmos de ordenamiento
– Algoritmos simples: inserción, selección e inserció selecció intercambio – Algoritmo deShell – Algoritmos HeapSort MergeSort – Algoritmo QuickSort – Algoritmos de ordenamiento externo

1

Contenido
§ En este capítulo se discutirá el problema de capí discutirá ordenar un arreglo deelementos. § La mayoría de los algoritmos asumen que los mayorí datos pueden almacenarse en su totalidad en la memoria principal. Al final se discutirá discutirá ordenamiento externo. § Paraordenamiento interno se verá que: verá
– Existen varios algoritmos simples de O(N2). – Algunos algoritmos más complicados cuyo peor caso es má O(N2) pueden alcanzar en promedio O(N log N). – Un algoritmo deordenamiento de proposito general requiere Ω(N log N) comparaciones.

Ordenamiento Interno
Considérese un arreglo numérico de 5 elementos A1, A2, A3, A4, A5. Escriba un programa que ordene los valoresen el arreglo de menor a mayor.

2

Clasificación de algoritmos de ordenamiento interno
§ Su solución probablemente pertenece a uno solució de los siguientes tipos:
– Un ordenamiento porinserción. inserció – Un ordenamiento por intercambio. – Un ordenamiento por selección. selecció – Un ordenamiento por enumeración. enumeració – Un algoritmo especializado. – Una actitud perezosa. – Unatécnica novedosa súper eficiente. té sú

Ordenamiento por inserción
Original 81 94 11 96 12 35 19 95 Pase 1 81 94 11 96 12 35 19 95 Pase 2 11 81 94 96 12 35 19 95 Pase 3 11 81 94 96 12 35 19 95 Pase 411 12 81 94 96 35 19 95 Pase 5 11 12 35 81 94 96 19 95 Pase 6 11 12 19 35 81 94 96 95 Pase 7 11 12 19 35 81 94 95 96
Movimientos y comparaciones

0,1 2,2 0,3 3,4 3,5 4,6 1,7 13,28

3Ordenamiento por inserción
§ Se realiza en N-1 pases. § Para el pase p = 1 hasta N-1 se ordenan los elementos en las posiciones 0 hasta p. § Al inicio de cada pase, los elementos en las posiciones 0...