Arreglos - Recorridos

Arreglos: Recorridos

Los arreglos, no son otra cosa mas que matrices dentro de los lenguajes de programación. Se utilizan para almacenar, organizar y manipular grandes cantidades de información, por grandes nos referimos a cantidades para las cuales no resulta muy conveniente o práctico utilizar variables separadas.

Una de las operaciones más importantes en los arreglos y que puede llegar a resultar algo confusa, son los recorridos. Antes de entrar a hablar sobre recorridos, recordemos un poco sobre los arreglos. 

Los arreglos, al igual que las matrices, son estructuras que contienen información en cada "casilla" o posición del arreglo. Para hacer referencia a una "casilla" o posición especifica del arreglo, se hacen uso de los índices, que sirven para identificar la fila y columna a la que nos estamos refiriendo en caso de los arreglos bidimensionales, en el caso de los arreglos unidimensionales se necesita un sólo numero para hacer referencia a algún elemento del arreglo. 

Como podemos observar, en C# es muy sencillo hacer referencia a una celda específica del arreglo. Ahora bien, ya que vimos como se hace eso, podemos hablar de recorridos. El mas común y sencillo se basa en dos estructuras de iteración, como puede ser el for, while o do-while, en este caso usaremos el for. Se dice que es el recorrido mas común porque es sencillo, empieza en la posición [0,0] del arreglo, recorre toda la primera fila hasta quedar en la posición final [5,0], después repite la operación pero ahora comenzando en la posición [0,1] para terminar en la posición [5,1]; se repite el mismo procedimiento para las otras 4 filas. 

El algoritmo para este procedimiento es bastante sencillo, apenas unas cuantas lineas;

Para i = 0 hasta i = n - 1 hacer

   Para j = 0 hasta j = n - 1 hacer

       Escribir "["+j+","+i+"]"

   Fin Para

Fin Para

Donde n es la dimensión del arreglo, por ejemplo para un arreglo de 5x5, n = 5.

Y esto en código de C# es aún más sencillo. Por ejemplo, para llenar un arreglo con números en orden, es decir, 1,2,3,4... n*n, podría implementarse el siguiente código.

public int[,] numOrden(int[,] arreglo, int n)

{

int c = 1;

for(int i = 0; i < n; i++)

   for(int j = 0; j < n; j++)

   {

      arreglo[ j , i ] = c;

      c = c + 1;

   } 

return arreglo;

}

Imaginando que n = 3, este método lo que hará, en un principio será situarse en la posición [j,i] del arreglo, en un inicio tanto i como j valen 0, por lo tanto estariamos situados en [0,0] y es ahí donde se almacena el valor de c (1 al principio). Después, el for mas interno hace la comparación j < 3, como j vale 0, el ciclo se repite, la próxima vez que se ejecute la comparación, j valdrá 1, la siguiente 2 y por último 3 < 3, como eso es falso, entonces el for interno no se ejecuta de nuevo, ahora el for externo es el que entra en ejecución y hace la comparación i < 3, como i  en un principio vale 0, todo el proceso se repite nuevamente. 

En otras palabras, el for interno se ejecuta 3 veces por sí mismo, y el for externo hace que éste se ejecute 3 veces, por lo tanto las repeticiones del for interno por las repeticiones del for externo nos dan un total de 9 repeticiones, es decir, habrá visitado cada lugar del arreglo.

Éste mismo código puede utilizarse para recorrer el arreglo columna por columna en vez de fila por fila, solamente tendria que cambiar arreglo[j,i] por arreglo[i,j]. De la misma forma podría usarse para recorrer el arreglo desde el final ( [n-1,n-1] ) hasta el principio, todo depende de las necesidades del programador así como de su imaginación. 

Recorrido en espiral

Arreglo 3x3

Uno de los sencillos recorridos que se pueden hacer sobre un arreglo, es el recorrido de espiral. A simple vista, y sobre todo en arreglos grandes, puede parecer un procedimiento difícil de programar, pero nada mas lejos de la realidad, solo hay que encontrar patrones.

Primero que nada, si nos detenemos a observar con atención el recorrido, podemos darnos cuenta que independientemente de las dimensiones del arreglo, siempre y cuando sea cuadrado, los primeros 3 movimientos (derecha, abajo, izquierda) son de la misma longitud, es decir, si en el arreglo de la imagen estamos posicionados en [0,0] para llegar al final de la fila hay que movernos 2 unidades ( [0,0] → [2,0] ), desde el final de la fila, hasta el final de la columna también son 2 unidades ( [2,0] → [2,2] ), desde el final de la fila hasta el principio son otras 2 unidades ( [2,2] → [0,2] ) hasta ahí, esos 3 movimientos son iguales. Como decíamos al principio, esos 3 movimientos son iguales en todos los arreglos, en términos generales, si el arreglo es de 3x3 entonces n = 3, y podemos decir que los 3 primeros movimientos son de n - 1 unidades.

