\chapter{Arreglos y Punteros}

\section{Introducción}

Un apuntador o Puntero  es una variable que contiene la dirección en memoria de otra variable. Se pueden tener apuntadores a cualquier tipo de variable. La manera de declarar un apuntador es utilizando * así por ejemplo:


\begin{center}
\begin{tabular}{|c|c|}
	\hline 
	char * a; & es un apuntador a una variable de tipo char \\
	int *a; & es un apuntador a entero \\
	float *a; & es un apuntador a una variable de tipo float\\
	double *a; & es un apuntador a una variable tipo double\\
	tipo *a & es un apuntador  a una variable de tipo general  \\
	\hline
\end{tabular}
\end{center}

Así por ejemplo cuando se tenga la declaración

\begin{verbatim}
   void main() {
         int *a;
         char *b;
   }
\end{verbatim}

Las variables $a$ y $b$ son apuntadores y representan la dirección física en memoria de donde se almacena los valores en cada variable.

Un apuntador es la variable mas versátil de C ya que podemos acceder el contenido de cualquier localidad de memoria y cambiar su contenido. Esta posibilidad le da a C una capacidad para cambiar los contenidos de video, puertos, impresoras, tarjetas de video, variables, etc.
 
Los apuntadores tendrán un doble significado, así por ejemplo

\begin{verbatim}
	void main() {
		int *a = 10;
		printf("%X, %d\n", a, *a);		
	}
\end{verbatim}

\begin{center}
\begin{tabular}{|c|c|}
	\hline
	a & representa la dirección de memoria donde se almacena el número 10\\
	*a & representa el número 10 almacenado en memoria \\
	\hline
\end{tabular}
\end{center}


\section{Direcciones de variables}

El operador unario o monádico \& devuelve la dirección de memoria de una variable, a diferencia del operador de indirección o deferencia * devuelve el ``contenido de un objeto apuntado por un apuntador''.

Para declarar un apuntador para una variable entera hacer:

\begin{verbatim}
	int *apuntador;
\end{verbatim}

Se debe asociar a cada apuntador un tipo particular. Por ejemplo, no se puede asignar la dirección de un short int a un long int.

Para tener una mejor idea, considerar el siguiente código:

\begin{verbatim}
 main() {
    int x = 1, y = 2;
    int *ap;

    ap = &x;

    y = *ap;

    x = ap;

    *ap = 3;
}
\end{verbatim}


Con el objetivo de entender el comportamiento del código supongamos que la variable x esta en la localidad de la memoria 100, y en 200 y ap en 1000. Nota: un apuntador es una variable, por lo tanto, sus valores necesitan ser guardados en algún lado.

\begin{verbatim}
   int x = 1, y = 2;
   int *ap;

   ap = &x;
\end{verbatim}

\begin{tabular}{|c|c|c|}
  \hline
  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
  100 & 200 & 1000 \\
\begin{tabular}{|c|c|}
  \hline
  x & 1 \\
  \hline
\end{tabular} &
\begin{tabular}{|c|c|}
  \hline
  y & 2 \\
  \hline
\end{tabular} &
\begin{tabular}{|c|c|}
  \hline
    ap & 100 \\
  \hline
\end{tabular} \\
\hline
\end{tabular}

Las variables $x$ e $y$ son declaradas e inicializadas con 1 y 2 respectivamente, ap es declarado como un apuntador a entero y se le asigna la dirección de x (\&x). Por lo que ap se carga con el valor 100.

y = *ap;


\begin{tabular}{|c|c|c|}
  \hline
  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
  100 & 200 & 1000 \\
\begin{tabular}{|c|c|}
  \hline
  x & 1 \\
  \hline
\end{tabular} &
\begin{tabular}{|c|c|}
  \hline
  y & 1 \\
  \hline
\end{tabular} &
\begin{tabular}{|c|c|}
  \hline
    ap & 100 \\
  \hline
\end{tabular} \\
\hline
\end{tabular}

Después y obtiene el contenido de ap. En el ejemplo ap apunta a la localidad de memoria 100 -- la localidad de x. Por lo tanto, y obtiene el valor de x -- el cual es 1.

x = ap;

\begin{tabular}{|c|c|c|}
  \hline
  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
  100 & 200 & 1000 \\
\begin{tabular}{|c|c|}
  \hline
  x & 100 \\
  \hline
\end{tabular} &
\begin{tabular}{|c|c|}
  \hline
  y & 1 \\
  \hline
\end{tabular} &
\begin{tabular}{|c|c|}
  \hline
    ap & 100 \\
  \hline
\end{tabular} \\
\hline
\end{tabular}

Como se ha visto C no es muy estricto en la asignación de valores de diferente tipo (apuntador a entero). Así que es perfectamente legal (aunque el compilador genera un aviso de cuidado) asigna el valor actual de ap a la variable x. El valor de ap en ese momento es 100.

*ap = 3;

\begin{tabular}{|c|c|c|}
  \hline
  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
  100 & 200 & 1000 \\
\begin{tabular}{|c|c|}
  \hline
  x & 3 \\
  \hline
\end{tabular} &
\begin{tabular}{|c|c|}
  \hline
  y & 2 \\
  \hline
\end{tabular} &
\begin{tabular}{|c|c|}
  \hline
    ap & 100 \\
  \hline
\end{tabular} \\
\hline
\end{tabular}

Finalmente se asigna un valor al contenido de un apuntador (*ap).

Importante: Cuando un apuntador es declarado apunta a algún lado. Se debe inicializar el apuntador antes de usarlo. Por lo que:

main() {
    int *ap;
    *ap = 100;
}
\noindent
puede generar un error en tiempo de ejecución o presentar un comportamiento errático.

El uso correcto será:

\begin{verbatim}
 main() {
    int *ap;
    int x;

    ap = &x;
    *ap = 100;
}
\end{verbatim}

Con los apuntadores se puede realizar también aritmética entera, por ejemplo:

\begin{verbatim}
 main() {
    float *flp, *flq;

    *flp = *flp + 10;

    ++*flp;

    (*flp)++;

    flq = flp;
}
\end{verbatim}
NOTA: Un apuntador a cualquier tipo de variables es una dirección en memoria -- la cual es una dirección entera, pero un apuntador NO es un entero.

La razón por la cual se asocia un apuntador a un tipo de dato, es por que se debe conocer en cuantos bytes esta guardado el dato. De tal forma, que cuando se incrementa un apuntador, se incrementa el apuntador por un ``bloque'' de memoria, en donde el bloque esta en función del tamaño del dato.

