martes, 1 de abril de 2008

Arreglos





Abajo







CLASE 11: Estructura de Datos Arreglos.

Estructuras de datos estáticas

ARREGLOS

Los arreglos son estructuras de datos homogéneas, es decir, todas sus componentes son del mismo tipo. Como una estructura de datos estática su espacio debe definirse en tiempo de compilación.
¿Por qué utilizar este tipo de estructura de datos?. Supongamos la siguiente situación; se requiere tener en memoria interna y en forma simultánea los datos de los Apellidos, Nombres de 10 alumnos. Mantener todos estos datos al mismo tiempo en la memoria interna requerirá de 10 variables, pero cada una de ellas con un nombre diferente, p.e. ApeNom1, ApeNom2, ..., ApeNom10. Notamos que esta forma de notación haría muy compleja la tarea de programar, imaginemos ingresar estos datos, emitirlos, procesarlos y si en vez de 10 fueran 100 ó 1000 o más, ¡mucho más complicado!. Entonces, bajo estas situaciones, cuando contemos con una colección de datos todas del mismo tipo emplearemos los arreglos.
Podemos decir, entonces que los arreglos son colecciones o disposiciones de datos homogéneas ubicadas en la memoria interna y de manera continua la cual se le asigna un nombre único o genérico que hace referencia a esa región de memoria reservada en tiempo de compilación. Ahora bien, para poder referirnos a un elemento o componente se utiliza un subíndice, siendo la notación formada por el nombre genérico seguido del subíndice encerrado entre corchetes. Por ejemplo, si tomamos el caso anterior, el nombre genérico podría ser ApeNom y el subíndice podría ser i; por lo tanto, para indicar un elemento del arreglo lo escribiríamos como se indica a continuación ApeNom[i]. De esta manera al tener que emitir por ejemplo cada uno de los nombres de los alumnos, basta con variar el valor del subíndice para hacer referencia a cada elemento del arreglo.
Podríamos representar este concepto de manera gráfica:



ApeNom[i] en donde 1 MENOR= i MENOR= 10

