09/02/2018

1

Facultad de Informática Culiacán

Tema: Arreglos

Instructor: MC. Gerardo Gálvez Gámez

Febrero de 2017

UNIVERSIDAD AUTÓNOMA DE SINALOA

Arreglos • FIUAS

Competencia

• Construir programas que utilicen arreglosunidimensionales y multidimensionales parasolucionar problemas del mundo real, previoanálisis y diseño para la obtención de un TDA, enlos cuales se implementen las operacionesbásicas que permiten realizar, en al menos unlenguaje de programación.

09/02/2018

2

Arreglos • FIUAS

Temas▫ Arreglos

Definición.

Unidimensionales.

Bidimensionales.

Multidimensionales.

Operaciones.

Clases para la implementación de arreglos.

Resolución de problemas con arreglos.

Arreglos • FIUAS

Descripción general

Los Arreglos proporcionan una formaimportante de agrupar datos.

Para sacar el máximo partido a esta estructura,es fundamental entender como:

CreaciónUsos

09/02/2018

3

Arreglos • FIUAS

Introducción a los arreglos

• ¿Qué es un arreglo?

• Notación para arreglos

• Rango de un arreglo

• Acceso a los elementos de un arreglo

Arreglos • FIUAS

¿Qué es una arreglo?

Es un tipo de dato estructurado formado por un conjunto de datos.

Es una secuencia de elementos, donde:▫ Todos sus elementos son del mismo tipo de dato (datos

simples como: ENTERO, REAL, etc.),

▫ Se accede a elementos individuales usando índices enteros,

Arreglo

Índice entero 1

(uno)

Índice entero 5

(cinco)

Celda

09/02/2018

4

Arreglos • FIUAS

¿Qué es un arreglo?

Los arreglos permiten el acceso aleatorio.

Los elementos de un arreglo;▫ Ocupan posiciones de memoria contiguas,

▫ Lo que significa que un programa puede acceder con la misma rapidez a todos los elementos de un arreglo.

Índice entero 1

(uno)

Índice entero 5

(cinco)

Arreglo

1024 1025 1026 1027 1028

Arreglos • FIUAS

Definición de Arreglo (Cairo Pág. 2 )

Se define como una colección finita, homogénea yordenada de elementos:

▫ Finita: Todo arreglo tiene un límite; es decir, se debedeterminar cuál será el número máximo de elementos queformarán parte del arreglo.

▫ Homogénea: Todos los elementos de un arreglo son delmismo tipo. Es decir, todos enteros, todos booleanos,etcétera, pero nunca una combinación de distintos tipos.

▫ Ordenada: Se puede determinar cuáles son el primero, elsegundo, el tercero, ... Y el enésimo elementos.

09/02/2018

5

Arreglos • FIUAS

Notación para arreglos

Una variable de tipo arreglo se define especificando: ▫ El tipo de elementos del arreglo.▫ El rango del arreglo.

▫ El nombre de la variable.

Especifica el tipo de datos para los elementos del arreglo

Especifica el rango del arreglo

Especifica el nombre de la variable arreglo

tipo nombre[Tamaño ]

Arreglos • FIUAS

Rango de un arreglo

• El rango se conoce también como dimensión del arreglo

• El número de índices asociados con cada elemento

Rango 1: Unidimensional

Un solo índice asociado con

cada elemento ENTERO

Rango 2: Bidimensional

Dos índices asociados con

cada elemento ENTERO

ENTERO Fila[ ] ENTERO Cuadrícula[ , ]

09/02/2018

6

Arreglos • FIUAS

Acceso a los elementos de un arreglo

Se indica un índice entero para cada rango

▫ Los índices se cuentan a partir de uno

4

3

2

ENTERO Fila[ ]

...

Fila[4]

ENTERO Cuadricula[,]

...

Cuadrícula[2,3]

Arreglos • FIUAS

• Creación de un arreglo

• Creación de un arreglo de tamaño calculado

Creación de arreglos

09/02/2018

7

Arreglos • FIUAS

Creación de un arreglo

Fila

0 0 0 0

Cuadrícula

0 0 0

0 0 0

Variable Arreglo

ENTERO Fila[4]

ENTERO Cuadricula[2,3]

Constantes

Arreglos • FIUAS

Creación de un arreglo de tamaño

