Programación: búsquedas y ordenamientos

Busquedas yOrdenamientos

AngelVazquez-Patino

Busqueda

Utilidad

Busqueda secuencial

Busqueda binaria

Eficiencia

Ordenamiento

Utilidad

Clasificacion

Algoritmo de burbuja

Algoritmo de seleccion

Algoritmo de insercion

Eficiencia

Burbuja

Seleccion

Insercion

Fuentes

Busquedas y Ordenamientos

Docentes de Programacion

Editado por Angel [email protected]

Departamento de Ciencias de la ComputacionUniversidad de Cuenca

4 de julio de 2016

1 / 53

mailto:[email protected]


AngelVazquez-Patino

Busqueda

Utilidad

Busqueda secuencial

Busqueda binaria

Eficiencia

Ordenamiento

Utilidad

Clasificacion




Eficiencia

Burbuja

Seleccion

Insercion

Fuentes

Objetivos

1. Entender los algoritmos de busqueda

2. Entender los algoritmos de ordenamiento

3. Conocer el concepto de eficiencia

4. Tener una idea intuitiva de la eficiencia de losalgoritmos estudiados

2 / 53


AngelVazquez-Patino

Busqueda

Utilidad

Busqueda secuencial

Busqueda binaria

Eficiencia

Ordenamiento

Utilidad

Clasificacion




Eficiencia

Burbuja

Seleccion

Insercion

Fuentes

ContenidoAlgoritmos de busqueda

UtilidadBusqueda secuencialBusqueda binariaEficiencia

Algoritmos de ordenamientoUtilidadClasificacionAlgoritmo de ordenamiento de burbujaAlgoritmo de seleccionAlgoritmo de insercionEficiencia

Ordenamiento de burbujaAlgoritmo de seleccionAlgoritmo de insercion

Fuentes3 / 53


AngelVazquez-Patino

Busqueda

Utilidad

Busqueda secuencial

Busqueda binaria

Eficiencia

Ordenamiento

Utilidad

Clasificacion




Eficiencia

Burbuja

Seleccion

Insercion

Fuentes

Utilidad I

I Uno de los usos mas frecuentes de los computadoreses la busqueda de informacion en estructuras dedatos. La eficiencia de la busqueda depende de si laestructura esta o no ordenada. E.g., diccionario

I Tome un diccionario y busque la palabra mundo.Para encontrarla, ira directamente a la seccion depalabras que comienzan con m. Luegobuscara tomando la siguiente letra de la palabra(u), luego la n y ası sucesivamente. Esto lo puedehacer porque el diccionario se encuentra ordenado(busqueda binaria)

4 / 53


AngelVazquez-Patino

Busqueda

Utilidad

Busqueda secuencial

Busqueda binaria

Eficiencia

Ordenamiento

Utilidad

Clasificacion




Eficiencia

Burbuja

Seleccion

Insercion

Fuentes

Utilidad II

I Si el diccionario no estuviera ordenado se podrıatambien buscar la palabra recorriendo cada una delas hojas y revisando cada una de las palabras quese encuentren en esa hoja. Esto tardarıa mucho mas(menos eficiencia)(busqueda secuencial)

I Los tipos de busquedas a estudiar tienen semejanzacon los ejemplos dados

5 / 53


AngelVazquez-Patino

Busqueda

Utilidad

Busqueda secuencial

Busqueda binaria

Eficiencia

Ordenamiento

Utilidad

Clasificacion




Eficiencia

Burbuja

Seleccion

Insercion

Fuentes

Busqueda secuencial o lineal

1. Consiste en empezar desde el inicio del arreglo e ir atraves de cada elemento hasta encontrar el valorbuscado o hasta llegar al final

2. El arreglo no requiere estar ordenado

Busqueda secuencial en arreglos

1. https://youtu.be/W3ClRnYb0KM

6 / 53

https://youtu.be/W3ClRnYb0KM


AngelVazquez-Patino

Busqueda

Utilidad

Busqueda secuencial

Busqueda binaria

Eficiencia

Ordenamiento

Utilidad

Clasificacion