El gráfico está indicando varias cosas; el nombre genérico ApeNom , la cantidad de elementos 10, cantidad de dimensiones 1, tipo del índice valores enteros, intervalo de valores del índice [1; 10], contenido de cada elemento de tipo cadena, por otro lado se nota que la variable ApeNom se encuentra ubicada en la dirección 1000 y que su tamaño es de 21 b. x 10 = 210 bytes. El área de memoria reservada para la variable ApeNom va desde 1000 a 1000 + 210 – 1, es decir de 1000 a 1209.
Si queremos averiguar el tamaño físico de un arreglo, esto se puede determinar con la función SizeOf(obj), en donde obj indicará el tipo arreglo o la variable de ese tipo arreglo. La función retorna un longint indicando la cantidad de byte de ese objeto. Si queremos calcular el espacio ocupado por la variable ApeNom, lo estableceríamos de la siguiente manera, SizeOf(ApeNom), y si ApeNom fue definido de tipo VecAlu como un arreglo con 10 componentes cada una de las cuales sería una cadena de 20 caracteres, lo estableceríamos de la siguiente manera, SizeOf(VecAlu). Por lo tanto, SizeOf(ApeNom) = SizeOf(VecAlu) = 210.
Por otro lado, si lo que queremos es averiguar cuantas componentes tiene un arreglo, esto se establecería como el tamaño físico del arreglo dividido por el tamaño de una de sus componentes, es decir, SizeOf(ApeNom) div SizeOf(ApeNom[1]) = 210 div 21 = 10.
Si utilizamos un subíndice para que haga referencia a un elemento del arreglo, estará indicando una dirección de memoria dentro de ese intervalo, siempre y cuando el valor del subíndice esté comprendido entre 1 y 10. Así, p.e. si i = 1 la dirección del primer elemento del arreglo coincide con la dirección de la variable ApeNom, es decir, dApeNom = dApenom[1], en donde la letra d indica dirección, si i = 2, la dirección de inicio del segundo elemento es 1021, en cambio si i = 3, la dirección de inicio del tercer elemento es 1042 y así sucesivamente. Por lo tanto, notamos que un incremento de 1 en el subíndice en realidad es un incremento en 21 bytes, es decir, un incremento de acuerdo al tamaño de cada componente del arreglo.
¿Qué sucederá si el subíndice adoptara un valor inferior o superior a 1 ó 10 respectivamente? La respuesta es obvia, estaríamos invadiendo una zona de memoria desconocida, por lo tanto, los efectos que se podrían producir serían impredecibles, algunos de los cuales podrían ser, cambiar los valores a otras variables que estuvieran contiguas a esta región de memoria, que aparecieran caracteres extraños en la pantalla, que se colgara la ejecución del programa, entre otros. Será responsabilidad del programador llevar el control del valor del subíndice. Turbo Pascal brinda de una directiva al compilador {$R+} y {$R-} que permite modificar para que el compilador pueda hacer un control o no, de los valores que tomen las variables y en el caso de los arreglos también el subíndice, para que genere un error cuando sus valores escapen fuera de su intervalo definidos en tiempo de compilación. Bajo estas situaciones se detendrá la ejecución del programa, si la directiva está indicada con signo más. En cambio si la directiva está indicada con signo menos se desactiva esta característica y en caso que una variable o subíndice adopten valores fuera de su intervalo no se generará ninguna advertencia por parte del compilador y la ejecución del programa continuará como si nada hubiese ocurrido, en estos casos se complementará el valor excedido para que se genere un valor dentro del intervalo aceptado por la declaración del tipo de la variable. Una excepción a esta directiva, es cuando en el código del programa asignamos un valor fuera de los límites que puede soportar una variable, en estos casos, al momento de compilar el programa, el mismo compilador informará que el valor que queremos asignar está fuera de los límites. Por ejemplo, si x es una variable de tipo byte y hacemos x <-- 258 al compilar el programa generará un mensaje de error. En el caso de los índices de un arreglo, si tomamos el ejemplo anterior que es de 1 a 10, si el subíndice adoptara un valor de 15 ó 130 ó 255 no se complementaría ya que el compilador lo determinaría como de tipo byte, pero si tomara un valor negativo o mayor a 255 en estos casos sí lo complementaría, pudiendo generar un valor entre 0 y 255, esto en la situación en que le asignemos estos posibles valores a la variable que será empleada como índice, p.e. si asignamos a la variable x <-- 255 y hacemos que la variable i <-- x + 3, si la variable i estuviera definida como de tipo byte el valor que se asignaría no sería 258 sino que se complementaría y pasaría a contener 2, es decir, el resultado de 258 – 256, luego si hacemos ApeNom[i] se estaría refiriendo al segundo elemento del arreglo, es decir a Ríos, María. En cambio, si lo que quisiéramos realizar fuera ApeNom[i + 3], en este caso el resultado sería 258, no se complementa y por lo tanto, se estaría haciendo referencia al elemento 258 y como notamos, eso está fuera de la región de memoria de ApeNom, en conclusión, se está invadiendo una región de memoria desconocida y como consecuencia se podría tener los problemas anteriormente indicados. La directiva al compilador {$R±} realiza la verificación de intervalo de valores de los objetos, el símbolo R se refiere a range, y el error informado en tiempo de ejecución es el Error#201 Range check error, Verificación de intervalo. El valor por defecto es {$R-}, vale decir, está desactivada. En el estado {$R+} los arreglos y las expresiones de cadena indexadas cad[i], son verificadas dentro de los límites definidos, y todas las asignaciones a variables escalares y de intervalo son también verificadas dentro de los límites definidos. Si la verificación de intervalo falla, la ejecución del programa finaliza y se muestra un mensaje de error. Esta opción se debe utilizar en tiempo de depuración del programa y desactivarla cuando el programa haya sido depurado, de esta manera el programa correrá más rápidamente. Si lo que queremos es controlar en todo el ámbito del programa, entonces la directiva debe ubicarse antes de los módulos, un lugar apropiado sería incluso antes de la cabecera del programa, es decir, antes de la palabra reservada program, o bien inmediatamente a continuación de esta cabecera, como se muestra en los siguientes ejemplos:

{$R+}
program VerificarIntervalos;
...


program VerificarIntervalos;
{$R+}
...

Otros tipos de advertencias que se podrían generar al compilar un programa que utilice arreglos, son los casos en que nos quedemos sin memoria suficiente; informados por el compilador Turbo Pascal serían los siguientes:
Error#22 Structure too large, Estructura muy grande. Se produce al definir un arreglo en el cual la memoria se ve saturada por el espacio a reservar, es decir, cantidad de elementos por la cantidad de bytes de cada componente, es mayor a 64 Kbytes, que es el espacio máximo para las variables globales, p.e. al definir el siguiente tipo de dato v = array[1..3000] of str22; se generará dicho error.
Error#96 Too many variables, Demasiadas variables. Se producirá el definir varias estructuras de datos en la cual ninguna de ellas supera el máximo permitido, pero sí la sumatoria de ellas, p.e. v = array[1..2000] of str22; w = array[1..1000] of str22; lo mismo ocurriría al declarar variables espacios en cada uno de los módulos.

Conclusión: al momento de utilizar arreglos, se deben tomar ciertas medidas preventivas. La memoria interna puede verse saturada, el subíndice puede tomar valores fuera del intervalo de valores definidos. Por estos motivos se recomienda realizar una estimación necesaria para la cantidad de memoria a utilizar y asegurarse los valores que adopten los índices, ya que, la responsabilidad será exclusivamente del programador.


Arreglos en Turbo Pascal

Para poder emplear arreglos primero debemos definir un identificador de tipo arreglo. En el mismo se indicará la cantidad de dimensiones y por cada dimensión la cantidad de elementos o componentes que tendrá, por último se indicará el tipo de esas componentes.
A continuación se muestra como declarar un tipo arreglo en Turbo Pascal:

type
Arreglo = array[dimensión1, dimensión2, ... ] of tipo;

En el ejemplo anterior vemos que la palabra reservada array establece el tipo arreglo, dimensión1 establece la primer dimensión del arreglo, dimensión2 la segunda dimensión y así sucesivamente, Turbo Pascal no impone límites en la cantidad de dimensiones, el límite solamente estará impuesto por la cantidad de memoria interna disponible y esto es solo para el segmento de datos cuyo tamaño máximo es de 64Kb. Cada una de las dimensiones de un arreglo establecerá la cantidad de componentes a través de un intervalo valIni..valFin en donde, valIni indica el valor inicial y valFin el valor final, es decir, el intervalo cerrado de valores que podrá contener el subíndice, mientras que tipo establece el tipo de valores de cada componente del arreglo.
Tratándose si las variables de tipo arreglo se declararon de ámbito global entonces ocupará el segmento de datos y su tamaño máximo es de 64 Kbytes. Pero si la variable fue declarada de ámbito local, es decir dentro de un módulo, la región de memoria es el segmento del stack o pila y el tamaño de la memoria de esta región por defecto Turbo Pascal lo establece en 16384 bytes, aunque su valor máximo se podría llevar a los 64 Kbytes, el resultado sería si el tamaño fuera el valor por defecto sucedería un error en tiempo de ejecución por desbordamiento de la pila, es decir supero la capacidad de almacenamiento. Error 202.
De este ejemplo, se puede inferir que una variable de tipo arreglo insume mucha memoria.
Los valores valIni y valFin deben ser de tipo ordinal, vale decir, que pueden ser los enteros, -pero no el tipo longint o por intervalo de tipo longint-, char, boolean, o definidos por el usuario. Solo se podrán consignar valores constantes tanto para valIni como para valFin. Cada dimensión podrá ser de diferentes tipos ordinales, por ejemplo, si un arreglo fue definido con 2 dimensiones, la primer dimensión podría ser valores enteros y la segunda valores char, como se muestra a continuación:

ArrReal = array[1..10, ‘A’..’E’] of real;

el tipo definido por el usuario ArrReal es igual al tipo arreglo con 2 dimensiones, siendo la primer dimensión establecida en el intervalo [1; 10], lo que establece que el subíndice de la primer dimensión sólo podrá tomar valores entre 1 y 10 y la segunda dimensión establecida en el intervalo [‘A’; ‘E’], lo que establece que el subíndice de la segunda dimensión sólo podrá tomar valores entre ‘A’ y ‘E’. La cantidad de elementos del arreglo ArrReal está establecida en 10 x 5 = 50 elementos ocupando un espacio en la memoria interna cuando se declaren variables de ese tipo de 50 x 6 bytes = 300 bytes.
Los arreglos con una dimensión se denominan vectores y los arreglos con 2 dimensiones se los denominan matrices. A los elementos de un arreglo se los puede acceder en forma secuencial o bien al azar. La manera de recorrer los elementos secuencialmente es con un ciclo que lo recorra desde su valor inicial hasta su valor final o bien dentro de estos valores.
Las componentes de un arreglo se ubican en la memoria en forma lineal, en un arreglo unidireccional la correspondencia es directa, pero ¿cómo será en el caso de un arreglo bidireccional o con más dimensiones?. Tomemos el caso de un arreglo de 2 dimensiones de m x n, es decir, m filas y n columnas, la disposición se realizará por filas o bien por columnas, esto lo determinará el propio lenguaje a utilizar. En el caso del Turbo Pascal la disposición de los elementos, la convención elegida es por filas, esto es, primero se ubican en la memoria los primeros n elementos de la primer fila, luego los segundos n elementos de la segunda fila y así sucesivamente hasta completar los últimos n elementos de la fila m. Conociendo esta disposición de los elementos, es fácil poder determinar el lugar de almacenamiento en forma lineal de un elemento[i, j] aplicando la siguiente expresión:







(i - 1) * n + j (1)









con: (1 MENOR= i MENOR= m) ^ (1 MANOR= j MENOR= n)

Por ejemplo, si m = 4 y n = 5, encontrar la posición del elemento[2, 4], aplicando la expresión (1), reemplazando i por 2 y j por 4 obtenemos 9, por lo tanto, el elemento[2, 4] linealizado se localiza en la posición ordinal 9 a partir de la dirección inicial del arreglo en la memoria interna.
En el ejemplo que se detalla a continuación notamos que el elemento[2, 4] = 22 y en la linealización dada a continuación vemos que en la posición 9 el valor es 22.












Las matrices pueden ser rectangulares o cuadradas. Una matriz rectangular es aquella en la que la cantidad de filas es distinta a la cantidad de columnas es decir, Anxm, en donde, n ≠ m y una matriz cuadrada es aquella en la que la cantidad de filas es igual a la cantidad de columnas, es decir, Anxm = Anxn ya que, n = m.
Una matriz cuadrada presenta 2 diagonales, una diagonal principal y una diagonal secundaria. Los elementos que se encuentran en la diagonal principal tienen como condición i = j y los elementos que se encuentran en la diagonal secundaria tienen como condición i + j = n + 1. (II)
Asignar unos a los elementos de la diagonal principal:

i <-- 1 ↑ n A[i, i] <-- 1 Asignar 1’s a los elementos de la diagonal secundaria: i <-- 1 ↑ n A[i, n + 1 - i] <-- 1 n + 1 – i se obtiene de despejar j en la expresión (II)

Los elementos de un arreglo se pueden utilizar de la misma manera que las variables simples para, asignarles un valor en una asignación interna o como una asignación externa de entrada o de salida, comparar su valor, utilizarlas en una expresión, etc.

