Máximo, mínimo, media, y suma de los componentes de un array no ordenado

Detalles

TrivialidadesEstas son cuatro operaciones básicas que se suelen realizar a menudo sobre un array, o en general, una lista sin orden, es decir, un conjunto de elementos (enteros, cadenas o cualquier otra cosa) los cuales se colocan uno tras otro, pero sin un órden concreto en su colocación.

Para obtener el elemento más grande, el más pequeño, la media aritmética o la suma de todos los valores, no tenemos más remedio que recorrer tooooda la lista.

Obtener estos cuatro valores de un vector no tiene misterio alguno.

Vamos con el máximo y el mínimo. Saber cuál es el elemento más grande o más pequeño de un array unidimensional no ordenado (o una lista, en general) implica recorrer todo el vector, ya que en ningún momento podemos saber qué elemento es el mayor o el menor de todos ellos. Siempre podría ser el último.

MÁXIMO.

Dado que es necesario recorrer todo el array, y éste tendrá una longitud concreta y conocida, el bucle ideal para ésto es un for.

El tipo del array puede ser cualquiera, pero eso si, debe cumplir una condición: sus elementos deben ser ordenables por algún criterio. Es decir, se le debe poder aplicar un operador o función relacional (por ejemplo ">") que nos compare dos elementos, y nos diga si uno es mayor que otro. Por ejemplo, esto ocurre con los enteros, los reales... incluso las cadenas (que normalmente podemos comparar lexicográficamente). En caso de otros tipos más complejos (por ejemplo, una clase que represente a coches, o a casas, o a perros...) será necesario construir una función u operador relacional.

