algoritmos de ordenamiento y busqueda en C

1

Universidad Catlica del Maule

Departamento de Computacin e informtica

Ingeniera civil informtica

Estructura de datos

Profesor Hugo Araya

Algoritmos de Ordenamiento y

Bsqueda

Alumno: Jonathan Nicols Seplveda Castillo

Fecha entrega: 13 de Mayo 2013

2

Resumen

En esta investigacin se hizo comparaciones de algoritmos de ordenamiento

(Buble Sort, Shell Sort, Quick Sort), con el fin de decidir cul es el ms

conveniente o eficaz, para esto se obtuvieron los tiempos de ejecucin y

cantidades de instrucciones con diferentes tamaos de listas, esto se realiz en

Windows y Linux. Lo mismo se realizo con los algoritmos de bsqueda

(secuencial, binaria, interpolacin).

Los resultados arrojaron que para el ordenamiento de datos lo mejor es ocupar

el Shell Sort, en el caso de la bsqueda de datos es ms conveniente usar el

ordenamiento binario. Ambos algoritmos fueron elegidos por su velocidad y

estabilidad al usar lista de gran tamao sin depender mucho del hardware o del

S.O.

Palabras clave: Buble Sort, Quick Sort, Shell Sort, bsqueda, secuencial, interpolacin, algoritmo.

3

ndice

1. Introduccinpg.5

2. Investigacin y problemtica.pg.6

3. Marco terico: anlisis de algoritmos.pg.7

4. Desarrollo de la parte experimental y recoleccin de

datospg.7

5. Tablas

o 5.1. Algoritmos de ordenamiento:

5.1.1. Buble Sort..pg.8

Tabla 1.1.1 (tiempo)pg.8

Tabla 1.1.2 (instrucciones)..pg.8

5.1.2. Shell Sort...pg.9

Tabla 1.2.1 (tiempo)...........pg.9

Tabla 1.2.2 (instrucciones)..pg.9

5.1.3. Quick Sort...pg.10

Tabla 1.3.1 (tiempo)..Pg.10

Tabla 1.3.2(instrucciones).Pg.10

o 5.2.Algoritmos de Bsqueda:

5.2.1. Bsqueda secuencial...Pg.11

Tabla 2.1.1 (tiempo)..pg.11

Tabla 2.1.2 (instrucciones)pg.12

5.2.2. Bsqueda binaria pg.13

Tabla 2.1.1 (tiempo)..pg.13

Tabla 2.1.2 (instrucciones)pg.14

4

5.2.3. Bsqueda interpolacin. pg.15

Tabla 2.1.1 (tiempo) pg.15

Tabla 2.1.2 (instrucciones)....pg.16

6. Interpretacin de datos obtenidos.pg.17

o 6.1. Algoritmos de ordenamiento:

6.1.1. Buble Sort.. pg.17

Figura 1.1.1.. pg.18

Figura 1.1.2...pg.18

6.1.2. Shell Sort pg.19

Figura 1.2.1.. pg.20


6.1.3. Quick Sort.. pg.21


Figura 1.3.2...... pg.22

o 6.2. Algoritmos de Bsqueda:

6.2.1. Bsqueda secuencial. pg.23

Figura 2.1..pg.24

6.2.2. Bsqueda binaria pg.24

Figura 2.2..pg.25

6.2.3. Bsqueda interpolacin...pg.26

Figura 2.3..pg.27

7. Anlisis de resultados y soluciones...pg.28

o 7.1.Solucin para el ordenamiento de datos....

...pg.28

o 7.2. Solucin para la bsqueda de datos... pg.29

8. Conclusiones pg.30

5

1. Introduccin

Los desarrolladores de software siempre caen en la problemtica de cmo

dejar satisfecho al cliente con su producto final, que mtodos o algoritmos son

los mejores para que el programa tenga un funcionamiento ptimo y adems

haya un buen aprovechamiento de los recursos.

En esta investigacin analizaremos distintos algoritmos para resolver 2

problemas planteados: ordenar una lista de nmeros y encontrar un

nmero en una lista, para esto se harn pruebas implementando los distintos

algoritmos, registrando sus tiempos de ejecucin y nmero de instrucciones