Por lo tanto para un apuntador a un char, se agrega un byte a la dirección y para un apuntador a entero o a flotante se agregan 4 bytes. De esta forma si a un apuntador a flotante se le suman 2, el apuntador entonces se mueve dos posiciones float que equivalen a 8 bytes.

El siguiente es un ejemplo de como a través de un apuntador podemos cambiar el contenido de una variable.

\begin{verbatim}
/* 
 * File:   cambia_valores.c
 * Author: felix
 *
 * Created on 25 de octubre de 2011, 9:46
 */

#include <stdio.h>
#include <stdlib.h>

/*
 * Ejemplo de cambio de valores
 */
int main(int argc, char** argv) {
    int a = 10, b = 15, c = 20;
    int *p;
    
    printf("a = %d b = %d c = %d\n", a, b, c);
    printf("direcciones de a = %X b = %X y C = %X\n", &a, &b, &c);
    
    p = &a;
    *p = 15;
    
    p = &b;
    
    *p = 16;
    
    printf("a = %d b = %d c = %d\n", a, b, c);
    
    printf("En la direccion %X hay un %d\n", p, *p);
    p++;
    printf("En la direccion %X hay un %d\n", p, *p);

    return (0);
}
\end{verbatim}

\section{Punteros como argumentos}
Los punteros puwden ser utilizados como argumentos de una función. El caso mas conocido y que hemos estado utilizando es la función scanf. En esta función cuando hacemos el llamado a ella escribimos
\begin{verbatim}
      float a ;
      scanf("%f", &a);
\end{verbatim}

\noindent
En este caso la función scanf, recibe dos parametros, una cadena de control y la dirección donde se almacena la variable a. El prototipo de la función scanf es:

\begin{verbatim}
      scanf(char *, float *);
\end{verbatim}

Una de las aplicaciones  mas interesante de los apuntadores es cuando queremos que en una función los argumentos sean modificados dentro del cuerpo de la función.  Un ejemplo de esto es la función inc del siguiente ejemplo

\begin{verbatim}
/* 
 * File:   incremento.c
 * Author: felix
 *
 * Created on 27 de octubre de 2011, 9:37
 */

#include <stdio.h>
#include <stdlib.h>

/*
 * 
 */
void inc01(int x) {
    x ++;
}

int inc(int x) {
    x++;
    return x;
}

void inc2(int *x) {
    (*x)++;
}

int main(int argc, char** argv) {
    int x = 10;
    printf("x = %d\n", x);
    inc01(x);
    printf("x = %d\n", x);
    x = inc(x);
    printf("x = %d\n", x);
    inc2(&x);
    printf("x = %d\n", x);
    return (EXIT_SUCCESS);
}

\end{verbatim}

\section{Paso por valor y por referencia en funciones}

En C el paso por valor significa que al compilar la función y el código que llama a la función, Esta recibe una copia de los valores de los parámetros que se le pasan como argumentos. Las variables reales no se pasan a la función, solo copias de su valor.

Cuando una función debe modificar el valor de la variable pasada como parámetro y que esta modificación retorne a la función llamadora, se debe pasar el parámetro por referencia. En este método, el compilador no pasa una copia del valor del argumento; en su lugar, pasa una referencia, que indica a la función donde existe la variable en memoria.

La referencia que una función recibe es la dirección de la variable. Es decir, pasar un argumento por referencia es, simplemente, indicarle al compilador que pase la dirección del argumento.

Ejemplo:
\begin{verbatim}
void demo(int &valor) {
  valor=5;
  printf("%d\n",valor);
}

void main() {
  int n=10;
  printf("%d\n", n);
  demo(n);
  printf("%d\n", n);
}
\end{verbatim}

La salida de este programa será 5;

\subsubsection{Ejemplo de paso por referencia}

Dados dos números a y b hacer un programa que reciba como argumentos estos dos números y que independientemente de los valores siempre en la variable a este el mayor y en b el menor. La implementación en C es:

\begin{verbatim}
//Ejemplo paso_x_referencia.c

/**
 * <p>Title: Paso por referencia</p>
 *
 * <p>Description: Cambia el valor de dos numeros en una función</p>
 *
 * <p>Copyright: Copyright (c) 2003</p>
 *
 * <p>Company: UMSNH</p>
 *
 * @author Dr. Felix Calderon Solorio
 * @version 1.0
 */

#include <stdio.h>

void cambia(float *x, float *y);

int main() {
    
  float a = 2;
  float b = 3;
    
  printf("Antes   %f %f\n", a, b);
    
  cambia(&a, &b);
    
  printf("Despues %f %f\n", a, b);

  return 0;
}
  
void cambia(float *x, float *y)
{
  float temp = *x;
  *x = *y;
  *y = temp;

  return;
}
\end{verbatim}

Cuando en C se utiliza \&a, se esta pasando la dirección de la variable a, en la memoria donde reside el dato; y cuando *a es el apuntador de la memoria (apuntadores será revisado en los siguientes capítulos).


\section{Aritmética de apuntadores}

Como ya se mencionó los apuntadores tienen asociado un tipo de datos, este es muy importante cuando necesitamos realizar operaciones con un apuntador. En esta sección analizaremos la aritmética de apuntadores.

Sea:
\begin{verbatim}
   int a[10], *ap;
   ap = a; /*dirección del primer elemento */
\end{verbatim}
a es el nombre de un arreglo de enteros, recuerda que el nombre de un arreglo se define como:

a $\equiv \&$ a[0]

\noindent 

por lo tanto el nombre de cualquier arreglo es un APUNTADOR CONSTANTE, esto implica que:

ap $ \equiv \&$ a[0]


El siguiente esquema muestra la relación existente entre los elementos del arreglo a y del apuntador ap:


\begin{tabular}{|c|c|c|c|c|c|}
  \hline
  a = &a[0]& a[1]& a[2] & ... & a[n-1]\\
  & & & & & \\
  \hline
  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
  & 0008 & \_\_\_\_ & \_\_\_\_ & ....&\_\_\_\_  \\
  \hline
  & & & & & \\
  ap = & 1000& 1004& 1008& ... & 4*(n-1)+1000\\
  \hline

\end{tabular}


Como se puede observar el apuntador ap más un número entero, equivale a la dirección de alguno de los elementos del arreglo, esto es:


( ap + 0 )  $ \equiv \&$ a[0]

( ap + 1 )  $ \equiv \&$ a[1]

.... ...

( ap + 8 )  $ \equiv \&$ a[8]


( ap + 2 )  $ \equiv \&$ a[0] + ( 2 * sizeof(int) )

ap ++; /* apunta a \& a[1] */

