Algoritmos Ordenamiento y Busqueda

ALGORITMOS DE ORDENAMIENTO
TIPOS DE ALGORITMOS Para poder ordenar una cantidad determinada de numeros almacenadas en un vector o matriz, existen distintos metodos (algoritmos) con distintas caracteristicas y complejidad. Existe desde el metodo mas simple, como el Bubblesort (o Método Burbúja), que son simples iteraciones, hasta el Quicksort (Método Rápido), que al estar optimizado usandorecursion, su tiempo de ejecucion es menor y es más efectivo. METODOS ITERATIVOS Estos metodos son simples de entender y de programar ya que son iterativos, simples ciclos y sentencias que hacen que el vector pueda ser ordenado. Dentro de los Algoritmos iterativos encontramos:
Burbuja, Inserción-Selección y Shellsort METODOS RECURSIVOS Estos metodos son aún mas complejos, requieren de mayor atención yconocimiento para ser entendidos. Son rápidos y efectivos, utilizan generalmente la técnica Divide y vencerás, que consiste en dividir un problema grande en varios pequeños para que sea más fácil resolverlos. Mediante llamadas recursivas a si mismos, es posible que el tiempo de ejecución y de ordenación sea más optimo. Dento de los algoritmos recursivos encontramos:
Mezclas (merge) y Rápido(quick) METODO DE LA BURBUJA Uno de los mas simples es el método burbuja, es tan fácil como comparar todos los elementos de una lista contra todos, si se cumple que uno es mayor o menor a otro, entonces los intercambia de posición. Por ejemeplo, imaginemos que tenemos los siguientes valores:
5 6
1 0 3, lo que haria una burbuja simple, seria comenzar recorriendo los valores de izquierda a derecha,comenzando por el 5. Lo compara con el 6
, con el 1, con el 0 y con el 3, si es mayor o menor (dependiendo si el orden es ascendiente o descendiente) se intercambian de posicion. Luego continua con el siguiente, con el 6
, y lo compara con todos los elementos de la lista, esperando ver si se cumple o no la misma condicion que con el primer elemento. Asi, sucesivamente, hasta el ultimo elementode la lista. Burbuja simple Como lo describimos en el item anterior, la burbuja mas simple de todas es la que compara todos con todos, generando comparaciones extras, por ejemplo, no tiene sentido que se compare con sigo mismo o que se compare con los valores anteriores a el, ya que supuestamente, ya estan ordenados. Burbuja mejorada Una nueva version del metodo de la burbuja seria limitando elnumero de comparaciones, dijimos que era inutil que se compare consigo misma. Si tenemos una lista de 10.000 elementos, entonces son 10.000 comparaciones que estan sobrando. Imaginemos si tenemos 1.000.000 de elementos. El metodo seria mucho mas optimo con “n” comparaciones menos (n = total de elementos). Burbuja optimizada Si al cambio anterior (el de la burbuja mejorada) le sumamos otro cambio, elhecho que los elementos que estan detrás del que se esta comparando, ya estan ordenados, las comparaciones serian aun menos y el metodo seria aun mas efectivo. Si tenemos una lista de 10 elementos y estamos analizando el quinto elemento, que sentido tiene que el quinto se compare con el primero, el segundo o el tercero, si supuestamente, ya estan ordenados? INSERCCION Y SELECCION El bucleprincipal de la ordenacion por insercion va examinando sucesivamente todos los elementos de la matriz desde el segundo hasta el n-ésimo, e inserta cada uno en el lugar adecuado entre sus precedesores dentro de la matriz. La ordenacion por selección funciona seleccionando el menor elemento de la matriz y llevandolo al principio; a continuacion selecciona el siguiente menor y lo pone en la segunda posicionde la matrizm y asi sucesivamente.

ORDENAMIENTO POR MEZCLA Este algoritmo consiste basicamente en dividir en partes iguales la lista de numeros y luego mezclarlos comparandolos, dejandolos ordenados. Si se piensa en este algoritmo recursivamente, podemos imaginar que dividirá la lista hasta tener un elemento en cada lista, luego lo compara con el que está a su lado y según corresponda, lo...