calculado

No es necesario que el tamaño de un arreglo seauna constante de tiempo de compilación:

▫ Se puede usar cualquier expresión entera válida

▫ El acceso a los elementos es igualmente rápido entodos los casos

09/02/2018

8

Arreglos • FIUAS

Creación de un arreglo de tamaño

calculado

▫Tamaño del arreglo especificado por constanteentera de tiempo de compilación:

▫Tamaño de arreglo especificado por valor entero detiempo de ejecución:

CONST ENTERO Tamaño=4

ENTERO Fila[Tamaño]

ENTERO Tamaño

IMPRIMIR “Indique el tamaño del arreglo:”

LEER Tamaño

ENTERO Fila[Tamaño]

Arreglos • FIUAS

Creación de un arreglo de tamaño

calculado

▫Tamaño del arreglo especificado por constanteentera de tiempo de compilación:

▫Tamaño de arreglo especificado por valor entero detiempo de ejecución:

CONST ENTERO Renglones=2

CONST ENTERO Columnas=3

ENTERO Cuadricula[Renglones, Columnas]

ENTERO Renglones, Columnas

IMPRIMIR “Indique el tamaño de Renglones para el arreglo:”

LEER Renglones

IMPRIMIR “Indique el tamaño de Columnas para el arreglo:”

LEER Columnas

ENTERO Cuadricula[Renglones, Columnas]

09/02/2018

9

Arreglos • FIUAS