Eficiencia

Burbuja

Seleccion

Insercion

Fuentes

Algoritmo

7 / 53


AngelVazquez-Patino

Busqueda

Utilidad

Busqueda secuencial

Busqueda binaria

Eficiencia

Ordenamiento

Utilidad

Clasificacion




Eficiencia

Burbuja

Seleccion

Insercion

Fuentes

Busqueda binaria o dicotomica I

Condiciones

1. La estructura debe estar ordenada (ascendente odescendentemente)

2. Conocer el numero de elementos de la estructura

8 / 53


AngelVazquez-Patino

Busqueda

Utilidad

Busqueda secuencial

Busqueda binaria

Eficiencia

Ordenamiento

Utilidad

Clasificacion




Eficiencia

Burbuja

Seleccion

Insercion

Fuentes

Busqueda binaria o dicotomica II

Algoritmo (orden ascendente)

1. Se compara el valor buscado con el valor localizadoal centro del arreglo

2. Si el valor buscado es localizado, se termina labusqueda

3. Si el valor buscado es menor que el analizado,repetir proceso en la mitad inferior, sino en la mitadsuperior

4. El proceso de partir por la mitad de la estructura serepite hasta encontrar el valor o hasta que eltamano de la estructura restante sea cero (i.e.,valor no encontrado)

9 / 53


AngelVazquez-Patino

Busqueda

Utilidad

Busqueda secuencial

Busqueda binaria

Eficiencia

Ordenamiento

Utilidad

Clasificacion




Eficiencia

Burbuja

Seleccion

Insercion

Fuentes

Busqueda binaria o dicotomica III

Metodo de busqueda binaria

1. https://youtu.be/7qv1An90q2Q

2. https://youtu.be/7oa1qEPLFps

10 / 53

https://youtu.be/7qv1An90q2Q

https://youtu.be/7oa1qEPLFps


AngelVazquez-Patino

Busqueda

Utilidad

Busqueda secuencial

Busqueda binaria

Eficiencia

Ordenamiento

Utilidad

Clasificacion




Eficiencia

Burbuja

Seleccion

Insercion

Fuentes

Algoritmo

11 / 53


AngelVazquez-Patino

Busqueda

Utilidad

Busqueda secuencial

Busqueda binaria

Eficiencia

Ordenamiento

Utilidad

Clasificacion




Eficiencia

Burbuja

Seleccion

Insercion

Fuentes

Ejercicios

I Dado el conjunto de numeros 23, 12, 44, 9, 3, 8, 1,7, 0, 2, 4, 55 indique el numero de comparacionesque se deben hacer para encontrar el numero 1utilizando busqueda secuencial.

I Tome el conjunto de numeros dados y utilize labusqueda binaria para encontrar el numero 1.Indique el numero de comparaciones realizadas.

I Revise los ejercicios propuestos en el documento deEjercicios Basicos de Programacion.

12 / 53

https://goo.gl/X0UTxi


AngelVazquez-Patino

Busqueda

Utilidad

Busqueda secuencial

Busqueda binaria

Eficiencia

Ordenamiento

Utilidad

Clasificacion




Eficiencia

Burbuja

Seleccion

Insercion

Fuentes

Eficiencia

¿En que sentido un algoritmo de busqueda es maseficiente que otro?

¡Comparaciones!

13 / 53


AngelVazquez-Patino

Busqueda

Utilidad

Busqueda secuencial

Busqueda binaria

Eficiencia

Ordenamiento

Utilidad

Clasificacion




Eficiencia

Burbuja

Seleccion

Insercion

Fuentes

Eficiencia

¿En que sentido un algoritmo de busqueda es maseficiente que otro?

¡Comparaciones!

14 / 53


AngelVazquez-Patino

Busqueda

Utilidad

Busqueda secuencial

Busqueda binaria

Eficiencia

Ordenamiento

Utilidad

Clasificacion




Eficiencia

Burbuja

Seleccion

Insercion

Fuentes

Eficiencia: busqueda secuencial

I En el mejor caso se encontrara el valor en el primerelemento.