ap += 3; /* apunta a \& a[4] */


De la misma manera el contenido del apuntador hace referencia al contenido de alguno de los elementos del arreglo, es decir:

\begin{verbatim}
*( ap + 0 )  a[0]

*( ap + 1 )  a[1]

.... ...

*( ap + 8 )  a[8]


*( ap + 2 )  *(a[0] + ( 2 * sizeof(int) ) )

*(ap ++); /* contenido del elemento a[1] */

*(ap += 3); /* contenido del elemento a[4] */
\end{verbatim}


El nombre de un arreglo es un apuntador al primer elemento del mismo,1 por eso basta con asignar el nombre a un apuntador, para que este apunte al inicio del arreglo.

Cuando le sumamos un entero a un apuntador, este avanza tantas direcciones como bytes ocupen el tipo de dato del arreglo. En el ejemplo de arriba nota que los apuntadores se incrementan de 4 en 42

La resta de apuntadores es valida siempre y cuando ambos apunten a un mismo arreglo, el resultado es el numero de celda que existen entre las celdas apuntadas. Si restamos bp-ap obtenemos 93

Los apuntadores pueden compararse entre sí, siempre y cuando apunten a un mismo arreglo. Las comparaciones se hacen en base a la posición de las celdas apuntadas. Por ejemplo:

\begin{verbatim}
if (ap == bp) /* es falsa */

if (ap != bp ) /* es cierta */

if (ap > bp ) /* es falsa */

if (ap < bp ) /* es cierta */

if (ap >= bp ) /* es falsa */

if (ap <= bp ) /* es cierta */
\end{verbatim}

El siguiente ejemplo muestra como se pueden acceder localidades de memoria consecutivas y colocar un valor e imprimirlo.

\begin{verbatim}
Cualquier otra operación con apuntadores NO ES VALIDA.
/* 
 * File:   aritmetica.c
 * Author: felix
 *
 * Created on 5 de mayo de 2012, 19:14
 */

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char** argv) {
    int a[10];
    int *p, i;
    p = a;
    
    for(i=0; i<10; i++) 
        *(p + i) = i+1;
    
    for(i=0; i<10; i++) 
        printf("%D %d\n" , (p+i), *(p + i));
    
    return (EXIT_SUCCESS);
}
\end{verbatim}

Como resultado de la ejecución podemos ver que un incremento unitario equivale a 4 en dirección de memoria, lo cual corresponde al tamaño de un entero.

\section{Definición de arreglo y declaración tipo vector y tipo matriz}

Los vectores y matrices en matemáticas se definen como arreglos de números representados por una variable. Los vectores se representaran como

\begin{equation*}
a = 
\left(
\begin{array}{c}
  a_1   \\
  a_2   \\
  \vdots \\
  a_n   
\end{array}
\right)
\]

y las matrices se representan como

\[
\left(
\begin{array}{cccc}
  a_{1,1} &   a_{1,2} & \cdots  & a_{1,N} \\
  a_{2,1} &   a_{2,2} & \cdots  & a_{2,N} \\
  \cdots   &   \cdots  & \cdots   & \vdots \\
  a_{M,1} &   a_{M,2} & \cdots  & a_{M,N} \\
\end{array}
\right)
\]

\subsection{Los vectores}

Imaginemos que tenemos que hallar el promedio de 10 números que introduzca el usuario (o realizar cualquier otra operación con ellos). Parece evidente que tiene que haber una solución más cómoda que definir 10 variables distintas y escribir 10 veces las instrucciones de avisar al usuario, leer los datos que teclee, y almacenar esos datos. Si necesitamos manejar 100, 1000 o 10000 datos, resulta todavía más claro que no es eficiente utilizar una variable para cada uno de esos datos.

Por eso se emplean los arrays (o arreglos). Un array es una variable que puede contener varios dato del mismo tipo. Para acceder a cada uno de esos datos emplearemos corchetes. Por ejemplo, si definimos una variable llamada $m$ que contenga 10 números enteros, accederemos al primero de estos números como m[0], el último como m[9] y el quinto como m[4] (se empieza a numerar a desde 0 y se termina en n-1). Veamos un ejemplo que halla la media de cinco números (con decimales, "double"):


\begin{verbatim}
/* 
 * File:   Arreglos.c
 * Author: felix
 *
 * Created on 27 de octubre de 2011, 9:18
 */

#include <stdio.h>
#include <stdlib.h>

/*
 * 
 */

void ejemplo01(){
    float a[10];
    int i;
    
    // Lee 10 numeros de teclado
    
    for(i=0; i<10; i++) {
        printf("Dame el valor a[%d] = ", i);
        scanf("%f", &a[i]);
    }
    
    
    // Imprime 10 numeros
    
    for(i=0; i<10; i++)
        printf("%f\n", a[i]);
}

void ejemplo02(){
    float a[10];
    int i;
    
    // Lee 10 numeros de teclado
    
    for(i=0; i<10; i++) {
        printf("Dame el valor a[%d] = ", i);
        scanf("%f", a+i);
    }
    
    
    // Imprime 10 numeros
    
    for(i=0; i<10; i++)
        printf("%f\n", *(a+i));
}

int main(int argc, char** argv) {

    ejemplo01();
    return (EXIT_SUCCESS);
}
\end{verbatim}

Para definir la variable podemos usar dos formatos:  ``float a[10]'' que es la sintaxis habitual en C en el cual se declaran los arreglos de manera fija a tiempo de ejecución o de manera dinámica.

Lo habitual no será conocer los valores en el momento de teclear el programa, como hemos hecho esta vez. Será mucho más frecuente que los datos los teclee el usuario o bien que los leamos de algún fichero, los calculemos, etc.  En este caso, tendremos que reservar el espacio, y los valores los almacenaremos a medida que vayamos conociéndolos.

Para ello, primero declararíamos que vamos a utilizar un array, así:

\begin{verbatim}
   float  *datos;
\end{verbatim}

\noindent
y después reservaríamos espacio (por ejemplo, para 1000 datos) con

\begin{verbatim}
   datos = (float *) malloc(1000*sizeof(float));
\end{verbatim}

\noindent
o también
\begin{verbatim}
   datos = (float *) calloc(1000, sizeof(float));
\end{verbatim}


Los valores los podemos asignar de una forma similar a la que hemos visto en el ejemplo anterior:

\begin{verbatim}
   datos[25] = 100 ; datos[0] = i*5 ; datos[j+1] = (j+5);
\end{verbatim}