Bueno... nostros trabajaremos con enteros, que suele ser lo más normal en este tipo de ejemplos. La estrategia es sencilla. Por ejemplo, para conocer el máximo de un vector de enteros inicializaremos una variable al valor más negativo que podamos encontrar (Casi todos los lenguajes disponen de una constante que nos da ese valor, el entero más negativo que una variable de tipo entero puede contener. En C se llama MAXINT. En C# es un miembro de la clase int: int.MinValue). Después iremos recorriendo el array elemento por elemento. Si el elemento en cuestión es mayor que el que teníamos en nuestra variable, modificamos esa variable asignándole el mismo valor que el elemento del array que estamos examinando. Una vez recorrido todo el array, nuestra variable contiene el valor del elemento que es mayor o igual a cualquier otro, es decir, el máximo.

Debemos tener en cuenta posibles excepciones. En este caso, si el vector de entrada estuviera completamente vacío. ¿Qué debemos devolver? Es necesario señalizar esta situación anómala de alguna manera.

Tenemos dos opciones para esto: Si estamos seguros de que el vector de entrada no contiene ningún elemento que sea igual al más negativo (en nuestro caso, int.MinValue), podemos no hacer nada concreto, y si el vector está completamente vacío, devolver ese valor. Fuera del algoritmo puede comprobarse ese valor y tomarse como una situación anómala.

En caso de que los enteros del vector pudieran tomar cualquier valor, también podrían tomar el más negativo, y sería posible (raro, pero posible) que además ese elemento fuera el máximo. En ese caso, deberíamos recurrir a construir una excepción para señalizar esto y lanzarla.

Vamos a suponer el primer caso: nuestro vector no puede contener a int.MinValue.

En ese caso, el algoritmo en C# podría ser algo así:

1
2
3
4
5
6
7
8
9
10
11
12
int maximo(int[] v)
{
   int resultado=int.MinValue;
   for(int i=0;i<v.length;i++) 
   {
      if (v[i] > resultado)
      {
         resultado = v[i];
      }
   }
return resultado;
}

Si utilizas un lenguaje como Java o C# que disponen de un bucle foreach, también es idóneo para esta tarea, ya que el bucle foreach recorrerá todos los elementos del array

1
2
3
4
5
6
7
8
9
10
11
12
int maximo(int[] v)
{
   int resultado=int.MinValue;
   foreach(int k in v) 
   {
      if (k > resultado)
      {
         resultado = k;
      }
   }
return resultado;
}

A menudo, a los arrays se les dimensiona dándoles más espacio del que en realiadad necesitamos, y se acompañan siempre de un entero que nos indica cuántos elementos del array estamos utilizando. Por ejemplo, si tenemos que almacenar una cantidad de enteros que puede variar a lo largo de nuestra aplicacion, a menudo escogemos un tamaño relativamente grande para el array (100 elementos, 1000 elementos... un número al que sepas que no vas a llegar), y acompañamos al vector siempre de una variable para saber cuántos de esos elementos estamos utilizando realmente.

Si éste es nuestro caso, tendremos que modificar ligeramente el algoritmo, para que busque el máximo sólo entre los elementos utilizados, y no entre todos los elementos del array.

En este caso, no podríamos utilizar un bucle foreach, ya que éste recorre todos los elementos del vector, y no sólo los que nos interesan.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//en este caso, sólo recorremos
//los n primeros elementos del
//array v
int maximo(int[] v, int n)
{
   int resultado=int.MinValue;
   for(int i=0;i<n;i++) 
   {
      if (v[i] > resultado)
      {
         resultado = v[i];
      }
   }
return resultado;
}

En lenguajes que admiten sobrecarga de métodos, ésta versión del método y una de las anteriores pueden coexistir en la misma clase, ya que admiten distinto número de parámetros. En lenguajes que no lo admitan, deberemos utilizar nombres distintos.

MÍNIMO

La estrategia y consideraciones para hallar el mínimo son exactamente las misma, pero en lugar de asignar a nuestra variable resultado el menor valor posible, asignaremos el mayor posible. Recorreremos el vector, y si encontrarmos un resultado menor nos quedaremos con él.

1
2
3
4
5
6
7
8
9
10
11
12
int minimo(int[] v, int n)
{
   int resultado = int.MaxValue;
   for(int i=0;i<n;i++)
   {
      if (v[i] < resultado)
      {
          resultado = k;
      }
   }
return resultado;
}

SUMA

La estrategia es sencilla. Inicializaremos una variable a 0. Recorremos los elementos del vector, y sumamos a esa variable cada uno de ellos.

1
2
3
4
5
6
7
8
9
int suma(int[] v, int n)
{
   int resultado = 0;
   for (int i = 0; i < n; i++)
   {
      resultado += v[i];
   }
return resultado;
}

MEDIA

Finalmente, la media aritmética se define como suma de una serie de valore dividido por la cantidad de valores que hemos sumado. Aparentemente podría ser similar al algoritmo de la suma, solo que el resultado lo dividimos por el número de valores que hay.

1
2
3
4
5
6
7
8
9
int media(int[] v, int n)
{
   int resultado = 0;
   for (int i = 0; i < n; i++)
   {
      resultado += v[i];
   }
return resultado/n;
}

Pero habría que tener en cuenta una consideración adicional: ¿Qué ocurre si n es 0? Pues que no se puede calcular la media, porque no se puede dividir por 0. Es bastante pertinente captar esa situación, si no, nuestro programa se interrumpiría en esa línea.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int media(int[] v, int n)
{
   int resultado = 0;
   for (int i = 0; i < n; i++)
   {
      resultado += v[i];
   }
   if (n < 0)
   {
      //provocará error si n=0
      resultado/n;
   }
   else
   {
      //un valor que indique
      //una situación excepcional, o
      //lanzar una excepción
      resultado=0;
   }
return resultado;

Por último, sólo comentar que todos estos algoritmos tienen una complejidad lineal, tanto en el peor como en el mejor caso es decir O(n) y Ω(n).

 


Actualización: Me han comentado que a la hora de calcular el máximo (o el mínimo), en lugar de suponer que el máximo es un entero muy grande (o muy grande en negativo), podríamos suponer que el primer elemento es el máximo (o el mínimo), y entonces, empezar el bucle a partir del segundo elemento. Vale... pero entonces ¿Qué pasaría si nos pasan un array completamente vacío?... Pues un error de ejecución por índices del array fuera de rango ;-)

   

Síguenos  

   

¿Dónde estoy?  

Estás en La tecla de ESCAPE, un sitio web personal en el que nos gusta hablar de algoritmos, metodología de la programación, personajes de informática, tecnología, ingeniería del software, internet, y cualquier otra tontería que se nos ocurra.

[{modal url=url=index.php?option=com_content&view=article&id=1301}Leer más / Términos de uso (ToS){/modal}]

   

¿Quién está en línea?