I En el peor caso se haran n comparaciones.

I El orden de complejidad en el peor caso serıa O(n).

15 / 53


AngelVazquez-Patino

Busqueda

Utilidad

Busqueda secuencial

Busqueda binaria

Eficiencia

Ordenamiento

Utilidad

Clasificacion




Eficiencia

Burbuja

Seleccion

Insercion

Fuentes

Eficiencia: busqueda binaria I

I En el mejor caso se encontrara el valor en elelemento del medio (una comparacion).

I Se hara el analisis para el peor caso.

I Inicialmente el numero de elementos a analizar es n.

I Tras la primera division, el numero de elementosque nos queda por analizar es, como mucho, n/2(pues nos hemos quedado con la mitad deelementos); tras la segunda division, el numero deelementos que nos queda sera, como mucho, n/4; yası sucesivamente.

I Por lo general, tras la division numero i , el numerode elementos por analizar sera, como mucho,

n

2i

16 / 53


AngelVazquez-Patino

Busqueda

Utilidad

Busqueda secuencial

Busqueda binaria

Eficiencia

Ordenamiento

Utilidad

Clasificacion




Eficiencia

Burbuja

Seleccion

Insercion

Fuentes

Eficiencia: busqueda binaria III El peor caso se da cuando el elemento a buscar no

se encuentra en el vector (es decir, cuando trasdividir los elementos por analizar nos quedemos conun numero menor a 1). Por lo tanto, el numeromaximo de divisiones a realizar es el menor numerom tal que

n

2m< 1

I Transformando esta formula a un logaritmo en base2, tenemos que

n < 2m

y quelog2 n < m

es decir, que el numero m depende, no del tamanon del arreglo, sino del logaritmo de dicho n.

17 / 53


AngelVazquez-Patino

Busqueda

Utilidad

Busqueda secuencial

Busqueda binaria

Eficiencia

Ordenamiento

Utilidad

Clasificacion




Eficiencia

Burbuja

Seleccion

Insercion

Fuentes

Eficiencia: busqueda binaria III

I Es por esto que el algoritmo de busqueda binariatiene una complejidad de orden logarıtmicoO(log2n).

18 / 53


AngelVazquez-Patino

Busqueda

Utilidad

Busqueda secuencial

Busqueda binaria

Eficiencia

Ordenamiento

Utilidad

Clasificacion




Eficiencia

Burbuja

Seleccion

Insercion

Fuentes

Eficiencia: busqueda secuencial vs binaria

19 / 53


AngelVazquez-Patino

Busqueda

Utilidad

Busqueda secuencial

Busqueda binaria

Eficiencia

Ordenamiento

Utilidad

Clasificacion




Eficiencia

Burbuja

Seleccion

Insercion

Fuentes

Algoritmos de ordenamiento

Definition (Ordenamiento)Reorganizar elementos de tal manera que cumplan conun criterio establecido.

e1 < e2 < e3 . . . < en → Ascendentee1 > e2 > e3 . . . > en → Descendente

20 / 53


AngelVazquez-Patino

Busqueda

Utilidad

Busqueda secuencial

Busqueda binaria

Eficiencia

Ordenamiento

Utilidad

Clasificacion




Eficiencia

Burbuja

Seleccion

Insercion

Fuentes

Utilidad

I Los datos ordenados son faciles de encontrar, estoimplica menos operaciones y menos tiempo(eficiencia).

I Existen varios algoritmos de ordenamiento que,dependiendo de la estrategia, serviran en mayor omenor grado para ordenar elementos.

I Que un algoritmo sea ingenioso, en este contexto,significa que ordena el conjunto desordenado con elmenor numero posible de comparaciones eintercambios.

21 / 53


AngelVazquez-Patino

Busqueda

Utilidad

Busqueda secuencial

Busqueda binaria

Eficiencia

Ordenamiento

Utilidad

Clasificacion




Eficiencia

Burbuja

Seleccion

Insercion

Fuentes

Clasificacion de los algoritmos de

ordenamiento

De acuerdo a la memoria utilizada