cambiando la cantidad de elementos de la lista o arreglo. Con los resultados

listos se decidir cul es el mejor algoritmo para resolver cada problema.

Este informe estar dividido en una parte experimental, una recoleccin de

resultados o datos, el anlisis de los mismos y una decisin para dar solucin a

cada problema planteado.

6

2. Investigacin y problemtica

Se tiene diferentes algoritmos en investigacin (3 de ordenamiento y 3 de

bsqueda), implementados en el lenguaje de programacin C. Con estos

trabajaremos lo que llamamos el anlisis de algoritmos.

Los algoritmos se sometern a prueba en distintas situaciones (S.O, cantidad

de datos, hardware). Habr comparacin entre estos, se vern la eficacia de

cada uno, el comportamiento en diferentes casos.

En esta investigacin se respondern interrogantes como las siguientes:

Cmo trabaja cada algoritmo? es conveniente tal comportamiento?

Qu factores influyen en su comportamiento?

Qu deficiencias o ventajas tiene cada algoritmo?

Cul es el ms conveniente? Por qu?

Cul es el menos conveniente? Por qu?

Como objetivo tenemos el aprender a analizar, diferenciar. Llegar a tomar la

mejor decisin en como implementar o elegir un algoritmo de forma ms

eficaz, con el mejor uso de recursos, y mejor funcionamiento del producto

final (Software).

7

3. Anlisis de algoritmos

Esta es una herramienta para hacer una evaluacin de un diseo, permite

establecer la calidad de un algoritmo y compararlos con otros que dan

solucin al mismo problema sin siquiera implementarlos. Esto implica asociar

a cada algoritmo una funcin matemtica que mida su eficacia, para ver esto

se utiliza como referencias su estructura y tiempo de ejecucin como variables

principales.

En este caso no utilizaremos esta tcnica, sino que trabajaremos de la forma

exhaustiva implementando cada programa, tomando sus tiempos y nmero de

instrucciones. Igual llegaremos a nuestro objetivo que es: ver que es la mejor

implementacin para resolver cada problema.

4. Desarrollo de la parte experimental y

recoleccin de datos

Para hacer el anlisis se implementaran en lenguaje C los algoritmos Buble

Sort, Shell Sort y Quick Sort (en la parte de algoritmos de

ordenamiento); bsqueda secuencial, bsqueda binaria (en la parte de

algoritmos de bsqueda).

Las variables a buscar sern el tiempo de ejecucin y la cantidad de

instrucciones, que se vern en listas de datos de varios tamaos. En esta

ocasin este experimento se realizara en los sistemas operativos Windows 7 y

Fedora 17 (Linux) en la misma mquina (notebook). El equipo a utilizar tiene

las siguientes especificaciones de hardware que influyen en los resultados:

Procesador Intel Core i3 primera generacin de 2.40 GHz.

RAM de 4 Gb.

Estructura de 64 bit soportada.

Los resultados numricos de la implementacin sern expuestos en las

siguientes pginas en tabla para cada algoritmo:

8

5.1.Algoritmos de ordenamiento:

5.1.1. Buble Sort

Tiempo Algoritmo Buble Sort

S.O : Windows 7 Pro (64bit) S.O: Linux Fedora 17 (64 bit)

N Ordenado Inverso Aleatorio N Ordenado Inverso Aleatorio

1000 0.0 0 0 1000 0 0 0

10000 0.0 0 1 10000 0 0 0

100000 18 36 43 100000 19 36 44

200000 74 148 175 200000 75 144 174

300000 168 325 384 300000 172 346 391

400000 305 587 665 400000 302 564 694

500000 489 916 1038 500000 470 885 1085

600000 - - - 600000 692 1270 1566

700000 - - - 700000 933 1740 2134

800000 - - - 800000 1228 2267 2792

900000 - - - 900000 1556 2888 3552

1000000 - - - 1000000 1914 3568 4392

Algoritmo Buble Sort

Numero de instrucciones

N Ordenado Inverso Aleatorio

1000 500499 2498499 1432851

10000 50004999 249984999 149200267

100000 5000049999 2499984999 15009968375

200000 20000099999 99999699999 59960205271