Ejemplo:












Ejemplos:

const
MIN = 1;
MAX = 10;
ULT_MES = 12;

type
str = string[20];
IntVal = 1..ULT_MES;
ArrUno = array[MIN..MAX] of word;
ArrDos = array[1..5,’1’..’5’] of str20;
Arr1 = array[-5..5] of longint;
Arr2 = array[IntVal] of char;

En todos los ejemplos precedentes el tipo de cada elemento es un tipo simple de dato, pero existe la posibilidad que esos tipos sean de un tipo estructurado de datos. Por lo tanto el tipo de cada componente también podría ser como se indica a continuación:

type
str20 = string[20];
Fecha = record
aa : word;
mm,
dd : byte
end;

VCuotas = array[1..12] of real;
RegAlu = record
NroLeg : longint;
ApeNom,
Domic,
Local : str20;
FecNac : Fecha;
EstCiv : char;
Trabaja : boolean;
Cuotas : VCuotas
end;

VecRegAlu = array[1..100] of RegAlu;
VecVec = array[1..10] of array[1..10] of RegAlu;
CjtoByte = set of byte;
VecCjto = array[1..50] of CjtoByte;

var
VapeNom : VecRegAlu;

Al igual que los arreglos con componentes simples, también podremos referirnos a elementos de una estructura arreglo de registro para asignar valores de manera interna o externa de entrada o salida, comparar, emplear dentro de expresiones, etc.

Ejemplo:

VapeNom[i].NroLeg <-- 1234 VapeNom[i].FecNac.mm > mes
x <-- x + VapeNom[i].Cuotas[j]
Pasaje de parámetros de tipo arreglos

De la misma manera que las variables simples, o archivos, o registros, o conjuntos, los arreglos también pueden ser pasados como parámetros a los módulos. Cabe aclarar que los arreglos pueden ser pasados por valor o por referencia, en el primer caso se haría una copia del arreglo en el segmento de la pila, lo que implica que si el arreglo es muy grande podríamos saturar ese espacio con la consecuente situación de error por desbordamiento de la pila, siendo el Error #202 Stack overflow error, Error por desbordamiento de la Pila. Este es un error fatal y ocasionará la terminación de la ejecución del programa inmediatamente. En el segundo caso si el arreglo es pasado por referencia solo se pasa un puntero al arreglo. Por lo tanto, lo aconsejable sería pasar los arreglos siempre por referencia.
A continuación presentamos diversas variantes para pasar como parámetro la variable VapeNom, por razones de conveniencia en la escritura, se pasará el arreglo por valor.

SizeOf(RegAlu) = 145 y SizeOf(VapeNom) = 14500











La asignación entre vectores es posible siempre y cuando los arreglos sean del mismo tipo. Si ArrUno es un tipo arreglo y Vec1 y Vec2 son ambos de tipo ArrUno, entonces la asignación entre estos dos arreglos es válida, como se indica a continuación: Vec2 <-- Vec1 Esto mismo sería equivalente a realizar:











Operaciones con arreglos








Búsqueda secuencial o lineal

La búsqueda secuencial en un arreglo consiste en buscar un valor en el arreglo recorriendo los elementos adyacentes, comenzando desde una posición inicial. El proceso finaliza cuando se encuentre una posición en el cual su valor es el buscado o bien cuando se haya alcanzado al último elemento y no apareció el valor buscado. Por lo tanto habrá dos situaciones de salida, una es cuando se encontró el valor y la otra cuando se alcanzó al último elemento en el arreglo sin haberse encontrado el valor. De esto se desprende que si el valor estuviera en la primera posición, un solo acceso al arreglo sería suficiente y en el peor de los casos tendremos que acceder hasta la última posición, así, si un arreglo tuviera n componentes, la cantidad de accesos promedia sería de n / 2.
A continuación se presenta el siguiente módulo en el cual se buscará el valor de una clave en un arreglo, retornando el módulo la posición encontrada si el valor clave se encontró en el arreglo, caso contrario un valor cero si no se encontró.











