ARREGLOS

Definición:
Es una colección de datos del mismo tipo. Sirve para manejar un número “n” de elementos en común, ya sea de tipos definidos por el Lenguaje,(“int”,”float”,”String”,etc…) así como aquellos definidos por el programador.

Clasificación:

Arreglos unidimensionales

Es un tipo de datos estructurado que está formado de una colección finita y ordenada de datos del mismo tipo. Es la estructura natural para modelar listas de elementos iguales. Están formados por un conjunto de elementos de un mismo tipo de datos que se almacenan bajo un mismo nombre, y se diferencian por la posición que tiene cada elemento dentro del arreglo de datos. Al declarar un arreglo, se debe inicializar sus elementos antes de utilizarlos. Para declarar un arreglo tiene que indicar su tipo, un nombre único y la cantidad de elementos que va a contener.

Arreglos multidimensionales

Es un tipo de dato estructurado, que está compuesto por dimensiones. Para hacer referencia a cada componente del arreglo es necesario utilizar n índices, uno para cada dimensión. El término dimensión representa el número de índices utilizados para referirse a un elemento particular en el arreglo. Los arreglos de más de una dimensión se llaman arreglos multidimensionales.

Arreglos con múltiple subíndices

Es la representación de tablas de valores, consistiendo de información arreglada en renglones y columnas. Para identificar un elemento particular de la tabla, deberemos de especificar dos subíndices; el primero identifica el renglón del elemento y el segundo identifica la columna del elemento. A los arreglos que requieren dos subíndices para identificar un elemento en particular se conocen como arreglo de doble subíndice. Note que los arreglos de múltiples subíndices pueden tener más de dos subíndices. El estándar ANSI indica que un sistema ANSI C debe soportar por lo menos 12 subíndices de arreglo.

Operaciones Básicas:

Las operaciones en arreglos pueden clasificarse de la siguiente forma:

• Lectura: este proceso consiste en leer un dato de un arreglo y asignar un valor a cada uno de sus componentes
• Escritura: Consiste en asignarle un valor a cada elemento del arreglo.
• Asignación: No es posible asignar directamente un valor a todo el arreglo
• Actualización: Dentro de esta operación se encuentran las operaciones de eliminar, insertar y modificar datos. Para realizar este tipo de operaciones se debe tomar en cuenta si el arreglo está o no ordenado.
• Ordenación.
• Búsqueda.
• Insertar.
• Borrar.
• Modificar.

Método de Ordenamiento:

Selección Directa

Este método consiste en seleccionar el elemento más pequeño de nuestra lista para colocarlo al inicio y así excluirlo de la lista.

Para ahorrar espacio, siempre que vayamos a colocar un elemento en su posición correcta lo intercambiaremos por aquel que la esté ocupando en ese momento.

El algoritmo de selección directa es el siguiente:

i <- 1

mientras i<= N haz

        min <-i

        j <- i + 1

        mientras j <= N haz

                si arreglo[j] < [min] entonces

                        min <-j

                j <- j + 1

        intercambia(arreglo[min],arreglo[i])

        i <- i +1

Ordenación por Burbuja

Es el método de ordenación más utilizado por su fácil comprensión y programación, pero es importante señalar que es el más ineficiente de todos los métodos .

Este método consiste en llevar los elementos menores a la izquierda del arreglo ó los mayores a la derecha del mismo. La idea básica del algoritmo es comparar pares de elementos adyacentes e intercambiarlos entre sí hasta que todos se encuentren ordenados.

i <- 1

mientras i < N haz

        j <- N

        mientras j > i haz

                si arreglo[j] < arreglo[j-1] entonces

                        intercambia(arreglo[j],arreglo[j-1])

                j < j - 1

        i <- i +1

Ordenación por Mezcla

Este algoritmo consiste en partir el arreglo por la mitad, ordenar la mitad izquierda, ordenar la mitad derecha y mezclar las dos mitades ordenadas en un array ordenado. Este último paso consiste en ir comparando pares sucesivos de elementos (uno de cada mitad) y poniendo el valor más pequeño en el siguiente hueco.

procedimiento mezclar(dat,izqp,izqu,derp,deru)

inicio

        izqa <- izqp

        dera <- derp

        ind <- izqp

        mientras (izqa <= izqu) y (dera <= deru) haz

                si arreglo[izqa] < dat[dera] entonces

                        temporal[ind] <- arreglo[izqa]

                        izqa <- izqa + 1

                en caso contrario

                        temporal[ind] <- arreglo[dera]

                        dera <- dera + 1

                ind <- ind +1

        mientras izqa <= izqu haz

                temporal[ind] <- arreglo[izqa]

                izqa <- izqa + 1

                ind <- ind +1

        mientras dera <= deru haz

                temporal[ind] <=dat[dera]

                dera <- dera + 1

                ind <- ind + 1

        para ind <- izqp hasta deru haz

                arreglo[ind] <- temporal[ind]

fin

Método de Búsqueda:

Búsqueda Secuencial

A este método tambien se le conoce como búsqueda lineal y consiste en empezar al inicio del conjunto de elementos , e ir a travez de ellos hasta encontrar el elemento indicado ó hasta llegar al final de arreglo.

Este es el método de búsqueda más lento, pero si nuestro arreglo se encuentra completamente desordenado es el único que nos podrá ayudar a encontrar el dato que buscamos.

ind <- 1

encontrado <- falso

mientras no encontrado y ind < N haz

si arreglo[ind] = valor_buscado entonces

encontrado <- verdadero

en caso contrario

ind <- ind +1

Búsqueda Binaria

Las condiciones que debe cumplir el arreglo para poder usar búsqueda binaria son que el arreglo este ordenado y que se conozca el numero de elementos.

Este método consiste en lo siguiente: comparar el elemento buscado con el elemento situado en la mitad del arreglo, si tenemos suerte y los dos valores coinciden, en ese momento la búsqueda termina. Pero como existe un alto porcentaje de que esto no ocurra, repetiremos los pasos anteriores en la mitad inferior del arreglo si el elemento que buscamos resulto menor que el de la mitad del arreglo, o en la mitad superior si el elemento buscado fue mayor.

La búsqueda termina cuando encontramos el elemento o cuando el tamaño del arreglo a examinar sea cero.

encontrado <- falso

primero <- 1

ultimo <- N

mientras primero <= ultimo y no encontrado haz

mitad <- (primero + ultimo)/2

si arreglo[mitad] = valor_buscado entonces

encntrado <- verdadero

en caso contrario

si arreglo[mitad] > valor_buscado entonces

ultimo <- mitad - 1

en caso contrario

primero <- mitad + 1

Búsqueda por Hash

La idea principal de este método consiste en aplicar una función que traduce el valor del elemento buscado en un rango de direcciones relativas. Una desventaja importante de este método es que puede ocasionar colisiones.

funcion hash (valor_buscado)

inicio

hash <- valor_buscado mod numero_primo

fin

inicio <- hash (valor)

il <- inicio

encontrado <- falso

repite

si arreglo[il] = valor entonces

encontrado <- verdadero

en caso contrario

il <- (il +1) mod N

hasta encontrado o il = inicio