1	Tema 10: Ordenamientos Profesor : Rodrigo Salas e-mail : rsalas@inf.utfsm.cl
2	Algoritmos de Ordenamiento Definición: Son algoritmos que fueron realizados para ordenar un conjunto de datos de acuerdo a alguna regla o relación de orden. Los algoritmos varían según su facilidad de entendimiento, su eficiencia, cantidad de código necesario para implementarlos, complejidad, requisitos necesarios de los datos.
3	Algoritmos de Ordenamiento. Existen un gran número de algoritmos de ordenamientos, los cuales pueden ser clasificados en: Internos: El tamaño del conjunto de datos es lo suficientemente pequeño para que sea almacenado en la memoria principal. Externos El tamaño del conjunto de datos es más grande de lo que puede almacenar la memoria principal, por lo cual se requiere el uso de memorias secundarias o adicionales.
4	Algoritmos de ordenamiento Interno Algunos algoritmos de ordenamiento internos son: Simples: Bubble Sort, Insertion Sort, Exchange Sort Complejos: Quick Sort, Heap Sort, Radix Sort
5	Estructura del Dato Algoritmo
6	Ordenamientos Internos Simples
7	Ordenamiento Burbuja El algoritmo consiste en que los elementos más pesados se hundan y los más livianos salgan a flote.
8	Ordenamiento Burbuja
9	Ordenamiento por Inserción En el i-ésimo recorrido de “inserta” el i-ésimo elemento A[i] en el lugar correcto entre A[1],...,A[i-1]
10	Ordenamiento por Inserción
11	Ordenamiento por Selección En el i-ésimo recorrido se selecciona el registro con la clave más pequeña, entre A[i],...,A[n] y se intercambia con A[i]. Como resultado, después de i pasadas, los i registros menores ocuparán A[1],...,A[i] en un cierto orden.
12	Ordenamiento por Selección
13	Ordenamientos Internos Complejos
14	Quicksort El algoritmo básico fue inventado en 1960 por C.A.R. Hoare. Es un método de ordenamiento basado en el paradigma “divide y conquista”. Particiona un conjunto en dos partes, y luego ordena cada partición de manera independiente. Evaluación del algoritmo: En el caso promedio requiere alrededor de N log N operaciones para ordenar N registros. En el peor caso requiere N² operaciones.
15	Quicksort
16	Quicksort La función particion debe reordenar el arreglo de manera tal que se cumpla las siguientes condiciones: El elemento A[i] se encuentra en su último lugar en el arreglo para algún i. Ninguno de los elementos en A[1],...,A[i-1] son mayores que A[i]. Ninguno de los elementos en A[i+1],...,A[r] es menor que A[i].
17	Quicksort
18	Heapsort Evaluación del algoritmo: En el caso promedio y peor caso se requiere alrededor de N log N operaciones para ordenar N registros.
19	Heapsort
20	Heapsort
21	Heapsort