El método de búsqueda secuencial sirve tanto si el arreglo está desordenado como si se encontrara ordenado. No obstante en los casos en que el arreglo estuviera ordenado debería optimizarse el algoritmo para los casos en que habiendo llegado a una posición en el arreglo y siendo que su contenido es mayor al valor buscado, bajo esta situación se debería abandonar la búsqueda, ya que si no se lo encontró hasta esa posición, tampoco se lo encontrará más adelante, por ser todos esos valores mayores al buscado, sabiendo que el arreglo se encontraba ordenado en forma ascendente.


A continuación se presenta el módulo de búsqueda secuencial optimizado.











El módulo BusLinOpt mejora el rendimiento de la búsqueda con respecto al módulo BusLin, ya que en el segundo caso si se encontró un valor mayor al buscado se abandona la búsqueda de los siguientes elementos restantes.

Búsqueda binaria



Pero, ¿será este el mejor método de búsqueda cuando el arreglo se encuentre ordenado, por el valor de la clave a buscar?. La respuesta es ¡NO!. Una mejor manera de buscar un valor en un arreglo ordenado será aquel que obtiene un punto medio entre sus extremos y es comparado por el valor a buscar, si es, entonces se encontró y se abandona la búsqueda, en cambio si no lo es, caben dos posibilidades, que haya que seguir buscando en una primera mitad o bien en la segunda mitad, en ambos casos el arreglo queda reducido para continuar la búsqueda en la mitad. El método que realiza estas acciones se conoce como método de búsqueda binario o dicotómica. Este método ya fue presentado en el tema de buscar un elemento en un archivo ordenado. Por lo tanto, diremos que conservará básicamente la estructura lógica vista, la única diferencia notable está en que no hace falta bajar el dato ya que se encuentra en la propia memoria interna. A continuación se presenta el módulo de búsqueda binaria o dicotómica en arreglos.











El método comienza conociendo las posiciones extremas del arreglo, pri y ult, se obtiene el punto medio med y se compara si el valor de esta posición es el valor clave a buscar, si es entonces se abandona el proceso, sino caben 2 alternativas, es menor, entonces se modifica el extremo inferior pri por el de la posición med + 1 caso contrario se modifica el extremo superior ult por el de la posición med – 1, luego de lo cual se obtiene una nueva posición med. Si después de reiteradas búsquedas no aparece el valor el algoritmo finaliza cuando el valor extremo inferior pri se vuelva mayor al valor del extremo superior ult.
Como vemos por cada comparación realizada se reduce a la mitad el conjunto de valores a consultar, por lo tanto, el análisis será de:


n / 2, n / 4, n / 8; es decir, n / 21, n / 22, n / 23



El proceso finalizará cuando el tamaño se haga MENOR 1. Por lo tanto, si k es el número mayor de comparaciones n / 2k MENOR 1 establecerá la finalización.

Si tomamos un conjunto de 50000 elementos, la cantidad máxima de comparaciones estará en el orden de log2 n = log2 50000 ~16. Por lo tanto, con k = 16 se abandonará la búsqueda si aún no se encontró el valor de la clave en el arreglo.

Ejemplo:

Se tiene el siguiente arreglo Arr con los siguientes elementos:








y se requiere buscar el valor 35, los pasos a realizar establecerán los siguientes valores para los extremos y los puntos medios:

pri <-- 1, ult <-- 15, med <-- 8, como el valor de la pos. 8 es 56 y no es igual a 35 la comparación siguiente 56 MENOR 35 es falsa se cambia el extremo superior ult <-- med – 1 y med <-- 4, como el valor de la pos. 4 es 32 y no es igual a 35 la comparación siguiente 32 MENOR 35 es verdadera se cambia el extremo inferior pri <-- med + 1 y med <-- 6, notamos que 43 MENOR 35 es falso se modifica ult <-- med – 1 y med <-- 5, por último vemos que el valor de la pos. 5 35 es igual al valor a buscar que es 35, por lo tanto hemos encontrado el valor clave. Tambien notamos que los extremos en este último caso se hicieron iguales y justamente en esa posición se encontraba el valor a buscar, este sería la última comparación a realizar si el valor no se hubiera encontrado, debido a que en el próximo paso el extremo inferior se volvería mayor al extremo superior, indicando que no debemos seguir procesando la búsqueda.








Ordenamiento de arreglos

Como fue indicado en párrafos previos un arreglo podrá encontrarse ordenado o no. Si no se encuentra ordenado, a efectos de mejorar el rendimiento de un proceso o por motivos de mostrar los datos ordenados bajo un determinado criterio, hacen de la necesidad de ordenar los arreglos. Existen varios métodos para ordenar arreglos, pero básicamente podríamos dividirlos en 2 clases; los métodos cuadráticos o directos (N2) y los métodos avanzados o logarítmicos o indirectos (N x log2 N).






En el primer grupo encontramos varios métodos, a saber; burbuja (bubble sort), selección, inserción. En el segundo grupo encontramos también varios métodos, a saber; shell, quick sort, ordenación por mezcla (merge).






Los métodos directos son fáciles de programar pero de ejecución más lenta. En cambio, los métodos indirectos son más complejos en su programación pero más eficientes para su ejecución ya que corren más rápidamente que los directos. No obstante, con pocos elementos en un arreglo, ambos métodos directos o indirectos funcionan muy parejos.






A continuación se presentará el método de ordenación por burbujeo optimizado. Este método compara elementos adyacentes, es decir, v[i] y v[i+1], cada vez que un elemento de una posición menor sea mayor al adyacente inmediato siguiente se debe realizar un intercambio, por lo tanto, al avanzar desde las posiciones inferiores hacia las posiciones superiores del arreglo, se irá arrastrando el valor mayor hasta alcanzar la última posición, y algunos de los valores menores se irán corriendo hacia las posiciones inferiores. La cantidad de pasadas estará en función de la cantidad de elementos de un arreglo. En el caso de un arreglo con n cantidad de elementos la cantidad de pasadas máximas será de n – 1. Pero este método por ser optimizado tiene la característica de que si en una pasada no se realizó ningún intercambio podemos asegurar que el arreglo ya quedó ordenado y por lo tanto abandonar las restantes pasadas, consiguiendo un ahorro en el tiempo de ejecución. Por cada pasada debemos recorrer cada elemento desde 1 hasta a n – k, en donde, k en la primer pasada vale 1, en la segunda pasada vale 2 y así sucesivamente. Al termino de cada pasada se habrá acomodado el elemento más pesado en la última posición de cada pasada. Seguidamente se presenta el algoritmo de ordenación por burbujeo optimizado.





Los métodos directos de ordenación se miden en cuanto a la cantidad de preguntas que deben de realizarse y está en función del valor N. En el caso de la ordenación por burbuja optimizado, notamos que en la primera pasada la cantidad de comparaciones es de n – 1, en la segunda pasada de n-2, n-3 en la tercera pasada, hasta llegar a 1 comparación en la última pasada, por lo tanto:







1 + 2 + 3 + ... + (n - 3) + (n - 2) + (n - 1) = n · (n - 1) / 2 = (n2 – n) / 2




El mejor de los casos es que el arreglo se encuentre ordenado, en esta situación solo hará falta una pasada, en cambio, el peor de los casos será que el arreglo se encuentre ordenado invertido, es decir, si queremos ordenarlo en forma ascendente y se encuentra ordenado en forma descendente.
Los métodos vistos en párrafos previos de búsqueda secuencial, búsqueda secuencial optimizada, búsqueda binaria y ordenación por burbujeo, han sido desarrollados para arreglos en la que las componentes son de un valor simple de dato. No obstante, estos mismos métodos con algunas ligeras modificaciones pueden ser aplicados para arreglos cuyas componentes sean de tipo estructurado, lo más común de tipo registro. Bajo esta situación al comparar un elemento con otro modificamos la notación Arr[i] por Arr[i].cmp en donde, cmp es el nombre de una de las componentes del registro, es decir, el nombre de un campo.