Operaciones en Arreglos (Pág. #7 Cairó)

LecturaEscritura

(Imprimir)Asignación

(inicialización)

Actualización

• Insertar• Eliminar• Modificar

Ordenación Búsqueda

Arreglos • FIUAS

Operaciones en Arreglos

• Lectura/Escritura.- El proceso de lectura de un arregloconsiste en leer y asignar un valor a cada uno de suscomponentes. Similar a la lectura, se debe escribir el valorde cada uno de los componentes.

• Asignación.- En este caso no es posible asignardirectamente un valor a todo el arreglo; sino que se debeasignar el valor deseado a cada componente.

• Actualización.- Este proceso se puede dar a través de tresoperaciones básicas: inserción o adición de un nuevoelemento al arreglo, eliminación o borrado de un elementodel arreglo y modificación o reasignación de un elementodel arreglo.

09/02/2018

10

Arreglos • FIUAS

Operaciones en Arreglos

• Ordenación.-Es el proceso de organizar los elementos deun vector en algún orden dado que puede ser ascendente odescendente. Existen diferentes formas o métodos parahacer este proceso: método de burbuja, método de burbujamejorado, ordenación por selección, inserción o método dela baraja, método Shell, Binsort o por urnas, ordenaciónpor montículos o HeapSort, por mezcla o MergeSort,método de la sacudida o Shackersort, Rapid Sort o QuickSort, por Árboles, etc.

• Búsqueda.-Consiste en encontrar un determinado valordentro del conjunto de datos del arreglo para recuperaralguna información asociada con el valor buscado. Existendiferentes formas para hacer esta operación: búsquedasecuencial o lineal, búsqueda binaria, búsqueda HASH,árboles de búsqueda.

Arreglos • FIUAS

Actividad de Aprendizaje

TAREA: Tomando como referencia elcontexto anterior, diseñe el TDAcorrespondiente e impleméntelo en unlenguaje de programación, tal que permitirla creación y manejo de arreglosunidimensionales y multidimensionales.

Objetivo:

El alumno elaborará un proyecto para ejemplificarel uso de arreglos unidimensionales ymultidimensionales de tamaño N, en tiempo decompilación o ejecución.

Operaciones:▫ Crear el Arreglo

▫ Insertar Datos

▫ Imprimir Datos

▫ otros

09/02/2018

11

Arreglos • FIUAS

Ejemplo

Diseño de la clase que representará al TDAArreglo.

Cairó

Arreglos • FIUAS

TDAArreglo

-tamaño:int-datos [ ]:int-mensaje: string-apuntadorElemento:int

+TDAArreglo()+TDAArreglo(pTamaño:int)+TDAArreglo(pArreglo [ ] :int) //se define a partir de los elementos de un arreglo proporcionado

+getTamaño:int+getMensjae:string+getApuntadorElemento:int+getDatos[ ] :int

+InicializarArreglo(pValor:int)+InsertarElemento(pElemento:int) //agrega un valor al arreglo, según posición siguiente

+InsertaElemento(pElemento:int, pPosicion:int)//inserta el elemento en la posición indicada, los demás elementos se recorren

+AccesoElemento(pPosicion:int)//regresa el valor de la celda correspondiente

+EliminarElementoPosicion(pPosicion:int)//eliminar el valor, renumerando los espacios delante de..

+EliminarElemento(pElemento:int)//eliminar la primera aparición, renumerando los espacios delante de..

+EliminarTodosElementos()+BuscarElemento():int // regresa la posición de la primera aparición del elemento

09/02/2018

12

Arreglos • FIUAS

Arreglos • FIUAS

Temas

1. Introducción

2. Conceptos

3. Categorías de los Métodos de ordenación

4. Métodos directos

5. Método de Intercambio o de burbuja

6. Codificación

7. Análisis de eficiencia del método

09/02/2018

13

Arreglos • FIUAS

Introducción:

• Operaciones básicas en el campo de lainformática:

▫ Ordenamiento,▫ Búsqueda e,▫ Intercalación.

▫ Las estadísticas señalan que sonoperaciones en las que las computadorasemplean la mitad de su tiempo.

Arreglos • FIUAS

Conceptos

• La Ordenación (clasificación)

▫ Es la operación de organizar un conjunto de datosen algún orden dado, tal como:

Datos Numérico ó Alfanuméricos:

Creciente, ó

Decreciente .

Operaciones típicas de ordenación son:

Lista de números,

Archivo de clientes de banco,

Nombres de una agenda telefónica, etc.

09/02/2018

14

Arreglos • FIUAS

Conceptos

• La búsqueda de información (recuperación):

▫ Es al igual que la ordenación otra operación muyfrecuente en el tratamiento de información.

▫ La búsqueda es una actividad que se realizadiariamente en cualquier aspecto de la vida.

▫ Normalmente se realiza sobre elementos ordenados.

Arreglos • FIUAS

Categorías de los Métodos de ordenación

1. Ordenación interna.

▫ Clasificación de los valores almacenados en unvector, según el orden creciente o decreciente y estose realiza en memoria central y rápida (RAM).

2. Ordenación externa.

▫ Es la clasificación de los registros de un archivosituado en un soporte externo (cinta, disco duro,diskette, cd-rom, etc.); aunque es menos rápido.

09/02/2018

15

Arreglos • FIUAS

Clasificación de los métodos internos

• Métodos directos (n2)

▫ Su implementación es sencilla

▫ Son fáciles de comprender

▫ Son ineficientes cuando N es de tamaño mediano o grande.

• Métodos logarítmicos(n *log n)

▫ Son mas complejos

▫ Su elaboración es mas sofisticada

▫ Son menos intuitivos

▫ Difíciles de entender

▫ Son mas eficientes, por requerir menos comparaciones y movimientos

Arreglos • FIUAS

MÉTODOS DIRECTOS

• Son los que se realizan en el espacio ocupado porel arreglo o vector. Los más conocidos son:

▫ Ordenación por Intercambio Directo (burbuja).

(Método # 1, Método # 2 y Método # 3).

▫ Ordenación por Inserción directa.

▫ Ordenación por Inserción Binaria.

▫ Ordenación por Selección Directa.

▫ Ordenación por el método de Shell.

▫ Ordenación por el método Quicksort (rápido).

09/02/2018

16

Arreglos • FIUAS

15 67 16 44 12 35

Problema

• Suponga que se desean ordenar las siguientesclaves del siguiente arreglo, utilizando el Método

de Intercambio Directo (burbuja).

• ArregloÍndice 0 1 2 3 4 5

Arreglos • FIUAS

Ordenación por Intercambio Directo (burbuja)

• Es el más utilizado entre los estudiantesprincipiantes en computación por su fácilcompresión de programación.

• Es el método más ineficiente.

• Puede trabajar de dos manera diferentes:

▫ Llevando los elementos mas pequeños hacia laparte izquierda del arreglo, ó

▫ Trasladando los elementos mas grandes haciasu parte derecha.

09/02/2018

17

Arreglos • FIUAS

Ordenación por Intercambio o de burbuja

La idea de la ordenación por burbuja es tomar unelemento y compararlo con el resto, intercambiándolossi están desordenados.

El método realiza n-1 pasadas.

En la primera pasada el mayor elemento se varecorriendo hasta ocupar el último lugar, al final de lasegunda pasada se obtienen los dos últimos elementosordenados y así con el resto de las pasadas.

Al final los elementos son arrastrados como una burbujahacia el final de la estructura.

Arreglos • FIUAS

Funcionamiento Lógico

09/02/2018

18

Arreglos • FIUAS

15 67 16 44 12 35

Ejemplo

1er Pasada n-1 comparaciones, donde n=total de elementos

Índice 0 1 2 3 4 5

1.-Comparar: 15 > 67 No

2.-Comparar: 67 > 16 Si, Intercambiar

3.-Comparar: 67 > 44, Si, Intercambiar

4.-Comparar: 67 > 12, Si, Intercambiar

5.-Comparar: 67 > 35, Si Intercambiar

15 16 67 44 12 35

15 16 44 67 12 35

15 16 44 12 67 35

15 16 44 12 35 67

Arreglos • FIUAS

Ejemplo

2da Pasada n-2 comparaciones, donde n=total de elementos

Índice 0 1 2 3 4 5

1.- Comparar: 15 > 16 No

2.- Comparar: 16 > 44 No

3.- Comparar: 44 > 12, Si, Intercambiar

4.- Comparar: 44 > 35, Si, Intercambiar

15 16 44 12 35 67

15 16 12 44 35 67

15 16 12 35 44 67

09/02/2018

19

Arreglos • FIUAS

Ejemplo

3ra Pasada n-3 comparaciones, donde n=total de elementos

Índice 0 1 2 3 4 5

1.- Comparar: 15 > 16 No

2.- Comparar: 16 12, Si, Intercambio

3.- Comparar: 16 > 35, No

15 16 12 35 44 67

15 12 16 35 44 67

15 12 16 35 44 67

Arreglos • FIUAS

Ejemplo

4ta Pasada n-4 comparaciones, donde n=total de elementos

Índice 0 1 2 3 4 5

1.- Comparar: 15 > 12, Si, Intercambio

2.- Comparar: 15 >16,No

15 12 16 35 44 67

12 15 16 35 44 67

09/02/2018

20

Arreglos • FIUAS

Ejemplo

5ta Pasada n-5 comparaciones, donde n=total de elementos

Índice 0 1 2 3 4 5

1.- Comparar: 12 > 15, No

FIN, Arreglo ordenado

12 15 16 35 44 67

Arreglos • FIUAS

C = (n – 1) + (n – 2) + ... + 2 + 1 = n * (n – 1)

2

que es igual a:

n2 – n

2C =

ANÁLISIS DE EFICIENCIA DEL MÉTODO

• El número de comparaciones en:▫ La primera pasada realizamos (n – 1) comparaciones,

▫ En la segunda pasada (n - 2) comparaciones,

▫ En la tercera pasada (n – 3) comparaciones y así sucesivamente hasta llegar a 2 y 1 comparaciones entre claves, siendo n el número de elementos del arreglo.

• Por lo tanto:

09/02/2018

21

Arreglos • FIUAS

Respecto del número de movimientos, éstos dependen de si el arreglo seencuentra ordenado, desordenado o en orden inverso. Los movimientos para cadauno de estos casos son:

Mmín = 0 Mmed = 0.75 * (n2 – n) Mmáx = 1.5 * (n2 – n)

Así por ejemplo si tiene que ordenarse un arreglo que contiene 500 elementos, seefectuaría lo siguiente:

a) Si el arreglo se encuentra ordenado:* 124 750 comparaciones* 0 movimientos

b) Si lo elementos del arreglo se encuentran dispuestos en forma aleatoria:* 124 750 comparaciones* 187 125 movimientos