Vamos a ver un ejemplo algo más completo, con  arrays de números enteros, llamados a, b y c. A uno de ellos (a) le daremos valores al definirlo, otro lo definiremos en dos pasos (b) y le daremos fijos, y el otro lo definiremos en un paso y le daremos valores calculados a partir de ciertas operaciones:

La implementación en C es

\begin{verbatim}
//inicia_arreglo.c

/**
 * <p>Title: Arreglos</p>
 *
 * <p>Description: inicializa arreglos de varias formas</p>
 *
 * <p>Copyright: Copyright (c) 2003</p>
 *
 * <p>Company: UMSNH</p>
 *
 * @author Dr. Félix Calderon Solorio
 * @version 1.0
 */

#include <stdio.h>
#include <stdlib.h>

int main( ) {

     int i;  // Para repetir con bucles "for"

     // ------  Primer array de ejemplo
     int a[] = { 10, 12345, -15, 0, 7 };

     printf( "Los valores de a son:\n" );
     for (i=0; i<5; i++)
       printf("%d\n", a[i]);

     // ------  Segundo array de ejemplo
     
	 int *b  = (int*) calloc(3, sizeof(int));

     b[0] = 15; b[1] = 132; b[2] = -1;

     printf( "Los valores de b son:\n" );
     for (i=0; i<3; i++)
       printf("%d\n", b[i] );

     // ------  Tercer array de ejemplo
     int j = 4;
     int *c = new int[j];

     for (i=0; i<j; i++)
       c[i] = (i+1)*(i+1);

     printf("Los valores de c son: \n" );
     for (i=0; i<j; i++)
       printf("%d\n", c[i]);

	 return 0;
     
}
\end{verbatim}


En general la forma mas común y que permite el manejo dinámico de memoria es utilizando la instrucción calloc o malloc. Esta la podemos escribir dentro de una función a la denominaremos vector, dicha función recibe el tamaño del arreglo y regresa un apuntador con la dirección a partir de la cual se guardaron los $N$ valores. En el siguiente código se muestra esto 

\begin{verbatim}
/* 
 * File:   vector.c
 * Author: felix
 *
 * Created on 16 de mayo de 2012, 5:22
 */

#include <stdio.h>
#include <stdlib.h>

/*
 * 
 */

float * vector(int N) {
    
    float *ap;
    
    ap = (float *) calloc(N, sizeof(float));
    
    return ap;
}

int main(int argc, char** argv) {
    
    float *v;
    
    v= vector(10);
    
    return (EXIT_SUCCESS);
}
\end{verbatim}

En este caso cuando se llama a la función vector(10) regresa un apuntador con 10 reservaciones de flotantes numerados del 0 al 9 respectivamente. Para hacer una reservación de diferente tipo solamente hay que cambiar float por cualquier otro tipo en todas las variables involucradas en la función.

El siguiente código es un ejemplo de un arreglo que es inicializando con los números de 1 al 10 y como imprimir los números contenidos en el.

\begin{verbatim}
/* 
 * File:   vector.c
 * Author: felix
 *
 * Created on 16 de mayo de 2012, 5:22
 */

#include <stdio.h>
#include <stdlib.h>

float * vector(int N) {    
    float *ap;   
    ap = (float *) calloc(N, sizeof(float));    
    return ap;
}

void llena(float *a, int N) {
    int i;
    
    for(i=0; i<N; i++)
        a[i] = i+1;
}

void imprime(float *a, int N) {
    int i;
    
    for(i=0; i<N; i++)
        printf("%f\n", a[i]);
}

int main(int argc, char** argv) {
    
    float *v;
    
    v= vector(10);
    llena(v, 10);
    imprime(v, 10);    
    return (EXIT_SUCCESS);
}
\end{verbatim}


\textbf{Ejercicio}

Hacer una función que regrese, los primeros 10 números de la sucesión de Fibonacci.

\subsection{Matrices}

Las matrices se definen, como un arreglo bidimensional, en donde tenemos un número de renglones N y un número de columnas M. La representación matemática de una matriz es :

$$
\left(%
\begin{array}{cccc}
a_{1,1} & a_{1,2} &  \cdots &  a_{1,M} \\
a_{2,1} & a_{2,2} &  \cdots &  a_{2,M} \\
\cdots & \cdots &  \cdots & \cdots \\
a_{N,1} & a_{N,2} &  \cdots &  a_{N,M} \\
\end{array}%
\right)
$$

Para hacer la definición de un arreglo bidimensional en C, se hace  es mediante la siguiente instrucción

\begin{verbatim}
    double a[][] = {{1,2,3}, {4,5,6}, {7,8,9}};
\end{verbatim}
\noindent
donde a es el nombre del arreglo 3 el número de renglones y 3 el número de columnas. Para hacer referencia al elemento en el i-esimo renglón y la j-esima columna hacemos a[i][j], por ejemplo para imprimir el valor el la posición a[0][0] escribimos

\begin{verbatim}
    printf("%f\n", a[0][0]);
\end{verbatim}

\noindent
el arreglo bidemensional o matriz es 

$$
a = \left(%
\begin{array}{ccc}
 1 & 2 & 3 \\
 4 & 5 & 6 \\
 7 & 8 & 9\\
\end{array}%
\right)
$$

\subsection{Ejemplo}

Hacer un programa que almacene la matriz anterior en un arreglo,la eleve al cuadrado e imprima el resultado en la pantalla.

La implementación pero en C es

\begin{verbatim}
/* 
 * File:   arreglo_bidimensional.c
 * Author: felix
 *
 * Created on 16 de mayo de 2012, 6:18
 */

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char** argv) {
  double a[3][3] = {{1,2,3}, {4,5,6}, {7,8,9}};
  double b[3][3] = {0,0,0,0,0,0,0,0,0} ;

  int i, j;


  for(i=0; i< 3; i++)
    for(j=0; j<3; j++)
      b[i][j] = a[i][j] * a[i][j];

  for(i=0; i< 3; i++)
  {
    for(j=0; j<3; j++)
      printf("%f ", b[i][j]);
    printf("\n");
  }
    
    return (EXIT_SUCCESS);
}
\end{verbatim}

\section{Manipulación de arreglos y punteros}

Una forma alterna de declarar una matriz es utilizando las instrucciones calloc y malloc ya que de esta forma podemos declarar arreglos de cualquier longitud en tiempo de ejecución. La manera de declarar una matriz de flotantes es utilizando apuntadores, un * será un apuntador a un arreglo unidimensional. dos ** a un arreglo bidimensional y así sucesivamente. Para declara el arreglo bidimensional M escribimos: 

\begin{verbatim}
   float **M;
\end{verbatim}