300000 45000149999 224999549999 135166553935

400000 80000199999 399999399999 240413179583

500000 125000249999 624999249999 375422331883

600000 180000299999 899999099999 540456926855

700000 245000349999 1224998949999 735557933775

800000 320000399999 1599998799999 960337562975

900000 405000449999 2024998649999 1216174836647

1000000 500000499999 2499998499999 1500398181655

5. Tablas

Tabla 1.1.1

Tabla 1.1.2

9

5.1.2. Shell Sort

Tiempo

Algoritmo Shell Sort



1000 0 0 0 1000 0 0 0

10000 0 0 0 10000 0 0 0

100000 0 0 0 100000 0 0 0

200000 0 0 0 200000 0 0 0

300000 0 0 1 300000 0 0 0

400000 0 0 1 400000 0 0 0

500000 1 1 1 500000 0 0 0

600000 - - - 600000 0 0 0

700000 - - - 700000 0 0 0

800000 - - - 800000 0 0 0

900000 - - - 900000 0 0 0

1000000 - - - 1000000 0 0 0

Algoritmo Shell Sort



1000 8033 42493

10000 120044 572558 89543

100000 1500054 7521238 2050577

200000 3200057 15944043 103176363

300000 5100062 23598359 152285011

400000 6800060 33689648 243829801

500000 8500069 49636925 278088731

600000 10800065 49902764 267649769

700000 12600066 60057841 425415889

800000 14400063 70980853 588968753

900000 16200068 77922189 576421845

1000000 18000064 85779790 668385733

Tabla 1.2.1

Tabla 1.2.2

10

5.1.3. Quick Sort

Tiempo

Algoritmo Quick Sort



1000 0 0 0 1000 0 0 0

10000 - - 0 10000 0 0 0

100000 - - 0 100000 - - 0

200000 - - - 200000 - - 0

300000 - - - 300000 - - 0

400000 - - - 400000 - - 0

500000 - - - 500000 - - 0

600000 - - - 600000 - - 0

700000 - - - 700000 - - 0

800000 - - - 800000 - - 1

900000 - - - 900000 - - 1

1000000 - - - 1000000 - - 1

Algoritmo Quick Sort



1000 1099 9990 19915

10000 109990 99990 263202

100000 - - 3241123

200000 - - 6912695

300000 - - 10662310

400000 - - 14609596

500000 - - 18493308

600000 - - 22638567

700000 - - 26618672

800000 - - 31182977

900000 - - 35490639

1000000 - - 39642089

Tabla 1.3.1

Tabla 1.3.2

11

5.2.Algoritmos de bsqueda

5.2.1 Bsqueda secuencial

Tiempo Algoritmo Bsqueda Secuencial

S.O: Linux- Fedora 17 (64 bit)

Opciones a buscar en lista

N 1 numero Ultimo numero Numero del Medio Numero no se encuentra

1000 0 0 0 0

10000 0 0 0 0

100000 0 0 0 0

200000 0 0 0 0

300000 0 0 0 0

400000 0 0 0 0

500000 0 0 0 0

600000 0 0 0 0

700000 0 0 0 0

800000 0 0 0 0

900000 0 0 0 0

1000000 0 0 0 0

S.O: Windows 7 Pro (64 bit)



1000 0 0 0 0

10000 0 0 0 0

100000 0 0 0 0

200000 0 0 0 0

300000 0 0 0 0

400000 0 0 0 0

500000 0 0 0 0

600000 - - - -

700000 - - - -

800000 - - - -

900000 - - - -

1000000 - - - -

Tabla 2.1.1

12

Llamadas Algoritmo Bsqueda Secuencial



1000 1003 1003 1003 1003

10000 10003 10003 10003 10003

100000 100003 100003 100003 100003

200000 200003 200003 200003 200003

300000 300003 300003 300003 300003

400000 400003 400003 400003 400003

500000 500003 500003 500003 500003

600000 600003 600003 600003 600003

700000 700003 700003 700003 700003

800000 800003 800003 800003 800003

900000 900003 900003 900003 900003

1000000 1000003 1000003 1000003 1000003

Tabla 2.1.2

13

5.1.2. Bsqueda binaria

