Algoritmos de Ordenamiento Interno
Burbuja
Este es el algoritmo más sencillo probablemente. Ideal para empezar. Consiste en ciclar repetidamente a través de la lista, comparando elementos adyacentes de dos en dos. Si un elemento es mayor que el que está en la siguiente posición se intercambian.
Ventajas:
· Fácil implementación.
· No requiere memoria adicional.
Desventajas:
· Muy lento.
· Realiza numerosas comparaciones.
· Realiza numerosos intercambios.
QuickSort
Esta es probablemente la técnica más rápida conocida. Fue desarrollada por C.A.R. Hoare en 1960. El algoritmo original es recursivo, pero se utilizan versiones iterativas para mejorar su rendimiento (los algoritmos recursivos son en general más lentos que los iterativos, y consumen más recursos).
Ventajas:
· Muy rápido
· No requiere memoria adicional.
Desventajas:
· Implementación un poco más complicada.
· Recursividad (utiliza muchos recursos).
· Mucha diferencia entre el peor y el mejor caso.
Shell
Este método utiliza una segmentación entre los datos. Funciona comparando elementos que estén distantes; la distancia entre comparaciones decrece conforme el algoritmo se ejecuta hasta la última fase, en la cual se comparan los elementos adyacentes, por esta razón se le llama ordenación por disminución de incrementos.
Ventajas:
· No requiere de memoria adicional
· Mejor rendimiento que el método de inserción clásico
Desventajas:
· Implementación algo confusa
· Realiza numerosas comparaciones e intercambios
Métodos de búsqueda
Búsqueda Secuencial
Búsqueda secuencial, también se le conoce como búsqueda lineal. Supongamos una colección de registros organizados como una lista lineal. El algoritmo básico de búsqueda secuencial consiste en empezar al inicio de la lista e ir a través de cada registro hasta encontrar la llave indicada (k), o hasta al final de la lista. Y así poder encontrar el dato requerido.
Mejor caso: Si tenemos mucha suerte, puede ser que la primera posición examinada contenga el elemento que buscamos, en cuyo caso el algoritmo informará que tuvo éxito después de una sola comparación. Por tanto, su complejidad será O (1). {
Peor caso: Sucede cuando encontramos X en la última posición del array. Como se requieren n ejecuciones del bucle mientras, la cantidad de tiempo es proporcional a la longitud del array n, más un cierto tiempo para realizar las condiciones del bucle mientras y para la llamada al método. Por lo tanto, la cantidad de tiempo es de la forma an+ b para ciertas constantes ay b. En notación O, O (an+b) = O (an) = O(n). {
Búsqueda Binaria
La búsqueda binaria es el método, donde si el arreglo o vector está bien ordenado, se reduce sucesivamente la operación eliminando repetidas veces la mitad de la lista restante. El proceso comienza comparando el elemento central del arreglo con el elemento buscado. Si ambos coinciden finaliza la búsqueda. Si no ocurre así, el elemento buscado será mayor o menor en sentido estricto que el elemento central del arreglo.
Caso optimo: La búsqueda binaria requiere sólo una comparación; esto significa que su tiempo de ejecución óptimo no depende de la cantidad de datos: es constante y por tanto proporcional a 1, es decir, O (1). {
Peor caso: En el peor caso sí dependen de N. La búsqueda binaria divide el array, requiriendo sólo un tiempo O (logn).
Búsqueda hashing
En este método se requiere que los elementos estén ordenados. El método consiste en asignar el índice a cada elemento mediante una transformación del elemento, esto se hace mediante una función de conversión llamada función hash. Hay diferentes funciones para transformar el elemento y el número obtenido es el índice del elemento.
Bibliografía:
No hay comentarios:
Publicar un comentario