El siguiente paso es reservar memoria utilizando las instrucciones calloc, esto lo realizamos en dos pasos, primero hacemos la declaración de los renglones para después declarar las columnas

\begin{verbatim}
  M = (TIPO **) calloc(ren, sizeof(TIPO*)); // buscar en stdlib.h
\end{verbatim}

\noindent
donde TIPO es cualquier tipo de datos declarado por el usuario. Posteriormente para cada columna reservamos la memoria haciendo

\begin{verbatim}
  for(i=0; i<ren; i++)
	M[i] = (TIPO *) calloc(col, sizeof(TIPO));
\end{verbatim}

\noindent
finalmente tenemos un arreglo M de TIPO de tamaño $ren \times col$. Todo esto lo podemos ver en la función Matriz que podemos usar en cualquier otro código

\begin{verbatim}
TIPO ** Matriz(int ren, int col)
{
  TIPO **aux;
  int i, j;

  aux = (TIPO **) calloc(ren, sizeof(TIPO*)); // buscar en stdlib.h

  for(i=0; i<ren; i++)
	aux[i] = (TIPO *) calloc(col, sizeof(TIPO));
    
  return aux;   
}
\end{verbatim}

\subsection{Ejemplo}
Hacer una función que reciba un número y regrese un cuadro de texto lleno de asteriscos, del mismo tamaño que el número que recibe y con el número en la diagonal. Así pues, esta función dado el número 4 regresara la información

\begin{verbatim}
4***
*4**
**4*
***4
\end{verbatim}

La implementación en C queda

\begin{verbatim}
//Ejemplo ec043.cpp

/**
 * <p>Title: Ejemplo de llenado de matrices</p>
 *
 * <p>Description: Llena una matriz con asteriscos</p>
 *
 * <p>Copyright: Copyright (c) 2005</p>
 *
 * <p>Company: UMSNH</p>
 *
 * @author Dr. Felix Calderon Solorio
 * @version 1.0
 */

/* 
 * File:   cuadro.c
 * Author: felix
 *
 * Created on 16 de mayo de 2012, 10:25
 */

#include <stdio.h>
#include <stdlib.h>

typedef char TIPO; 

void imprime(char **a, int n); 
char ** llena(int n);
char ** Matriz(int ren, int col);

int main() {
  char **a;
  int n = 5;

  a = llena(n);
  imprime(a, n);

  return 0;
}

void imprime(char **a, int n) {
  int i, j;

  for(i=0; i<n; i++)
  {
    for (j = 0; j < n; j++)
      printf("%c", a[i][j]);
    printf("\n");
  }
}


char ** llena(int n) {
  char **aux;
  int i, j;

  aux = Matriz(n, n);

  for(i=0; i<n; i++)
    for(j=0; j<n; j++)
      if(i==j) aux[i][j] = (char) (n+48);
      else aux[i][j] = '*';

  return aux;

}

TIPO ** Matriz(int ren, int col)
{
  TIPO **aux;
  int i, j;

  aux = (TIPO **) calloc(ren, sizeof(TIPO*)); // buscar en stdlib.h

  for(i=0; i<ren; i++)
	aux[i] = (TIPO *) calloc(col, sizeof(TIPO));
    
  return aux;   
}
\end{verbatim}


\section{Diferencia entre variables tipo apuntador y variables tipo arreglo}

Existe una relación estrecha entre los punteros y los arreglos. En C, un nombre de un arreglo es un índice a la dirección de comienzo del arreglo. En esencia, el nombre de un arreglo es un puntero al arreglo. Considerar lo siguiente:

\begin{verbatim}
int a[10], x; int *ap;

ap = &a[0];    /* ap apunta a la direccion de a[0] */

x = *ap;       /* A x se le asigna el contenido de ap (a[0] en
este caso) */

*(ap + 1) = 100;  /* Se asigna al segundo elemento de 'a' el valor
100 usando ap*/
\end{verbatim}

Como se puede observar en el ejemplo la sentencia a[t] es idéntica a ap+t. Se debe tener cuidado ya que C no hace una revisión de los límites del arreglo, por lo que se puede ir fácilmente mas alláá del arreglo en memoria y sobreescribir otras cosas.

\noindent
C sin embargo es mucho más sutil en su relación entre arreglos y apuntadores. Por ejemplo se puede teclear solamente:

\noindent
ap = a; en vez de ap = \&a[0]; y también *(a + i) en vez de a[i], esto es, \&a[i] es equivalente con a+i. Y como se ve en el ejemplo, el direccionamiento de apuntadores se puede expresar como:

\noindent
a[i] que es equivalente a *(ap + i) Sin embargo los apuntadores y los arreglos son diferentes:

Un apuntador es una variable. Se puede hacer ap = a y ap++. Un arreglo NO ES una variable. Hacer a = ap y a++ ES ILEGAL. Este parte es muy importante, asegúrese haberla entendido.

Con lo comentado se puede entender como los arreglos son pasados a las funciones. Cuando un arreglo es pasado a una función lo que en realidad se le esta pasando es la localidad de su elemento inicial en memoria.

Por lo tanto:

\noindent
strlen(s) es equivalente a strlen(\&s[0]) Esta es la razón por la cual se declara la función como:

\noindent
int strlen(char s[]); y una declaración equivalente es int strlen(char *s); ya que char s[] es igual que char *s.

La función strlen() es una función de la biblioteca estándar que regresa la longitud de una cadena. Se muestra enseguida la versión de esta función que podría escribirse:

\begin{verbatim}
int strlen(char *s) {
    char *p = s;

    while ( *p != '\0' )
        p++;
    return p - s;
}
\end{verbatim}

Se muestra enseguida una función para copiar una cadena en otra. Al igual que en el ejercicio anterior existe en la biblioteca estándar una función que hace lo mismo.

\begin{verbatim}
void strcpy(char *s, char *t) {
    while ( (*s++ = *t++) != '\0' );
}
\end{verbatim}

En los dos últimos ejemplos se emplean apuntadores y asignación por valor. Nota: Se emplea el uso del carácter nulo con la sentencia while para encontrar el fin de la cadena.


\section {Matrices, Operaciones básicas} \label{sec:matrices}

Una matriz se define como un arreglo bidimensional de datos, que tiene n renglones y m columnas. Un elemento del arreglo puede ser identificado con $a_{ij}$

$$
A = \left(%
\begin{array}{ccccc}
   a_{0,0} & a_{0,1} & a_{0,2} & ... & a_{0,n-1}  \\
   a_{1,0} & a_{1,1} & a_{1,2} & ... & a_{1,n-1}  \\
   a_{2,0} & a_{2,1} & a_{2,2} & ... & a_{2,n-1}  \\
       &     &     &     &      \\
   a_{m-1,0} & a_{m-1,1} & a_{m-1,2} & ... & a_{m-1,n-1}  \\
\end{array}%
\right)
$$