I Internos: cuando la memoria RAM es suficientepara el procesamiento

I Externos: cuando hace falta enviar cantidades deinformacion desde la memoria RAM a disco duro.Esto puede repetirse varias veces

De acuerdo a la estrategia utilizada

I Basicos: burbuja, seleccion e insercion

I Eficientes: shell sort, quick sort, radix sort, mergesort, heap sort, etc.

22 / 53


AngelVazquez-Patino

Busqueda

Utilidad

Busqueda secuencial

Busqueda binaria

Eficiencia

Ordenamiento

Utilidad

Clasificacion




Eficiencia

Burbuja

Seleccion

Insercion

Fuentes

Ordenamiento de burbuja I

IdeaTomar el elemento de mayor valor de un arreglo yllevarlo al final (ordenamiento ascendente); y estorepetirlo a todos los elementos

Porque del nombreAlguien se imagino que el elemento que se vadesplazando es como si una burbuja subiera desde elfondo del agua

23 / 53


AngelVazquez-Patino

Busqueda

Utilidad

Busqueda secuencial

Busqueda binaria

Eficiencia

Ordenamiento

Utilidad

Clasificacion




Eficiencia

Burbuja

Seleccion

Insercion

Fuentes

Ordenamiento de burbuja II

Estrategia

1. Recorrer el arreglo desde el elemento 0 con uniterador i.

2. En cada paso preguntar si el elemento i+1 es menoral elemento i (ordenamiento ascendente). Si es ası,se intercambian los elementos.

3. Ası, el elemento mayor quedara en el ındice mayor

4. Una vez que se llegue al ultimo elemento delarreglo, se comienza de nuevo con el paso 1.

5. Se repite hasta que no haya ningun intercambio deelementos.


24 / 53


AngelVazquez-Patino

Busqueda

Utilidad

Busqueda secuencial

Busqueda binaria

Eficiencia

Ordenamiento

Utilidad

Clasificacion




Eficiencia

Burbuja

Seleccion

Insercion

Fuentes

Ordenamiento de burbuja III

1. https://youtu.be/L3d48etbseY

Pseudocodigo

1: for i = 1 hasta n do2: for j = 0 hasta n-i do3: if arreglo[j] > arreglo[j+1] then4: intercambiar(arreglo[j], arreglo[j+1]);5: end if6: end for7: end for

25 / 53

https://youtu.be/L3d48etbseY


AngelVazquez-Patino

Busqueda

Utilidad

Busqueda secuencial

Busqueda binaria

Eficiencia

Ordenamiento

Utilidad

Clasificacion




Eficiencia

Burbuja

Seleccion

Insercion

Fuentes

Ejemplo, ordenamiento de burbujaOrden ascendente

26 / 53


AngelVazquez-Patino

Busqueda

Utilidad

Busqueda secuencial

Busqueda binaria

Eficiencia

Ordenamiento

Utilidad

Clasificacion




Eficiencia

Burbuja

Seleccion

Insercion

Fuentes

Ejercicios

I Usando el metodo de la burbuja, ordenedescendentemente el siguiente conjunto denumeros: 9, 3, 8, 1, 7, 0, 2, 4. Indique el numero depasadas realizadas.

I Usando el metodo de la burbuja, ordeneascendentemente el siguiente conjunto de numeros:8, 2, 99, 21, 45, 9, 23. Indique el numero depasadas realizadas.

I Revise los ejercicios propuestos en el documento deEjercicios Basicos de Programacion.

27 / 53



AngelVazquez-Patino

Busqueda

Utilidad

Busqueda secuencial

Busqueda binaria

Eficiencia

Ordenamiento

Utilidad

Clasificacion




Eficiencia

Burbuja

Seleccion

Insercion

Fuentes

Algoritmo de seleccion I

Estrategia

1. Se busca el menor de todos los elementos y se leubica en la primera posicion del arreglo.

2. Se busca el menor de entre los elementos quequedan y se lo intercambia con el primer elementodel arreglo que queda.

3. Se repite el proceso para todos los elementos delarreglo.


1. https://youtu.be/l0YwcUJB3vo

