Comparacion Busqueda Lineal vs Busqueda Binaria C

Facultad de Ingeniería

Tarea Evaluada

Rendimiento de Algoritmos

Daniel Castro Contardo
Programacion básica y algoritmos II
Ing. En Mecatrónica
2013465603

Introduccion
Con este trabajo, se pretende realizar un estudio de los diferentes comportamientos que
tienen específicamente dos algoritmos de búsqueda y un algoritmo de ordenamiento, el cual
se probarán bajo distintascondiciones de números de datos, así como también de tamaños
de números, además de distintos S.O. con la finalidad de encontrar una relación entre
rendimiento y tamaño de los mismos, además de evaluar que programa puede funcionar
mejor ante una eventual necesitad de rapidez con recursos limitados.
Los programas fueron probados en los equipos que se detallan a continuación:
PC1: Intel ® Celeron ® CPUB840 @ 1.90 GHz
4.00 GB RAM
Windows 7 Professional x64
PC2: AMD A6-4400M APU with Radeon™ HD Graphics 2.70 GHz
4.00 GB RAM
Windows 8.1 x64
Todas las pruebas fueron realizadas suponiendo el peor de los casos ingresando la búsqueda
“0” el cual no estaba en ninguno de los rangos ingresados por random
Para efectos de tiempo, se utilizó la función clock_t para los programas de búsqueda binariay el ejercicio práctico, el cual se contó el tiempo en realizar el ordenamiento de datos para
posteriormente restarlo al tiempo total ofrecido en ventana por el programa codeblocks,
obteniendo así una buena aproximación del tiempo que demoro en buscar el objetivo, para
la búsqueda lineal se minimizo al máximo las operaciones por el usuario y por el programa
llegando de igual forma a unaaproximación del tiempo que finalmente demoro en buscar.

Desarrollo
En la diapositiva numero 3 la respuesta es por valor, ya que indica que el numero
posicionado en tempCadaHora[3] es el que actúa en la función.
Para pasar por referencia, se debe escribir de la siguiente manera: (tempCadaHora, 3);
Bubble Sort como función (anexo 1)
Cocktail Sort: El ordenamiento de burbuja bidireccional(cocktail sort en inglés) es un
algoritmo de ordenamiento que surge como una mejora del algoritmo ordenamiento de
burbuja.
La manera de trabajar de este algoritmo es ir ordenando al mismo tiempo por los dos
extremos del vector. De manera que tras la primera iteración, tanto el menor como el mayor
elemento estarán en sus posiciones finales. De esta manera se reduce el número de
comparaciones aunquela complejidad del algoritmo sigue siendo O (n²).
Quick Sort: es actualmente el más eficiente y veloz de los métodos de ordenación interna.
Es también conocido con el nombre del método rápido y de ordenamiento por partición, en
el mundo de habla hispana. Este método es una mejora sustancial del método de
intercambio directo y recibe el nombre de Quick Sort por la velocidad con que ordena loselementos del arreglo. Su autor C.A. Hoare lo bautizó así. La idea central de este algoritmo
consiste en lo siguiente:





Se toma un elemento x de una posición cualquiera del arreglo.
Se trata de ubicar a x en la posición correcta del arreglo, de tal forma que
todos los elementos que se encuentran a su izquierda sean menores o
iguales a x y todos los elementos que se encuentren asu derecha sean
mayores o iguales a x.
Se repiten los pasos anteriores pero ahora para los conjuntos de datos que se
encuentran a la izquierda y a la derecha de la posición correcta de x en el
arreglo.

MergeSort: es un algoritmo de ordenamiento basado en la estrategia "divide y vencerás".
Su orden asintótico es O(n log n), mucho más eficiente que otros algoritmos de
ordenamiento comoburbuja, inserción o selección que son de orden cuadrático,
básicamente MergeSort actúa de esta manera:





Si la longitud del vector es 1 significa que ya está ordenado y no hace nada.
Sino, divide en vector por la mitad en dos subvectores.
Ordena cada subvector de forma recursiva.
Finalmente mezcla los subvectores ya ordenados uniéndolos en un solo vector
ordenado.

Bubble Sort...