Tiempo Algoritmo Bsqueda Binaria




1000 0 0 0 0

10000 0 0 0 0

100000 0 0 0 0

200000 0 0 0 0

300000 0 0 0 0

400000 0 0 0 0

500000 0 0 0 0

600000 0 0 0 0

700000 0 0 0 0

800000 0 0 0 0

900000 0 0 0 0

1000000 0 0 0 0




1000 0 0 0 0

10000 0 0 0 0

100000 0 0 0 0

200000 0 0 0 0

300000 0 0 0 0

400000 0 0 0 0

500000 0 0 0 0

600000 - - - -

700000 - - - -

800000 - - - -

900000 - - - -

1000000 - - - -

Tabla 2.2.1

14

Llamadas Algoritmo Bsqueda Binaria



1000 33 37 1 36

10000 49 65 1 48

100000 61 69 1 64

200000 65 73 1 68

300000 69 73 1 68

400000 69 73 1 72

500000 69 73 1 72

600000 73 77 1 72

700000 73 77 1 72

800000 73 77 1 76

900000 73 77 1 76

1000000 73 77 1 76

Tabla 2.2.2

15

5.2.3. Bsqueda Interpolacin

Tiempo Algoritmo Bsqueda interpolacin




1000 0 0 0 -

10000 0 0 0 -

100000 0 0 0 -

200000 0 0 0 -

300000 0 0 0 -

400000 0 0 0 -

500000 0 0 0 -

600000 - - - -

700000 - - - -

800000 - - - -

900000 - - - -

1000000 - - - -




1000 0 0 0 -

10000 0 0 0 -

100000 0 0 0 -

200000 0 0 0 -

300000 0 0 0 -

400000 0 0 0 -

500000 0 0 0 -

600000 - - - -

700000 - - - -

800000 - - - -

900000 - - - -

1000000 - - - -

Tabla 2.3.1

16

Llamadas Algoritmo Bsqueda interpolacin



1000 4 4 1497 Error

10000 4 4 14997 Error

100000 4 4 149997 Error

200000 4 4 299997 Error

300000 4 4 449997 Error

400000 4 4 599997 Error

500000 4 4 749997 Error

600000 - - - -

700000 - - - -

800000 - - - -

900000 - - - -

1000000 - - - -

2.3.2

17

6. Interpretacin de datos obtenidos

Lo primero que podemos observar en forma general es la gran diferencia entre

los S.O (esto no es relevante en el objetivo de nuestra investigacin ya que

estamos comparando algoritmos no sistemas, pero no est dems aclarar),

donde Windows no soporta un arreglo mayor a 500.000 elementos a

diferencia de Linux que funciona con 1 milln de datos sin problemas. La otra

observacin general es que al parecer los tiempos de ejecucin son

directamente proporcionales a la cantidad de instrucciones.

A continuacin haremos un anlisis individual de cada de algoritmo:

6.1 Algoritmos de Ordenamiento

6.1.1 Buble Sort

Este podra decirse que es el ms simple de implementar entre los 3

algoritmos ocupados, tiene un funcionamiento simple donde va revisando cada

elemento y lo compara con el elemento anterior, pero esto consume mucho

tiempo en comparar. A continuacin el cdigo del Buble Sort:

Por lo visto en sus tiempos de ejecucin tiene un comportamiento

exponencial, por lo cual su grafica, que se presentar a continuacin, tiene un

18

gran aumento a medida que se aumenta la cantidad de datos. El peor caso para

este algoritmo es la lista aleatoria .

Windows

Linux

-200

0

200

400

600

800

1000

1200

-200000 0 200000 400000 600000 800000 1000000 1200000

Ordenado

Inverso

Aleatorio

-500

0

500

1000

1500

2000

2500

3000

3500

4000

4500

5000

-200000 0 200000 400000 600000 800000 1000000 1200000

Ordenado

Inverso

Aleatorio

Figura 1.1.1

Figura 1.1.2

19

6.1.2 Shell Sort

Este algoritmo trabaja como base con los valores intermedios de la lista. Tiene

como cdigo lo siguiente:

El comportamiento del tiempo de este ordenamiento es casi constante en T=0