Algunas de las operaciones básicas que pueden realizarse con matrices son suma, resta y multiplicación. La división de matrices como tal no existe y en su lugar se calcula la inversa.

\subsection{Suma de matrices}

Para que la sumar las matrices A y B, se requiere que las matrices tengan el mismo número de renglones y de columnas. Si queremos encontrar la suma C = A + B, cada elemento de la matriz C lo calculamos de la siguiente forma:

$$
C_{i,j} = A_{i,j} + B_{i,j}
$$
para todos lo $i,j$ en la matriz $C$


\subsection{Resta de matrices}

En este caso, se deben cumplir las mismas propiedades que la resta de matrices y el calculo de los elemento de la matriz C se calculan como:
$$
C_{i,j} = A_{i,j} - B_{i,j}
$$
para todos lo $i,j$ en la matriz $C$


\subsection{Multiplicación de matrices}

Para realizar el producto $C = A*B$ tenemos que considerar que el producto existe si

1.- El número de columnas de $A$ es igual al número de renglones de $B$.

$$
C(n,l) = A(n,m)*B(m,l)
$$

2.- Las dimensiones de la matriz resultante tendrá el mismo numero de renglones que la matriz $A$ y el mismo número de columnas que la matriz $B$.

3.- El cálculo de los elementos de la matriz C se lleva a cabo haciendo :

$$
c_{i,j} = \sum_{k=0}^{m-1} a_{i,k} * b_{k,j}
$$
para todos lo $i,j$ en la matriz $C$

\subsection{Solución de sistemas de ecuaciones triangulares} 

Considere el siguiente sistema de ecuaciones

$$
\left(%
\begin{array}{ccc}
a_{0,0} & a_{0,1} & a_{0,2} \\
      0 & a_{1,1} & a_{1,2} \\
      0 &       0 & a_{2,2} \\
\end{array}%
\right)
\left(%
\begin{array}{c}
  x_0 \\
  x_1 \\
  x_2 \\
\end{array}
\right) =
\left(%
\begin{array}{c}
  b_0 \\
  b_1 \\
  b_2 \\
\end{array}
\right)
$$

\noindent Podemos ver que la solución para $x_2$ es
$$
x_2 = \frac{b_2} {a_{2,2}}
$$
\noindent para $x_1$ es
$$
x_1 = \frac{b_1-a_{1,2}  x_2}{a_{1,1}}
$$
\noindent y para $x_0$
$$
x_0 = \frac{b_0-a_{0,1}  x_1 + a_{0,2} x_2}{a_{0,0}}
$$

\noindent en general tenemos que

$$
x_k = \frac{b_k-\sum_{j=k+1}^{n-1}  a_{k,j}  x_j}{a_{k,k}}
$$

Determinantes

Podemos ver que el determinante de una matriz triangular superior o inferior es :

$$
det(A)  = a_{0,0} * a_{1,1} a_{2,2}*...* a_{n-1,n-1}
$$

\subsection{Solución de sistemas lineales de ecuaciones por el método de Eliminación Gaussiana}

Consideremos que tenemos un sistema lineal Ax=b, donde la matriz A no tiene las condiciones de ser triangular superior.
$$
\left(%
\begin{array}{ccc}
a_{0,0} & a_{0,1} & a_{0,2} \\
a_{1,0} & a_{1,1} & a_{1,2} \\
a_{2,0} & a_{2,1} & a_{2,2} \\
\end{array}%
\right)
\left(%
\begin{array}{c}
  x_0 \\
  x_1 \\
  x_2 \\
\end{array}
\right) =
\left(%
\begin{array}{c}
  b_0 \\
  b_1 \\
  b_2 \\
\end{array}
\right)
$$

Comenzaremos por despejar  $x_0$ de la ecuación (I)

$$
x_0 = \frac{b_0 - a_{0,1}x_1 - a_{0,2}x_2}{a_{0,0}}
$$

y sustituimos en las ecuaciones (II)

$$
a_{1,0}\frac{b_0 - a_{0,1}x_1 - a_{0,2}x_2}{a_{0,0}} + a_{1,1}x_1
+ a_{1,2}x_2 = b_1
$$

agrupando términos semejantes tenemos:

$$
(a_{1,1}-\frac{a_{1,0} *a_{0,1}}{a_{0,0}})x_1 + (a_{1,2}-a_{1,0}
\frac{a_{0,2}}{a_{0,0}}) x_2 = (b_1 - a_{1,0} \frac{b_0}{a_{0,0}})
$$

Ahora sustituimos en la ecuación (III)

$$
a_{2,0}\frac{b_0 - a_{0,1}x_1 - a_{0,2}x_2}{a_{0,0}} + a_{2,1}x_1
+ a_{2,2}x_2 = b_2
$$
$$ (a_{2,1}-a_{2,0}
\frac{a_{0,1}}{a_{0,0}})x_1+(a_{2,2}-a_{2,0}
\frac{a_{0,2}}{a_{0,0}}) x_2 = (b_2-a_{2,0} \frac{b_0}{a_{0,0}})
$$


Lo cual nos da un nuevo sistema simplificado dada por

$$
\left(%
\begin{array}{ccc}
a_{0,0} & a_{0,1} & a_{0,2} \\
      0 & a'_{1,1} & a'_{1,2} \\
      0 & a'_{2,1} & a'_{2,2} \\
\end{array}%
\right)
\left(%
\begin{array}{c}
  x_0 \\
  x_1 \\
  x_2 \\
\end{array}
\right) = \left(
\begin{array}{c}
  b_0 \\
  b'_1 \\
  b'_2 \\
\end{array}
\right )
$$

donde los valores de $a'_{i,j}$ los calculamos como:
$$
a'_{i,j} = a_{i,j}-a_{i,k} \frac{a_{k,j}}{a_{k,k}}\\
b_i = b_i - a{i,k} \frac{b_k}{a_{k,k}}
$$

 Si repetimos el procedimiento, ahora para $x_1$, tendremos un sistema dado como:

$$
\left(%
\begin{array}{ccc}
a_{0,0} & a_{0,1} & a_{0,2} \\
      0 & a'_{1,1} & a'_{1,2} \\
      0 & 0 & a''_{2,2} \\
\end{array}%
\right)
\left(%
\begin{array}{c}
  x_0 \\
  x_1 \\
  x_2 \\
\end{array}
\right) =
\left(%
\begin{array}{c}
  b_0 \\
  b'_1 \\
  b''_2 \\
\end{array}
\right)
$$