2. https://youtu.be/KCvr7eHXEHE

28 / 53

https://youtu.be/l0YwcUJB3vo

https://youtu.be/KCvr7eHXEHE


AngelVazquez-Patino

Busqueda

Utilidad

Busqueda secuencial

Busqueda binaria

Eficiencia

Ordenamiento

Utilidad

Clasificacion




Eficiencia

Burbuja

Seleccion

Insercion

Fuentes

Algoritmo de seleccion II

Pseudocodigo

1: for i = 0 hasta n-2 do2: mınimo = i;3: for j = i+1 hasta n-1 do4: if arreglo[j] < arreglo[mınimo] then5: mınimo = j;6: end if7: end for8: intercambiar(arreglo[i], arreglo[mınimo]);9: end for

29 / 53


AngelVazquez-Patino

Busqueda

Utilidad

Busqueda secuencial

Busqueda binaria

Eficiencia

Ordenamiento

Utilidad

Clasificacion




Eficiencia

Burbuja

Seleccion

Insercion

Fuentes

Ejemplo, algoritmo de seleccion

Orden ascendente

30 / 53


AngelVazquez-Patino

Busqueda

Utilidad

Busqueda secuencial

Busqueda binaria

Eficiencia

Ordenamiento

Utilidad

Clasificacion




Eficiencia

Burbuja

Seleccion

Insercion

Fuentes

Ejercicios

1. Ordene, ascendentemente y descendentemente,usando el algoritmo de seleccion, el siguienteconjunto de numeros: 6, 2, 11, 23, 1, 5, 4. Indiqueel numero de pasadas realizadas.

2. Ordene, ascendentemente y descendentemente,usando el algoritmo de seleccion, el siguienteconjunto de letras: K, M, S, C, E, W, P, Q . Indiqueel numero de pasadas realizadas.

3. Revise los ejercicios propuestos en el documento deEjercicios Basicos de Programacion.

31 / 53



AngelVazquez-Patino

Busqueda

Utilidad

Busqueda secuencial

Busqueda binaria

Eficiencia

Ordenamiento

Utilidad

Clasificacion




Eficiencia

Burbuja

Seleccion

Insercion

Fuentes

Algoritmo de insercion I

Estrategia

1. Se toma el primer elemento del arreglo como elprimer elemento de lo que llamaremos el arregloordenado.

2. Se toma el proximo numero del arreglo y secompara con los elementos del arreglo ordenado,hasta encontrar su posicion.

3. Se repite el proceso para todos los elementos delarreglo.


32 / 53


AngelVazquez-Patino

Busqueda

Utilidad

Busqueda secuencial

Busqueda binaria

Eficiencia

Ordenamiento

Utilidad

Clasificacion




Eficiencia

Burbuja

Seleccion

Insercion

Fuentes

Algoritmo de insercion II

1. https://youtu.be/5kVQ8kf52K4

2. https://youtu.be/a7g7Z5dMdgQ

Pseudocodigo

1: for i = 1 hasta n-1 do2: j = i;3: while j > 0 and arreglo[j-1] > arreglo[j] do4: intercambiar(arreglo[j], arreglo[j-1]);5: j = j-1;6: end while7: end for

33 / 53

https://youtu.be/5kVQ8kf52K4

https://youtu.be/a7g7Z5dMdgQ


AngelVazquez-Patino

Busqueda

Utilidad

Busqueda secuencial

Busqueda binaria

Eficiencia

Ordenamiento

Utilidad

Clasificacion




Eficiencia

Burbuja

Seleccion

Insercion

Fuentes

Ejemplo, algoritmo de insercion

Orden ascendente

34 / 53


AngelVazquez-Patino

Busqueda

Utilidad

Busqueda secuencial

Busqueda binaria

Eficiencia

Ordenamiento

Utilidad

Clasificacion




Eficiencia

Burbuja

Seleccion

Insercion

Fuentes

Ejercicios

1. Ordene, ascendentemente y descendentemente,usando insercion, el siguiente conjunto de numeros:8, 3, 2, 9, 10, 7, 1, 4, 5. Indique las pasadasrealizadas.