segundos, un funcionamiento rpido, solo en Windows hay valores que llegan

a T=1 segundo, pero en Linux se mantiene constante en 0. El peor caso para

este algoritmos es la lista aleatoria.

En la siguiente pgina se exponen los grficos que demuestran esto:

20

Windows

Linux

-0,2

0

0,2

0,4

0,6

0,8

1

1,2

-200000 0 200000 400000 600000 800000 1000000 1200000

Ordenado

Inverso

Aleatorio

0

0,1

0,2

0,3

0,4

0,5

0,6

0,7

0,8

0,9

1

-200000 0 200000 400000 600000 800000 1000000 1200000

Ordenado

Inverso

Aleatorio

Figura 1.2.1

Figura 1.2.2

21

6.1.3 Quick Sort

Este algoritmo tiene la particularidad que ocupa una funcin recursiva para

ordenar la lista. Su cdigo es el siguiente:

El comportamiento, que se puede observa en los datos obtenidos, es lineal y

constante en T=0, funcionamiento rpido.

Eso si este tiene un gran problema, en cierto momento (al aumenta la cantidad

de elementos) el programa no es soportado por el equipo y deja de responde,

esto ocurre tanto en Windows como en Linux. Esto es causado por la cantidad

de llamadas que usa este algoritmo, al ser recursivo, dejando corto de memoria

al equipo. El peor caso es lista aleatoria.

A continuacin los grafico que muestran lo anteriormente dicho:

22

Windows

Linux

0

0,1

0,2

0,3

0,4

0,5

0,6

0,7

0,8

0,9

1

-100000 0 100000 200000 300000 400000 500000 600000

Ordenado

Inverso

Aleatorio

-0,2

0

0,2

0,4

0,6

0,8

1

1,2

-200000 0 200000 400000 600000 800000 1000000 1200000

Ordenado

Inverso

Aleatorio

Figura 1.3.1

Figura 1.3.2

23

6.2 Algoritmos de bsqueda

Aqu analizaremos la cantidad de instrucciones (la cual es la misma para

Windows y Linux) en vez de el tiempo, ya que los algoritmos de bsqueda son

muy rpidos y los valores entregados son solo t=0 segundos, adems solo se

ocupara una lista ordenada ya que la bsqueda binaria solo soporta eso y sera

la nica forma de compararlo con los dems algoritmos.

6.2.1 Bsqueda secuencial

La bsqueda secuencial es simple de entender su funcionamiento, este

simplemente va revisando cada uno de los elementos y cuando encuentra lo

deseado indica en qu posicin esta. Su cdigo es el siguiente:

El comportamiento de este es lineal y va en aumento constante.

Al buscar diferentes nmeros en una lista de mismo tamao el nmero de

instrucciones es el mismo, ya que siempre recorre todos los elementos de la

lista a pesar de ya haber encontrado lo deseado. El nmero de instrucciones

cambia proporcionalmente solo al cambiar el tamao de la lista o arreglo.

A continuacin se expone el grafico de lo anteriormente dicho:

24

Bsqueda Secuencial (numero de instrucciones)

6.2.2 Bsqueda Binaria

Este algoritmo, en forma grafica, tiene un comportamiento un tanto raro

pero efectivo: primero empieza buscando en la posicin media de la lista o

arreglo, despus en se va a los valores que estn antes del dato del centro y

despus a los que estn despus. Su cdigo es el siguiente:

-200000

0

200000

400000

600000

800000

1000000

1200000

-200000 0 200000 400000 600000 800000 1000000 1200000

1 numero

Ultimo numero

Numero del Medio

no encuentra

Figura 2.1

25

Se puede observar que al buscar un elemento que est en el centro de la lista el

nmero de instrucciones es 1. Tambin se puede ver que hay una relacin

entre la cantidad de instrucciones al buscar el primer dato y el ltimo dato,

esto se puede representar con la siguiente frmula:

I primero : es la cantidad de instrucciones del primer elemento de la lista.

I ultimo: es la cantidad de instrucciones del ltimo elemento de la lista.

A continuacin el grafico de lo anterior dicho:

Bsqueda Binaria (numero de instrucciones)

0

10

20

30

40

50

60