Arreglos paralelos

Una alternativa a los arreglos de registro son los arreglos paralelos. Se denominan arreglos paralelos debido a que las componentes de un arreglo se corresponden con las componentes de los otros arreglos, es decir, Arr1[i] se corresponde con Arr2[i], ... Arrn[i]. Los procesos analizados anteriormente, podrían aplicarse tanto a los arreglos de registros como a los arreglos paralelos. Por ejemplo, si estamos ordenando el arreglo, en el caso de arreglos de registro al intercambiar las componentes Arr[i] y Arr[i+1] se intercambian todos los campos de esas componentes, es decir se mueve el registro completo de una y de la otra componente. En el caso de los arreglos paralelos se deben intercambiar todas las posiciones correspondientes de cada uno de ellos, vale decir, Arr1[i] se intercambia con Arr1[i+1], Arr2[i] se intercambia con Arr2[i+1], ..., Arrn[i] se intercambia con Arrn[i+1].

Desplazamiento de elementos en un arreglo

Un arreglo puede generarse incorporando valores en forma ordenada en el mismo instante en que ocurre el evento. Esta acción implicará realizar un corrimiento de un lugar, de aquellos elementos que ya estuvieran en el arreglo para abrir un lugar al nuevo elemento que se insertará en la posición apropiada para mantener el orden, ya sea ascendente o descendente. La siguiente figura muestra un ejemplo de insertar el valor 43 en un arreglo que ya contiene los siguientes valores:







Según el modelo presentado el valor 43 deberá ser insertado entre los valores 41 y 49. Para poder llevar a cabo esto, los valores mayores a 41 deberán ser desplazados un lugar hacia la derecha. Al hacerlo debemos tener cuidado de no perder ningún valor en el arreglo, está claro que si moviéramos el valor 49 a la posición siguiente perderíamos el valor 52, por lo tanto el desplazamiento debería realizarse desde el fondo hacia arriba o en esta situación desde la derecha hacia la izquierda, esto es, el valor 94 se movería a la posición 11, luego el valor 87 se movería a la posición 10, y así sucesivamente hasta alcanzar el valor 49 que se movería a la posición 8. Por último insertaríamos el valor 43 en la posición 7. Este proceso debe contemplar todos los casos posibles, es decir, al insertar el primer elemento, al insertar el último elemento que completa el arreglo, al insertar al inicio, al insertar al final o en cualquier otra ubicación, incluso con valores que puedan repetirse, insertar ya dado un juego de valores que se ingresarán ordenados ascendente o descendentemente.
El proceso deberá contemplar entonces todos estos casos. A continuación se presenta el algoritmo correspondiente.











Algoritmo en pseudocódigo




Proc InsertaEnOrden(v: tvec; elem, card: byte) {




(card > 1) ^ (elem MENOR v[card - 1]) {




v[card] <-- v[card - 1]




card <-- card - 1




}




v[k] <-- elem




}




Bloque Principal




{




Emitir('Ingrese una cantidad')




Ingresar(cant)




card <-- 0




i <-- 1 ↑ cant {




Emitir('Ingrese item')




Ingresar(item)




Si not BusBin(v, item, card) {




card <-- card + 1




InsertaEnOrden(v, item, card)




}




}




}












Anterior: Conjuntos




Siguiente: Punteros y Estructuras dinámicas lineales: Pilas, Colas y Listas





Arriba

2 comentarios:

Karla dijo...

hola d verdad me sirvio mucho la informacion, gracias!!

Solde9 dijo...

Buena Info!