c) Si los elementos del arreglo se encuentran en orden inverso:* 124 750 comparaciones* 374 250 movimientos

Ahora bien, el tiempo necesario para ejecutar el algoritmo de la burbuja esproporcional a n2, O (n2), donde n es el número de elementos del arreglo.

Arreglos • FIUAS

Actividad de aprendizaje:

diseñar e implementar el método delalgoritmo de ordenación por elmétodo por Intercambio Directo(burbuja), para el TDA Arreglo.

09/02/2018

22

Arreglos • FIUAS

Intercambio Directo (burbuja) con Señal

Arreglos • FIUAS

15 12 16 44 50

Problema

• Realice los pasos gráficos para ordenar elsiguiente arreglo, utilizando el método de

Intercambio Directo (burbuja).

• ArregloÍndice 0 1 2 3 4

Determinar:

Número de pasadas:_____

Número de comparaciones:______

Número de intercambios:_______

09/02/2018

23

Arreglos • FIUAS

ORDENACIÓN POR EL MÉTODO DE INTERCAMBIO

DIRECTO CON SEÑAL

• Este método es una modificación del método deintercambio directo (burbuja).

• La idea central de este algoritmo consiste en utilizar unamarca o señal para indicar que no se ha producidointercambio en una pasada.

• Es decir, se comprueba si el arreglo está totalmenteordenado después de cada pasada, terminando suejecución en caso afirmativo.