70

80

90

-200000 0 200000 400000 600000 800000 1000000 1200000

1 numero

Ultimo numero

Numero del Medio

no encuentra

I primero+ 4 =I ultimo

Figura 2.2

26

6.2.3 Bsqueda interpolacin

El cdigo de este algoritmo es el siguiente:

Lo que se puede observar en este es que el nmero de llamadas en buscar el

primer y ltimo elemento no cambia al cambiar el tamao del arreglo (se

mantiene en # = 4 para ambos caso). Una cosa importante que se puede

rescatar es que para ambos S.O en algoritmo deja de responder despus de los

500 mil elementos, esto le da limitaciones a pesar de funcionar bien con listas

menores a los 500 mil elementos. Adems da error cuando no se encuentra.

El grafico que muestra ser expuesto a continuacin

27

Bsqueda interpolacin (numero de instrucciones)

-100000

0

100000

200000

300000

400000

500000

600000

700000

800000

900000

-500000 0 500000 1000000 1500000

1 numero

Ultimo numero

Numero del Medio

Numero no se encuentra

Figura 2.3

28

7. Anlisis de resultados y soluciones

En lo que son las preguntas planteadas en el inicio de este informe, algunas

como el funcionamiento de los algoritmos han sido respondidas en la seccin

anterior. Para lo dems podemos responder lo siguiente:

7.1. Solucin para el ordenamiento de datos

En lo que tiene que ver con los factores que intervienen en el

funcionamiento, podemos encontrar la cantidad de datos y el ambiente o

sistema (S.O) donde se trabaja.

En el tema del mejor algoritmo, podemos dejar como el ms conveniente

el Shell Sort, porque es rpido y es soportado por los 2 sistemas en su

totalidad. Por qu no el Quick Sort que mas rpido?, la respuesta a esto es

simple ya que al llegar a una determinada cantidad de datos el programa

no es soportado por el equipo, lo que limita su funcionamiento y no

garantiza un buen funcionamiento en cualquier maquina o sistema.

El peor vendra siendo el Buble Sort por el tiempo que ocupa en ordenar

arreglos, especialmente los muy grandes.

29

7.2. Solucin para la bsqueda de datos

Los factores que influyen son los mismos que en el ordenamiento de datos

Podemos dejar como el mejor algoritmo la bsqueda binaria, ya que ocupa

pocas instrucciones en buscar algn elemento y adems soporta sin

problemas un arreglo de 1 milln de elementos. Pero si para listas que no

superan los 500 mil elementos es preferible el algoritmo de bsqueda

interpolacin, especialmente cuando se busca valores de los extremos del

arreglo.

El peor sera la bsqueda secuencial, porque ocupa muchas instrucciones

en buscar algn dato o elemento.

30

8. Conclusiones y sugerencias

Ya con los resultados listos de nuestra investigacin, podemos rescatar

diferentes cosas. En el caso especifico de los algoritmos de ordenamiento, se

observa que el algoritmo Quick Sort tiene un mejor funcionamiento que los

dems, las razones son su velocidad de ordenamiento y su estabilidad al

ordenar listas de gran tamao. En el caso de los algoritmos de bsqueda, el

mejor caso se observa en el algoritmo de bsqueda binaria, tal decisin es

porque necesita pocas instrucciones para cumplir su funcin y se comporta de

forma estable en grandes listas o arreglos.

Tomando un caso ms general los algoritmos son comparados para ver cul es

el ms conveniente por factores como su tiempo de ejecucin, cantidad de

instrucciones y, algo muy importante, su estabilidad en distintas condiciones

como S.O, hardware, etc. Estos estn condicionados por la estructura de tal

cdigo (recursiva, no recursiva, etc.) y forma ocupar las iteraciones (for,

while).

El trabajo practico que se a realizado no se aleja mucho a lo teorico.

Como sugerencia general para optimizar el trabajo hecho es el revisar bien que

valores son ms relevantes de analizar, para ahorrar tiempo. Otra sugerencia

ms conveniente es aplicar el anlisis de algoritmos para poder decidir sin ni

siquiera implementar los diferentes algoritmos.

Documents

algoritmos de ordenamiento y busqueda en C