Ordenamientos y B squedas

Ordenamientos y Búsquedas
¿Qué es ordenamiento? 
Es la operación de arreglar los registros de una tabla en algún orden secuencial de acuerdo a un criterio de ordenamiento. 
El ordenamiento se efectúa con base en el valor de algún campo en un registro. 
El propósito principal de un ordenamiento es el de facilitar las búsquedas de los miembros del conjunto ordenado. 
¿Cuándo conviene usarun método de ordenamiento? 
Cuando se requiere hacer una cantidad considerable de búsquedas y es importante el factor tiempo. 
Tipos de ordenamientos: 
Los internos: Son aquellos en los que los valores a ordenar están en memoria principal, por lo que se asume que el tiempo que se requiere para acceder cualquier elemento sea el mismo (a[1], a[500], etc). 
Los externos: Son aquellos en los que los valo resaordenar están en memoria secundaria (disco, cinta, cilindro magnético, etc), por lo que se asume que el tiempo que se requiere para acceder a cualquier elemento depende de la última posición accesada (posición 1, posición 500, etc).
Clasificación de ordenación:
Ascendente.- cuando se tiene de menor a mayor los elementos de la lista, ya sea alfabéticamente o numéricamente.
Descendente.- cuando setiene de mayor a menor los elementos de la lista.
ALGORITMOS DE ORDENAMIENTO Burbuja
Llamado también de intercambio directo o bubble sort.
Es uno de los más conocidos
Más sencillo.
Más fácil de implementar.
Idea Básica:
Comparar elementos consecutivos en cada paso a lo largo del arreglo.
Cada vez que se realiza una comparación, los elementos se intercambian entre sí en caso de no estar en orden.Se le llama de burbuja, porque en la ordenación los elementos más ligeros suben en la lista.
Se pasa varias veces a través del arreglo en forma secuencial.
Cada paso consiste en la comparación de cada elemento con su sucesor, y el intercambio de los dos elementos si no están en el orden correcto.




Análisis de eficiencia
Hay n-1 comparaciones y pasos en este método. Por lo que el número totalde comparaciones es O(n).El número de intercambios depende del orden original del archivo.
La única característica redentora de este ordenamiento, es que requiere de poco espacio adicional para guardar el valor temporal para el intercambio y de algunas variables enteras simples. Que es O(n) en el caso de un arreglo ordenado en su totalidad o casi desordenado en su totalidad.ALGORITMOS DE ORDENAMIENTO Selección

La idea básica de esta ordenación es :

Encontrar el elemento menor (o mayor) de la lista y colocarlo en la primera posición, a continuación, el elemento siguiente menor (o mayor) se lleva a la segunda posición y así sucesivamente hasta que queda ordenado. Cualquier ordenamiento pos selección puede conceptualizarse como un algoritmo que usa una cola de prioridaddescendente.

Análisis de eficiencia
En el primer paso se efectúan n-1 comparaciones, en el segundo n-2 comparaciones y así sucesivamente. O sea que es del orden de O (n2).El número de intercambios es siempre n-1.
Solo se requiere un poco de memoria adicional, para guardar unas variables temporales.

El ordenamiento puede ser categorizado como más rápido que el de burbuja. No hay mejora si elarreglo esta ordenado o desordenado. A pesar de ser fácil de codificar, es improbable que se use este método, solamente cuando son arreglos pequeños.



















ALGORITMOS DE ORDENAMIENTO Rápido o QuickSort

Se le llama de Intercambio por partición.
Se define como un proceso recursivo.
Se basa en la técnica «divide y vencerás»
Se basa en el método de burbuja

Idea Básica
Se escoge un elementoa la mitad de la lista, llamado pivote.
Se tienen los elementos <= a la izquierda del pivote.
Se tienen los elementos >= a la derecha del pivote.

Análisis de eficiencia
Tiene aparente propiedad de trabajar mejor para elementos desordenados completamente, que para elementos semiordenados.
En promedio para todos los elementos, el método hace O (nlogn) comparaciones, el cual indica que es...