Arreglos • FIUAS

Actividad de aprendizaje

Diseñar e implementar el método del algoritmo de ORDENACIÓN POR EL MÉTODO DE INTERCAMBIO DIRECTO CON SEÑAL, para el TDA Arreglo.

09/02/2018

24

Arreglos • FIUAS

Burbuja #3

Arreglos • FIUAS

Método de la sacudida (shaker sort)

• Es una optimización del método de la burbuja.

• Idea:▫ Mezcla las dos formas en que se puede realizar el método

dela burbuja.▫▫ Por cada pasada se tienen 2 etapas:

1ra.- de derecha a izquierda: Se trasladan los elementos maspequeños hacia la izquierda del arreglo, almacenando en unavariable la posición del elemento intercambiado.

2da.-de izquierda a derecha: se trasladan los elementos masgrandes hacia la derecha del arreglo, almacenando en otravariable la posición del elemento intercambiado.

▫ El resto de las pasadas se trabajan con los elementos delarreglo comprendidos entre las posiciones almacenadas enlas variable auxiliares.

09/02/2018

25

Arreglos • FIUAS

Método de la sacudida (shaker sort)

• El algoritmo termina cuando en una etapano se producen intercambios, o

• Cuando la variable que guarda el extremoizquierdo del arreglo es mayor que elcontenido de la variable que almacena elextremo derecho.

Arreglos • FIUAS

15 67 8 16 44

Problema

• Realice los pasos gráficos para ordenar elsiguiente arreglo, utilizando el método de lasacudida (shaker sort)

• ArregloÍndice 0 1 2 3 4

09/02/2018

26

Arreglos • FIUAS

Actividad de Aprendizaje

Diseñe e implemente el método del algoritmo de ordenación por el Método de la sacudida (shaker sort), para el TDA Arreglo.

Arreglos • FIUAS

Actividad de aprendizaje

Formación de equipos y exposiciones de temasde investigación.

Objetivo:

El alumno formara equipos de 3-4 integrantes, yseleccionará aleatoriamente un tema deinvestigación , exposición y defensa.

Temas:. Métodos de ordenación pág. 329, Cairo.

▫ 8.2 Ordenación interna

▫ 8.2.1 Ordenación por intercambio directo (burbuja)

▫ 8.2.2 Ordenación por el método de intercambio directo conseñal

▫ 8.2.3 Ordenación por el método de la sacudida (shaker sort)8.2.4 Ordenación por inserción directa

▫ 8.2.5 Ordenación por el método de inserción binaria

▫ 8.2.6 Ordenación por selección

▫ 8.2.8 Ordenación por el método de Shell

▫ 8.2.9 Ordenación por el método quicksort

09/02/2018

27

Arreglos • FIUAS

Temas:. Métodos de búsqueda pág. 391, Cairo.

• 9.2 Búsqueda interna

▫ 9.2.1 Búsqueda secuencial

▫ 9.2.2 Búsqueda binaria

Arreglos • FIUAS

09/02/2018

28

Arreglos • FIUAS

Recursividad

• Poderosa herramienta de programación comoalternativa a algoritmos iterativos.

• Soluciones elegantes a problemas difíciles deresolver de otro modo (forma iterativa)

• Un método es recursivo si contieneinvocaciones a sí mismo

• Una llamada a un método recursivo puedegenerar una o más invocaciones al mismométodo, que a su vez genera otras, …