\noindent 
que corresponde a un sistema triangular superior que podemos solucionar utilizando sustitución hacia atrás.

Ejemplo.

Calcular el sistema triangular superior utilizando eliminación gaussiana.

$$
5x + 2y + 1z = 3
$$
$$
2x + 3y - 3z = -10
$$
$$
1x - 3y + 2z = 4 \\
$$

Primer paso

$$
5x +      2y +      1z = 3
$$
$$
0  + (11/5)y-(17/5)z =-(56/5)
$$
$$
0  - (17/5)y +  (9/5)z = (17/5)
$$

Segundo paso

$$
5x +      2y +      1z   = 3
$$
$$
0x + (11/5)y-( 17/5)z =-(56/5)
$$
$$
0x -      0y -(38/11)z =-(153/11)
$$

Ejemplo.

Resolver el sistema de ecuaciones


$$
\left(%
\begin{array}{ccc}
3 &  -1 &  -1\\
-1 &  1 &  0 \\
-1 &  0 &  1\\
\end{array}%
\right)
\left(%
\begin{array}{c}
  x \\
  y \\
  z \\
\end{array}
\right) = \left(
\begin{array}{c}
  0 \\
  1 \\
  1 \\
\end{array}
\right )
$$


Aplicando eliminación gaussiana nos queda.

$$
\left(%
\begin{array}{ccc}
3 &  -1 &  -1 \\
0 &  2/3 &  -1/3\\
0 &  0 &  1/2 \\
\end{array}%
\right)
\left(%
\begin{array}{c}
  x \\
  y \\
  z \\
\end{array}
\right) = \left(
\begin{array}{c}
  0 \\
  1 \\
  3/2 \\
\end{array}
\right )
$$

Ejemplo.


Un ejemplo de sistema donde es necesario hacer un cambio de renglón por renglón para que tenga solución es el siguiente sistema. 

$$
\left(%
\begin{array}{ccc}
1 & 2 & 6 \\
4 & 8 & -1 \\
-2 & 3 &  5\\
\end{array}%
\right)
$$

Aplicando el primer paso de la eliminación gaussiana tenemos:

$$
\left(%
\begin{array}{ccc}
1 & 2 & 6 \\
0 & 0 & -25 \\
0 & 7 & 17 \\
\end{array}%
\right)
$$

\noindent
note, que aparece un cero en el elemento 22, lo cual nos da un sistema sin solución. Permutando los renglones 2 y 3 el sistema tiene solución.

$$
\left(%
\begin{array}{ccc}
1 &  2 & 6 \\
-2 &  3 &  5 \\
4 &  8 & -1 \\
\end{array}%
\right)
$$

La implementación de estos algoritmos en C es:

\begin{verbatim}
// operaciones_matrices.c

/**
 * <p>Title: Operaciones b·sicas con Matrices</p>
 *
 * <p>Description: Realiza las operaciones de suma, resta, multiplicaciÛn y
 * solucion de un sistema de equaciones</p>
 *
 * <p>Copyright: Copyright (c) 2005</p>
 *
 * <p>Company: UMSNH</p>
 *
 * @author Dr. FÈlix Calderon Solorio
 * @version 1.0
 */


#include <stdio.h>
#include <stdlib.h>

double **Matriz(int N, int M);
double *vector(int N);
double ** suma(double ** A, double ** B, int N, int M, int R, int S) ;
double ** resta(double ** A, double ** B, int N, int M, int R, int S) ;
double ** multiplica(double **A, double **B, int N, int M, int R, int S); 
double * SolucionSL(double **a, double *b, int N);
void imprime_v(char texto[], double *fuente, int N) ;
void imprime_m(char texto[], double **fuente, int N, int M);


int main()
{
    double **A = Matriz(2,2);
    double **B = Matriz(2,2);
    
    A[0][0] = 1; A[0][1] = 2;
    A[1][0] = 3; A[1][1] = 4;
    
    imprime_m("A =", A, 2, 2);
    
    B[0][0] =  4; B[0][1] = 3;
    B[1][0] = -3; B[1][1] = 5;

    imprime_m("B =", B, 2, 2);

    double **C = suma(A, B, 2, 2, 2, 2);
    imprime_m("C = ", C, 2,2);
    
    double **D = resta(A, B, 2, 2, 2, 2);
    imprime_m("D = ",D, 2,2);

	double **E = multiplica(A, B, 2, 2, 2, 2);
    imprime_m("E = ", E, 2,2);

	double *Z = vector(2);
	Z[0] = 10; Z[1] = 5;
	double *x = SolucionSL(A, Z, 2);
    imprime_v("X =", x, 2);

	return 1;

}


double **Matriz(int N, int M)
{
	double **a;
        int i;

	a = (double **) calloc (N, sizeof(double*));

	for(i=0; i<N; i++)
		a[i] = (double *) calloc(M, sizeof (double));

	return a;
}

double *vector(int N)
{
	double *a;

	a = (double *) calloc (N, sizeof(double));

	return a;
}

double ** suma(double ** A, double ** B, int N, int M, int R, int S) 
{
  int i, j;
    
  if(N!=R || M!=S) return 0;
    
  double ** res = Matriz(N,M);

  for (i = 0; i < N; i++)
    for (j = 0; j < M; j++)
      res[i][j] = A[i][j] + B[i][j];

  return res;
}

double ** resta(double ** A, double ** B, int N, int M, int R, int S) 
{

  int i, j;

  if(N!=R || M!=S) return 0;

  double ** res = Matriz(N,M);

  for (i = 0; i < N; i++)
    for (j = 0; j < M; j++)
      res[i][j] = A[i][j] - B[i][j];

  return res;
}

double ** multiplica(double **A, double **B, int N, int M, int R, int S) 
{

  int i, j, k;
    
  if(M!=R) return 0;

  double **res = Matriz(N,S);

  for (i = 0; i < N; i++) {
    for (j = 0; j < S; j++) {
      res[i][j] = 0;

      for (k = 0; k < M; k++)
        res[i][j] += A[i][k] * B[k][j];
    }
  }
  return res;
}

double * SolucionSL(double **a, double *b, int N) 
{
    int  i, j, k;
    double suma;
        
    double *x = vector(N);

    for (k = 0; k <= N - 2; k++) {
       for (i = k + 1; i <= (N - 1); i++) {
          b[i] -= a[i][k] * b[k] / a[k][k];
         for (j = N - 1; j >= k; j--)
                a[i][j] -= a[i][k] * a[k][j] / a[k][k];
        }
    }
    for (k = N - 1; k >= 0; k--) {
        suma = 0;
        for (j = k + 1; j < N; j++)
            suma += a[k][j] * x[j];
        x[k] = (b[k] - suma) / a[k][k];
    }
    return x;
}