2. Ordene, ascendentemente y descendentemente,usando insercion, el siguiente conjunto de letras: J,M, A, E, W, Q, P, R, M, B,X. Indique el numero depasadas realizadas.

3. Revise los ejercicios propuestos en el documento deEjercicios Basicos de Programacion.

35 / 53



AngelVazquez-Patino

Busqueda

Utilidad

Busqueda secuencial

Busqueda binaria

Eficiencia

Ordenamiento

Utilidad

Clasificacion




Eficiencia

Burbuja

Seleccion

Insercion

Fuentes

Eficiencia

¿En que sentido un algoritmo de ordenamiento es maseficiente que otro?

¡Comparaciones e intercambios!

36 / 53


AngelVazquez-Patino

Busqueda

Utilidad

Busqueda secuencial

Busqueda binaria

Eficiencia

Ordenamiento

Utilidad

Clasificacion




Eficiencia

Burbuja

Seleccion

Insercion

Fuentes

Eficiencia

¿En que sentido un algoritmo de ordenamiento es maseficiente que otro?

¡Comparaciones e intercambios!

37 / 53


AngelVazquez-Patino

Busqueda

Utilidad

Busqueda secuencial

Busqueda binaria

Eficiencia

Ordenamiento

Utilidad

Clasificacion




Eficiencia

Burbuja

Seleccion

Insercion

Fuentes

Ordenamiento de burbuja I

Comparaciones

I Para ordenar un arreglo de n elementos, el numerode comparaciones siempre es:

c(n) = (n−1) + (n−2) + · · ·+ 2 + 1 =n × (n − 1)

2

I c(n) no depende del orden de los terminos, sino delnumero de terminos:

Θ(c(n)) = n2

I Por lo tanto la cota ajustada asintotica del numerode comparaciones pertenece al orden de n cuadrado.

38 / 53


AngelVazquez-Patino

Busqueda

Utilidad

Busqueda secuencial

Busqueda binaria

Eficiencia

Ordenamiento

Utilidad

Clasificacion




Eficiencia

Burbuja

Seleccion

Insercion

Fuentes

Ordenamiento de burbuja II

Intercambios

39 / 53


AngelVazquez-Patino

Busqueda

Utilidad

Busqueda secuencial

Busqueda binaria

Eficiencia

Ordenamiento

Utilidad

Clasificacion




Eficiencia

Burbuja

Seleccion

Insercion

Fuentes

Ordenamiento de burbuja IIII El numero de intercambios i(n), que hay que

realizar depende del orden de los terminos ypodemos diferenciar el mejor y peor caso.

Definition (mejor caso)Si el arreglo esta previamente ordenado.

Definition (peor caso)Si el arreglo esta previamente ordenado en orden inverso.

I Por lo que no se puede determinar una cota ajustadaasintotica del numero de intercambios, dado queeste dependera del orden del vector en cuestion.

Θ(i(n)) =?

40 / 53


AngelVazquez-Patino

Busqueda

Utilidad

Busqueda secuencial

Busqueda binaria

Eficiencia

Ordenamiento

Utilidad

Clasificacion




Eficiencia

Burbuja

Seleccion

Insercion

Fuentes

Ordenamiento de burbuja: peor caso I

Si pasamos al algoritmo un arreglo ordenado en ordeninverso realizara un numero de comparaciones

c(n) =n2 − n

2

y tendra que realizar un numero igual de intercambiosentre los terminos del arreglo, dado que en cadacomparacion los terminos estaran desordenados, y serealizara el intercambio.

i(n) =n2 − n

2

Por lo tanto en el caso mas desfavorable tanto el numerode comparaciones como el de intercambios coinciden:

41 / 53


AngelVazquez-Patino

Busqueda

Utilidad

Busqueda secuencial

Busqueda binaria

Eficiencia

Ordenamiento

Utilidad

Clasificacion




Eficiencia

Burbuja

Seleccion

Insercion

Fuentes

Ordenamiento de burbuja: peor caso II