Arreglos • FIUAS

Condiciones que debe cumplir un

método recursivo

1. Asegurar que existe una condición de salida, enla que no se producen llamadas recursivas (casobase).

2. Asegurar que se cubren todos los posibles casosentre el base y los no base.

3. Cada llamada, en el caso no base, conduce aproblemas cada vez más pequeños queterminarán en el caso base.

09/02/2018

29

Arreglos • FIUAS

Caso recursivo

• Una solución que involucra volver a utilizar lafunción original, con parámetros que se acercanmás al caso base. Los pasos que sigue el casorecursivo son los siguientes:

▫ El procedimiento se llama a sí mismo.

▫ El problema se resuelve, resolviendo el mismo problemapero de tamaño menor.

▫ La manera en la cual el tamaño del problema disminuyeasegura que el caso base eventualmente se alcanzará.

Arreglos • FIUAS

Cuando utilizar Recursividad

• En general, las soluciones recursivas son menoseficientes que las iterativas (coste mayor entiempo y memoria).

• Consejos:▫ Los algoritmos que por naturaleza son

recursivos y donde la solución iterativa escomplicada y debe manejarse explícitamenteuna pila para emular las llamadas recursivas,deben resolverse por métodos recursivos.

▫ Cuando haya una solución obvia al problemapor iteración, debe evitarse la recursividad.

09/02/2018

30

Arreglos • FIUAS

Algoritmo Iterativo

//Atributos de clase

PRIVADO ENTERO arreglo[]

PRIVADO ENTERO tamaño

//Constructor

tamaño=10

arreglo[tamaño]

//Métodos

PUBLICO SINVALOR ImpresionIterativa()

INICIO

ENTERO Indice;

DESDE(Indice=0;Indice<tamaño;Indice=Indice+1)

IMPRIMIR arreglo[Indice];

FIN_DESDE

FIN

Arreglos • FIUAS

Algoritmo Recursivo//Atributos de clase

PRIVADO ENTERO arreglo[]

PRIVADO ENTERO tamaño

//Constructortamaño=10

arreglo[tamaño]

//Métodos

PUBLICO SINVALOR ImpresionRecursiva()

INICIO

ImpresionRecursiva(0);

FIN

//Método Recursivo

PRIVADO SINVALOR ImpresionRecursiva(ENTERO Indice)

INICIO

//Caso Base

SI Indice==tamaño ENTONCES

REGRESAR;

FIN_SI

//Trabajo de izquierda a derecha

IMPRIMIR arreglo[Indice];

//Llamada recursiva

ImpresionRecursiva(Indice+1);

FIN

09/02/2018

31

Arreglos • FIUAS

Actividades Extra clase:

Desarrollar (métodos) recursivos que permitan:

▫ Determinar el mayor elemento de un arreglo.

▫ Determinar si un valor dado existe en unarreglo (1 si existe, 0 si no existe).

▫ Sustituir un valor dado por otro en un arreglo,e indicar cuantas sustituciones se realizaron.

▫ Calcular la sumar secuencial de los valores delarreglo.

Arreglos • FIUAS

Plantilla solución de Izq-Der

TipoDato NombreMetodo (parametros)

{

//definición de variables locales

//declaración del caso base

//Trabajo

//Llamada recursiva

}

09/02/2018

32

Arreglos • FIUAS

Plantilla solución de Der - Izq

TipoDato NombreMetodo (parametros)

{

//definición de variables locales

//declaración del caso base

//Llamada recursiva

//Trabajo

}

Arreglos • FIUAS

09/02/2018

33

Arreglos • FIUAS

Métodos de Búsqueda

• La búsqueda de un elemento dentro de un arreglo.

• Es una de las operaciones más importantes en elprocesamiento de la información, y permite larecuperación de datos previamente almacenados.

• Todos los algoritmos de búsqueda tienen dos finalidades:

▫ Determinar si el elemento buscado se encuentra en el conjunto en el que se busca.

▫ Si el elemento está en el conjunto, hallar la posición en la que se encuentra.

Arreglos • FIUAS

Métodos de Búsqueda

• La búsqueda se puede realizar sobreelementos:

▫ Ordenados: Ejemplos

Directorios telefónicos

Ofertas laborales

Libros en biblioteca