Habiendo definido esto, los desplazamientos a partir de aquí están dados por un patrón. El siguiente movimiento es hacia arriba, pero esta vez el movimiento no será de n - 1 unidades, a partir de aquí el movimiento es de n - 2 unidades, es decir de 3 - 2 = 1 unidad hacia arriba ( [0,2] → [0,1] ), después 1 unidad hacia la derecha ( [0,1] → [1,1] ), en este punto  el desplazamiento es de n - 3 = 3 - 3 = 0 unidades, entonces el proceso termina cuando el desplazamiento llega a ser de 0 unidades. 

Si observamos con atención, existe un patrón que describe el movimiento en espiral dentro del arreglo. A continuación el algoritmo.

Teniendo un arreglo de 3x3 por ejemplo, donde;

n  = 3; 
mov = n - 1;



col = 0
fil = 0
Para i = 0 hasta i = mov hacer
   Escribir arreglo[col,fil]
   col = col + 1
Fin para
Para i = 0 hasta i = mov hacer
   Escribir arreglo[col,fil]
   fil = fil + 1
Fin para
Para i = 0 hasta i = mov hacer
   Escribir arreglo[col,fil]
   col = col - 1
Fin para
mov = mov - 1
Mientras( mov >= 1) hacer   //Comienza el patrón
   Para i = 0 hasta i = mov hacer
      Escribir arreglo[col,fil]
      fil = fil - 1
   Fin para
   Para i = 0 hasta i = mov hacer
      Escribir arreglo[col,fil]
      col = col + 1
   Fin para
   mov = mov - 1
   Para i = 0 hasta i = mov hacer
   Escribir arreglo[col,fil]
      col = col + 1
      Fin para
   Para i = 0 hasta i = mov hacer
      Escribir arreglo[col,fil]
      fil = fil + 1
   Fin para
   mov = mov -1
Fin Mientras

Este algoritmo esta hecho para funcionar con cualquier arreglo cuadrado sin importar sus dimensiones y utiliza estructuras básicas de iteración. No es ni por mucho el único algoritmo ni el más eficiente, pero sirve para dar una idea de cómo se puede hacer este recorrido en un arreglo cuadrado. A continuación el código en C#.

public int[,] Espiral(int[,] a, int n)

{

int c = 1;
int cx = 0;
int cy = 0;
int lim = n - 1;
for(int i = 0; i< lim; i++)
{
  a[cx,cy] = c;
  cx++; //mueve hacia la derecha
  c++;
}
for(int i = 0; i < lim; i++)
{
  a[cx,cy] = c;
  cy++; //mueve hacia abajo
  c++;
}
for(int i = 0; i < lim; i++)
{
   a[cx,cy] = c;
   cx--; //mueve hacia la izquierda
   c++;
}
lim--;
while(lim>=1)
{
   if(lim>=1)
       for(int i = 0; i<lim; i++)
       {
           a[cx,cy] = c;
           cy--; //hacia arriba
           c++;
       }
    if(lim>=1)
        for(int i = 0; i<lim; i++)
        {
            a[cx,cy] = c;
            cx++; //hacia la derecha
            c++;
        }
     lim--;
     if(lim>=1)
         for(int i = 0; i<lim; i++)
         {
            a[cx,cy] = c;
            cy++; //hacia abajo
            c++;
         }
     if(lim>=1)
         for(int i = 0; i<lim; i++)
         {
             a[cx,cy] = c;
             cx--; //hacia la izquierda
             c++;
          }
      lim--;
}
return a

}

Claramente, este código contiene algunas validaciones que el algoritmo original no tiene, aunque dichas validaciones aparecen por si mismas al estar implementando el algoritmo en un lenguaje de programación. 

El recorrido análogo del espiral, el espiral desde el centro, funciona de una manera muy similar, comienza del centro, hace un movimiento en alguna dirección, hace otro movimiento, aumenta la cantidad de desplazamientos, hace un movimiento en cierta dirección, hace otro movimiento, nuevamente aumenta en 1 la cantidad de desplazamientos y el ciclo se repite hasta llegar al principio del arreglo. 

Próximamente se incluirán algunos otros recorridos típicos de los arreglos de cuadrados.