O(c(n)) = O(i(n)) = n2

El numero de comparaciones y de intercambios, en elpeor caso, pertenece al orden de n cuadrado.

42 / 53


AngelVazquez-Patino

Busqueda

Utilidad

Busqueda secuencial

Busqueda binaria

Eficiencia

Ordenamiento

Utilidad

Clasificacion




Eficiencia

Burbuja

Seleccion

Insercion

Fuentes

Ordenamiento de burbuja: mejor caso I

En el mejor caso el numero de comparaciones sera elmismo que en cualquier otro caso:

Ω(c(n)) = n2

La cota inferior asintotica del numero de comparacionespertenece al orden de n cuadrado, como en los demascasos, pero en todas las comparaciones el orden es elcorrecto y por tanto no se realiza ningun intercambio:

i(n) = 0

Por lo tanto el coste de intercambios no depende de n, yes constante:

Ω(i(n)) = 1

43 / 53


AngelVazquez-Patino

Busqueda

Utilidad

Busqueda secuencial

Busqueda binaria

Eficiencia

Ordenamiento

Utilidad

Clasificacion




Eficiencia

Burbuja

Seleccion

Insercion

Fuentes

Ordenamiento de burbuja: mejor caso II

A tener en cuenta

I El ordenamiento de burbuja tiene una complejidadΩ(n2) igual que el algoritmo de seleccion.

I Cuando un arreglo ya esta ordenado, a diferenciadel algoritmo de insercion, que pasara por el arreglouna vez y encontrara que no hay necesidad deintercambiar las posiciones de los elementos, elordenamiento de burbuja esta forzado a pasar pordichas comparaciones, esto hace que su complejidadsea cuadratica, incluso en el mejor de los casos.

I El ordenamiento de burbuja se cataloga como elalgoritmo mas ineficiente que existe.

44 / 53


AngelVazquez-Patino

Busqueda

Utilidad

Busqueda secuencial

Busqueda binaria

Eficiencia

Ordenamiento

Utilidad

Clasificacion




Eficiencia

Burbuja

Seleccion

Insercion

Fuentes

Algoritmo de seleccion I

Comparaciones

I Para ordenar un arreglo de n elementos, el numerode comparaciones siempre es:

c(n) = (n−1) + (n−2) + · · ·+ 2 + 1 =n × (n − 1)

2

I c(n) no depende del orden de los terminos, sino delnumero de terminos.

Θ(c(n)) = n2

I Por lo tanto la cota ajustada asintotica del numerode comparaciones pertenece al orden de n cuadrado.

45 / 53


AngelVazquez-Patino

Busqueda

Utilidad

Busqueda secuencial

Busqueda binaria

Eficiencia

Ordenamiento

Utilidad

Clasificacion




Eficiencia

Burbuja

Seleccion

Insercion

Fuentes

Algoritmo de seleccion II

Intercambios

I El numero de intercambios i(n) tambien es fijo.Tengase en cuenta que la instruccion deintercambio siempre se ejecuta.

i(n) = n

Definition (mejor caso)Si el arreglo esta previamente ordenado.

Definition (peor caso)Si el arreglo esta previamente ordenado en orden inverso.

46 / 53


AngelVazquez-Patino

Busqueda

Utilidad

Busqueda secuencial

Busqueda binaria

Eficiencia

Ordenamiento

Utilidad

Clasificacion




Eficiencia

Burbuja

Seleccion

Insercion

Fuentes

Algoritmo de seleccion III

I sea cual sea el arreglo, y el orden de sus elementos,lo que implica en todos los casos un coste lineal:

Θ(i(n)) = n

I la cota ajustada asintotica del numero deintercambios es lineal, del orden de n.

I La formula que representa el rendimiento delalgoritmo, viene dada por

c(n) =n2 + n

2

47 / 53


AngelVazquez-Patino

Busqueda

Utilidad

Busqueda secuencial

Busqueda binaria

Eficiencia

Ordenamiento

Utilidad

Clasificacion




Eficiencia

Burbuja

Seleccion

Insercion

Fuentes

Algoritmo de insercion I