▫ No Ordenados: Ejemplo

Localización de una ciudad dentro de un mapa.

La búsqueda es mas fácil y ocupa menos tiempocuando los elementos(datos) están ordenados

09/02/2018

34

Arreglos • FIUAS

Clasificación de los Métodos de Búsqueda

• Internos.-Cuando todos los elementos se encuentranen la memoria principal de la computadora. Ejemplo:

▫ Arreglos

▫ Listas ligadas

▫ Arboles

• Externos.-Los elementos están en memoriasecundaria. Ejemplo:

▫ Diferentes dispositivos de almacenamiento

Cintas

Discos magnéticos

Otros.

Arreglos • FIUAS

Métodos de búsqueda Interna

• Búsqueda secuencial o lineal

• Búsqueda Binaria

• Por transformación de claves

• Arboles de búsqueda

09/02/2018

35

Arreglos • FIUAS

Búsqueda secuencial o lineal

• Consiste en revisar elemento traselemento hasta encontrar el dato buscadoo llegar al final del conjunto de datosdisponibles, lo que ocurra primero.

• Normalmente interesa conocer en queposición fue hallado el elemento que seestaba buscando, idea que se generalizapara todos los métodos.

Arreglos • FIUAS

Actividad

Desarrollar un algoritmo iterativo queimplemente la Búsqueda Secuencialen un arreglo No ordenado:

1 2 3 4 5 612 16 35 15 67 44

09/02/2018

36

Arreglos • FIUAS

Actividad

Desarrollar un algoritmo iterativo, que implemente laBúsqueda Secuencial en un arreglo ordenado:

Agregar una condición que haga más eficiente el proceso. Buscaren el arreglo mientras el elemento en la posición i sea menoral elementos buscado.

1 2 3 4 5 6

12 15 16 35 44 67

Arreglos • FIUAS

Actividad

Desarrollar un algoritmo recursivo que implemente laBúsqueda Secuencial en un arreglo ordenado:

Agregar una condición que haga más eficiente el proceso. Buscaren el arreglo mientras el elemento en la posición i sea menoral elementos buscado.

1 2 3 4 5 6

12 15 16 35 44 67

09/02/2018

37

Arreglos • FIUAS

Análisis del método de búsqueda secuencial

• En base al número de comparaciones:

• Caso favorable

▫ Si el valor se encuentra hará i comparaciones donde i es la posición dentro el arreglo.

• Caso desfavorable

▫ Si el valor no se encuentra hará N comparaciones

Arreglos • FIUAS

Búsqueda Binaria

• Se utiliza cuando el arreglo en el que queremosdeterminar la existencia o no de un elemento estáordenado.

• Idea: Consiste en dividir el intervalo de búsqueda en dospartes, comparando el elementos buscado con el que ocupala posición central en el arreglo.

• En caso de no ser iguales, se redefinen los extremos delintervalo, según el elemento central sea mayor o menorque el elemento buscado, disminuyendo de esta forma elespacio de búsqueda.

• El proceso concluye, cuando el elemento es encontrado ocuando el intervalo de búsqueda se anula.

09/02/2018

38

Arreglos • FIUAS

Actividad

Desarrollar un algoritmo iterativo queimplemente la Búsqueda Binaria enun arreglo ordenado:

1 2 3 4 5 612 16 35 15 67 44

Arreglos • FIUAS

Análisis del método

• Caso más Favorable:

▫ Una sola comparación cuando el elementobuscado es el central.

• Caso menos favorable:

▫ Log2 (n) comparaciones, cuando el elementono se encuentra en el arreglo, ya que con cadacomparación el número de elementos en loscuales se debe buscar se reduce en un factorde 2.

09/02/2018

39

Arreglos • FIUAS

Actividad Extra:

• Analizar computacionalmente la eficienciade cada método de ordenamiento yentregar un reporte del mismo.

Arreglos • FIUAS

Bibliografía

ESTRUCTURAS DE DATOS

De: OSVALDO CAIRO

Editorial: MCGRAW-HILL INTERAMERICANA

ISBN: 9701059085

Edición: 3ª

Año: 2006

No. de páginas: 467

Idioma: ESPAÑOL

País: MEXICO

09/02/2018

40

Arreglos • FIUAS

Preguntas?

FIN de Unidad