void imprime_m(char texto[], double **fuente, int N, int M) 
{
    printf("%s\n", texto);
    if(fuente == 0) return;
    int i, j;

    for (i = 0; i < N; i++) {
        for (j = 0; j < M; j++) {
            printf("%f ", fuente[i][j]);
        }
    printf("\n");
    }
 }

void imprime_v(char texto[], double *fuente, int N) 
{
   printf("%s \n", texto);
   if (fuente == 0) return;
   int i;
    
   for (i = 0; i < N; i++) {
     printf("%f \n", fuente[i]);
      }
}
\end{verbatim}



\section {Ejemplos}

\subsubsection {Búsquedas lineales}

\subsubsection{Secuencial}

La forma más simple de búsqueda es la búsqueda secuencial. Esta búsqueda es aplicable a una tabla ``organizada'', ya sea como un arreglo o como una lista ligada. Supongamos que x es un arreglo de N llaves, de $x(0)$ a $x(N-1)$ y y el termino que deseamos encontrar en el arreglo, el algoritmo de búsqueda queda como:

\begin{verbatim}
int busqueda_secuencial(double x[], double y, int N)
{
    int i;

    for(i=0; i<N; i++)
      if(x[i] == y) return i;

    return -1;
}
\end{verbatim}


\subsubsection{Búsqueda Binaria}

El método de búsqueda más eficiente en una tabla secuencial sin usar índices o tablas auxiliares es el método de búsqueda binaria. Básicamente, se compara el argumento con la llave del elemento medio de la tabla. Sin son iguales, la búsqueda termina con éxito; en caso contrario, se busca de manera similar en la mitad superior o inferior de la tabla, según sea el caso.

\begin{verbatim}
int busqueda_binaria(double x[], double y, int N)
{
    int inicio = 0, fin = N, mitad;

    while(inicio <= fin)
    {
      mitad = (fin + inicio)/2;

      if(y == x[mitad]) return mitad;

      if(y < x[mitad]) fin = mitad -1;
      else inicio = mitad + 1;
    }
    return -1;
}
\end{verbatim}

El siguiente código muestra la implementación de ambos y un programa principal para hacer un llamado a cada uno de los métodos de búsqueda antes mencionados.

\begin{verbatim}
/* 
 * File:   busqueda_binaria.c
 * Author: felix
 *
 * Created on 16 de mayo de 2012, 12:28
 */

#include <stdio.h>
#include <stdlib.h>

int busqueda_secuencial(double x[], double y, int N)
{
    int i;

    for(i=0; i<N; i++)
      if(x[i] == y) return i;

    return -1;
}

int busqueda_binaria(double x[], double y, int N)
{
    int inicio = 0, fin = N, mitad;

    while(inicio <= fin)
    {
      mitad = (fin + inicio)/2;

      if(y == x[mitad]) return mitad;

      if(y < x[mitad]) fin = mitad -1;
      else inicio = mitad + 1;
    }
    return -1;
}

int main(int argc, char** argv) {
    double x[] = {1,2,4,7, 10, 11, 20, 21, 32};
    int N = 9, i;
    double y = 10;

    i = busqueda_secuencial(x, y, N);
    printf("El valor %f se encuentra en la posicion %d\n", y, i);
    printf("El valor %f se encuentra en la posicion %d\n", y,
      + busqueda_binaria(x, y, N));    
    return (EXIT_SUCCESS);
}
\end{verbatim}

\subsubsection {Método de ordenamiento (burbuja)}

El primer ordenamiento que presentamos es quizá el más ampliamente conocido entre los estudiantes que se inician en la programación. Una de las características de este ordenamiento es que es fácil de entender y programar. Aunque, es uno de los algoritmos mas ineficiente.

La idea básica subyacente en el ordenamiento de burbuja es pasar a través del arreglo de datos varias veces en forma secuencial. Cada paso consiste en la comparación de cada elemento en el arreglo con su sucesor (x[i] con  x[i+1]) y el intercambio de los dos elementos si no están en el orden correcto. Considérese el siguiente arreglo de datos:

25 57 48 37 12 92 86 33

En el primer paso se realizan las siguientes operaciones:

x[0] con x[1] (25 con 57)  no intercambio.

x[1] con x[2] (57 con 48)      intercambio.

x[2] con x[3] (57 con 32)      intercambio.

x[3] con x[4] (57 con 12)      intercambio.

x[4] con x[5] (57 con 92)  no intercambio.

x[5] con x[6] (92 con 86)      intercambio.

x[6] con x[7] (92 con 33)      intercambio.

Así después del primer paso, el arreglo está en el siguiente orden:

25 48 37 12 57 86 33 92

Observe que después del primer paso, el elemento mayor (en este caso 92) está en la posición correcta dentro del arreglo. En general x[n-i] estará en su posición correcta después de la iteración i. El método se lama ordenamiento de burbuja porque cada número ``burbujea'' con lentitud hacia su posición correcta. El conjunto completo de iteraciones es:

iteración 0:                       25 57 48 37 12 92 86 33

iteración 1:                       25 48 37 12 57 86 33 92

iteración 2:                       25 37 12 48 57 33 86 92

iteración 3:                       25 12 37 48 33 57 86 92

iteración 4:                       12 25 37 33 48 57 89 92

iteración 5:                       12 25 33 37 48 57 89 92

\begin{verbatim}
/* 
 * File:   burbuja.c
 * Author: felix
 *
 * Created on 16 de mayo de 2012, 12:39
 */

#include <stdio.h>
#include <stdlib.h>

void burbuja(float *a, int N) {
    int i, j;
    float aux;
    
    do{
        j=0;
        for(i=0; i<N-1; i++) {
            if(a[i] > a[i+1]){
                aux    = a[i];
                a[i]   = a[i+1];
                a[i+1] = aux;
                j++;
            }
        }
        
    }while (j >0);
}

void imprime(float *a, int N) {
    int i;
    
    for(i=0; i<N; i++)
        printf("%f ", a[i]);
    printf("\n");
}

int main(int argc, char** argv) {
    
    float a[] = {1, 6, 4, 0, 3, -2};
    
    imprime(a, 6);
    burbuja(a, 6);
    imprime(a, 6);
    
    return (EXIT_SUCCESS);
}
\end{verbatim}