EficienciaDepende del numero de comparaciones y del numero decopias que el algoritmo requiere.

Comparaciones

I En la primera pasada, se compara un maximo de unıtem. En la segunda pasada, se compara un maximode dos ıtems, y ası hasta un maximo de n − 1comparaciones en la ultima pasada. Esto es

1 + 2 + 3 + . . . + (n − 1) =n × (n − 1)

2

48 / 53


AngelVazquez-Patino

Busqueda

Utilidad

Busqueda secuencial

Busqueda binaria

Eficiencia

Ordenamiento

Utilidad

Clasificacion




Eficiencia

Burbuja

Seleccion

Insercion

Fuentes

Algoritmo de insercion II

I Sin embargo, ya que en cada pasada un promediode solamente la mitad del numero maximo de ıtemsson realmente comparados antes de que seencuentre el punto de insercion, se puede dividireste numero entre dos, lo que da

n × (n − 1)

4

Numero de copias

49 / 53


AngelVazquez-Patino

Busqueda

Utilidad

Busqueda secuencial

Busqueda binaria

Eficiencia

Ordenamiento

Utilidad

Clasificacion




Eficiencia

Burbuja

Seleccion

Insercion

Fuentes

Algoritmo de insercion III

I El numero de copias es aproximadamente el mismoque el numero de comparaciones. Sin embargo, unacopia no consume tanto tiempo como unintercambio, ası que para datos aleatorios estealgoritmo corre dos veces mas rapido que elalgoritmo de burbuja y mas rapido que el algoritmode seleccion.

I En cualquier caso, el algoritmo de insercion corre enO(n2) en tiempo para datos aleatorios.

50 / 53


AngelVazquez-Patino

Busqueda

Utilidad

Busqueda secuencial

Busqueda binaria

Eficiencia

Ordenamiento

Utilidad

Clasificacion




Eficiencia

Burbuja

Seleccion

Insercion

Fuentes

Algoritmo de insercion IV

I Para datos que estan ya ordenados o casiordenados, el algoritmo de insercion es mejor.Cuando los datos estan en orden, la condicion en elwhile nunca es verdadera, lo que ejecuta n-1 veces.En este caso el algoritmo corre en O(n) en tiempo.Si los datos estan casi ordenados, el algoritmo correcasi en O(n) en tiempo, lo que lo hace una manerasimple y eficiente para ordenar un archivo queesta solo un poco fuera de orden.

I Sin embargo, para datos que estan en orden inverso,toda posible comparacion y desplazamiento se llevaa cabo, ası que el algoritmo no corre mas rapidoque el algoritmo de burbuja.

51 / 53


AngelVazquez-Patino

Busqueda

Utilidad

Busqueda secuencial

Busqueda binaria

Eficiencia

Ordenamiento

Utilidad

Clasificacion




Eficiencia

Burbuja

Seleccion

Insercion

Fuentes

Algoritmo de insercion V

I Revise eso utilizando la opcion reverse-sorted en elapplet InsertSort Workshop(http://cs.brynmawr.edu/Courses/cs206/spring2004/lafore.html).

52 / 53

http://cs.brynmawr.edu/Courses/cs206/spring2004/lafore.html

http://cs.brynmawr.edu/Courses/cs206/spring2004/lafore.html


AngelVazquez-Patino

Busqueda

Utilidad

Busqueda secuencial

Busqueda binaria

Eficiencia

Ordenamiento

Utilidad

Clasificacion




Eficiencia

Burbuja

Seleccion

Insercion

Fuentes

Fuentes

Libros

• Lafore, R., 2003. Data structures & algorithms inJava, 2nd ed. Sams, Indianapolis, USA. Capıtulos 2y 3. (Disponible en la biblioteca)

• Deitel, P.J., Deitel, H.M., 2012. Java: How toProgram, 9th ed. Prentice Hall, Upper Saddle River,N.J. Capıtulo 19. (Disponible en la biblioteca)

53 / 53

Programación: búsquedas y ordenamientos

Engineering

Transcript of Programación: búsquedas y ordenamientos