ARREGLOS

MÉTODO DE ORDENAMIENTO

MÉTODO DE BÚSQUEDA

Material con fines didácticos del Prof. Daniel Valera

Compilado por: MSc. Ing. Sullin Santaella
 Arreglos
Arreglos (Definición):
Un arreglo es una colección de posiciones de almacenamiento de datos donde cada una
tiene el mismo tipo de datos y el mismo nombre. Cada posición de almacenamiento en un
arreglo es llamada elemento del arreglo. Por que usar arreglos en un programa?, se puede
responder a esto mediante un ejemplo. Si se están llevando las cuentas anuales de un negocio,
se podrían llevar 12 carpetas (una para cada mes) para almacenar sus recibos mensuales, pero
sería más conveniente tener una sola carpeta con 12 compartimientos.
Llevando este ejemplo a la programación de una computadora, imagínese que está
diseñando un programa para llevar los gastos totales del negocio, en este programa se
podría declarar 12 variables separadas, cada una para los totales de gasto del mes. Este
enfoque es similar a tener 12 carpetas separadas, cada una para el total de gastos del mes. Sin
embargo, la buena práctica de la programación utilizaría un arreglo con 12 elementos,
guardando el total de cada mes en el elemento del arreglo correspondiente. Este enfoque
es comparable al archivado de los recibos en una carpeta de 12 compartimientos. Acá una
representación gráfica:

12 Variables
Individuales
Un Arreglo
 Los arreglos también llamados vectores o tablas unidimensionales, son estructuras de
datos caracterizadas por:
Una colección de datos del mismo tipo.
Referenciados mediante un mismo nombre.
Almacenados en posiciones de memoria físicamente contiguas, de forma que, la
dirección de Memoria más baja corresponde a la del primer elemento, y la dirección de
memoria más alta Corresponde a la del último elemento.
La declaración de un array se realiza según la siguiente sintaxis:
tipo_de_las_variables nombre[cantidad de elementos];

Donde:
tipo_de_las variables: indica el tipo de los datos almacenados por el arreglo. Recordemos
que todos los elementos del vector son forzosamente del mismo tipo. Debe aparecer
necesariamente en la declaración, puesto que de ella depende el espacio de memoria que
se reservara para almacenar el vector.
nombre: es un identificador que usaremos para referiremos tanto al arreglo como un todo,
como a cada uno de sus elementos.
cantidad de elementos: es una expresión entera constante que indica el número de
elementos que contendrá el vector. El espacio ocupado por un vector en memoria se obtiene
como el producto del número de elementos que lo componen y el tamaño de cada uno de
estos.

Representación Gráfica de un Vector

El tamaño del arreglo viene definido por el número de elementos que pueda contener (si se
van a almacenar 5 datos será entonces de tamaño 5), cada elemento del arreglo se puede ubicar
por un respectivo índice, siendo la primera posición el índice 0 del arreglo y la última el
tamaño del vector menos 1 (n-1). Por ejemplo si definimos un arreglo de variables enteras:
int variable1[5];
Un arreglo de tamaño 5 y Desde el punto de vista lógico lo podríamos imaginar de esta
forma: Índices -> 0 1 2 3 4 <- Tamaño - 1
Y en cada parte del arreglo se podría almacenar un entero teniendo como máximo un
total de 5 enteros.
Acá otros ejemplos de declaración de arreglos: Por ejemplo:
int var1[10];
char nombre[50];
float numeros[200];
long double cantidades[25];

Operaciones Básicas con Arreglos:

Si tomamos el primer caso, estamos declarando un array de 10 variables enteras, cada una
de ellas quedará individualizada por el subíndice que sigue al nombre del mismo es decir:
var1[0] , var1[1] , … , hasta var1[9] .
Nótese que la CANTIDAD de elementos es 10, pero su numeración va de 0 a 9 , y no de 1
a 10 . En resumen un array de N elementos tiene subíndices válidos entre 0 y N - 1. Cualquier
otro número usado como subíndice, traerá datos de otras zonas de memoria, cuyo contenido es
impredecible. Se puede referenciar a cada elemento, en forma individual, tal como se ha hecho
con las variables anteriormente, por ejemplo:
var1[5] = 40 ;
contador = var1[3] + 7 ;
if(var1[0] >>= 37)
..................

También es posible utilizar como subíndice expresiones aritméticas, valores enteros

retornados por funciones, entre otros. Así podríamos escribir:
var1[8] = var1[ i + j ] ;

Por supuesto los subíndices resultantes de las operaciones tienen que estar acotados a
aquellos para los que el array fue declarado y ser enteros.

Inicialización de Arreglos:
La inicialización de los arrays sigue las mismas reglas que vimos para los otros tipos de
variables, es decir: Si se declaran como globales (afuera del cuerpo de todas las funciones)
cada uno de sus elementos será automáticamente inicializado a cero. Si en cambio, su
declaración es local a una función, no se realiza ninguna inicialización, quedando a cargo del
programa cargar los valores de inicio.
La inicialización de un array local, puede realizarse en su declaración, dando una lista de
valores iníciales:
int numero[8] = { 4 , 7 , 0 , 0 , 0 , 9 , 8 , 7 } ;
Obsérvese que la lista está delimitada por llaves. Otra posibilidad, sólo válida cuando se
inicializan todos los elementos del array, es escribir:
int numero[] = { 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , } ;
Donde se obvia la declaración de la cantidad de elementos, ya que está implícita en la
lista de valores constantes.
También se puede inicializar parcialmente un array, por ejemplo:
int numero[10] = { 1 , 1 , 1 } ;
En éste caso los tres primeros elementos del mismo valdrán 1, y los restantes cero en el
caso que la declaración sea global, ó cualquier valor impredecible en el caso de que sea local.

Clasificación de los Arreglos:

Los arreglos se pueden clasificar en 3 tipos distintos, comenzaremos hablando del tipo
abstracto de datos arreglos, tanto de una (vectores), dos (matrices) o múltiples dimensiones.

Vectores
En muchas ocasiones, antes de usar un vector (una tabla en general) por primera vez, es
necesario dar a sus elementos un valor inicial. La manera más habitual de inicializar un vector
en tiempo de ejecución consiste en recorrer secuencialmente todos sus elementos y darles el
valor inicial que les corresponda. Veámoslo en el siguiente ejemplo, donde todos los
elementos de un vector de números enteros toman el valor 0:
 #define TAM 100
int main()
{
int vector[TAM], i;
for (i= 0; i< TAM; i++)
vector[i] = 0;
return 0;
}
Nótese que el bucle recorre los elementos del vector empezando por el elemento 0 (i=0) y
hasta el elemento TAM-1 (condición i < TAM).
Para entender con mayor claridad la practicidad y funcionalidad de los arreglos se muestra
el siguiente ejemplo: Suponiendo que tenemos una cantidad n de valores y queremos
determinar cuál de ellos es el mayor. Suponiendo que no tenemos conocimientos del uso de
arreglos, en caso de que se nos presentase el problema anterior tendríamos que hacer algo
como lo que se muestra a continuación.
/* Ejemplo : el mayor de tres números enteros */
#include <iostream>
using namespace std;
int main()
{
int a,b,c;
cout << "Dime un valor para A : " <<endl;
cin >> a;
cout << "Dime un valor para B : " <<endl;
cin >> b;
cout << "Dime un valor para C : " <<endl;
cin >> c;
if ((a > b) && (a > c)) cout << "El mayor es:"<<a << endl;
else if ((b > a) && (b > c)) cout << "El mayor es: " <<b << end;
else cout << "El mayor es:"<<c <<endl;
return 0;
}
 En este ejemplo se muestra un programa ineficiente, y además difícil de ampliar, para
encontrar el mayor de tres números. Como podemos ver para encontrar el mayor de más de
tres números necesitaríamos reescribir el programa casi por completo. Pero si hacemos
uso de arreglos podemos mejorar un poco esto, por lo menos facilitando la reutilización y
mantenimiento del programa.
/* Ejemplo : el mayor de cuatro números enteros */
#include <iostream>
using namespace std;
int main()
{
int n = 4;
int a[n],c,mayor;
mayor = 0;
for (c = 0; c < n; c++)
{
cout <<"Dime un valor : " << endl;
cin >> a[c];
}
for (c = 0; c < n; c++)
{
if ((a[c] > mayor) || (c == 0))
mayor = a[c];
}
cout << "El mayor es : " << mayor << endl;
return 0;
}
Métodos de Ordenamiento
La ordenación o clasificación es el proceso de organizar datos en algún orden o
secuencia específica, tal como creciente o decreciente, para datos numéricos, o alfabéticos,
para datos de caracteres. Los métodos de ordenación más directos son los que se realizan en el
espacio ocupado por el array. El método más popular es el método de la burbuja:
 Método De Intercambio O De Burbuja:
Se basa en el principio de comparar pares de elementos adyacentes e intercambiarlos
entre si hasta que estén todos ordenados.
Supongamos que se desea clasificar en orden ascendente el vector o lista,

9, 8, 0, 2, 5, 1, 3, 2, 9

A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8]

Los pasos a dar son:

-Comparar A[0] y A[1] si están en orden, se mantienen como están, en caso
contrario se intercambian entre sí.
-A continuación se comparan los elementos 1 y 2; de nuevo se intercambian si es necesario.
-El proceso continua hasta que cada elemento del vector ha sido comparado con sus
elementos adyacentes y se han realizado los intercambios necesarios.
Ejemplo Visual del ordenamiento de burbuja
Iniciando el orden desde el primer elemento
Ahora con el segundo elemento... Ahora con el tercer elemento

El quinto elemento…
Así se van ordenando todos, ahora se
ordena el cuarto elemento:
El sexto… El séptimo y octavo elemento…

Ya no tiene que comparar el octavo con el noveno porque se supone que si todos los números
están ordenados hasta el octavo elemento, el último debe ser el mayor a todos. El arreglo
final, ordenado es así:

Ejemplo Práctico
/*Ordenamiento Burbuja */
#include <iostream>
using namespace std;
#define TAM 9
int main()
{
int a[TAM] = { 9, 8, 0, 2, 5, 1, 3, 2, 9};
int i, pasada, aux;
cout << "Datos en el orden inicial:"<< endl;
for(i=0;i<=TAM-1;i++)
cout <<a[i] << endl;
for(pasada=1;pasada<=TAM-1;pasada++) /*pasadas*/
for (i=0;i<=TAM-2;i++)
 if (a[i]>a[i+1]) /*comparación */
{
/*intercambio*/
aux=a[i];
a[i] = a[i+1];
a[i+1] = aux;
}
cout<< "Datos ordenados en sentido ascendente:" << endl;
for (i=0;i<=TAM-1;i++ )
cout << a[i] << endl;
return 0;
}

Métodos de Búsqueda
La búsqueda es una operación que tiene por objeto la localización de un elemento dentro de
la estructura de datos (arreglo). A menudo un programador estará trabajando con
grandes cantidades de datos almacenados en arreglos y pudiera resultar necesario determinar si
un arreglo contiene un valor que coincide con algún valor clave o buscado.

Búsqueda Secuencial
Este algoritmo compara uno a uno los elementos del arreglo hasta recorrerlo por
completo indicando si el número buscado existe. Su implementación es la siguiente:
#include <iostream>
using namespace std;
#define TAM 10
int main()
{
int a[TAM], temp, i, j, num, c, posicion;
for (c = 0; c < TAM; c++) //llenar el arreglo con números
{
cout <<"Dime un valor : " << endl;
cin >> a[c];
 }
cout << "Numero a buscar? "<<endl;
cin >>num;
for (i=0; i< TAM; i++)
if (a[i] == num)
{
temp =1;
posicion= i;
}
else temp = 0;
if (temp==1)
cout << "Valor encontrado en la posicion:" << posicion << endl;
else if (temp == 0) cout << "No existe" <<endl;
cout << "El arreglo era:" << endl;
for (i=0; i< TAM; i++)
cout << a[i] <<endl;
return 0;
}

Búsqueda Binaria
Este algoritmo permite buscar de una manera más eficiente un dato dentro de un arreglo,
para hacer esto se determina el elemento central del arreglo y se compara con el valor que se
está buscando, si coincide termina la búsqueda y en caso de no ser así se determina si el dato
es mayor o menor que el elemento central, de esta forma se elimina una mitad del arreglo junto
con el elemento central para repetir el proceso hasta encontrarlo o tener solo un elemento en el
arreglo. Para poder aplicar este algoritmo se requiere que el arreglo este ordenado. Su
implementación es la siguiente:
#include <iostream>
using namespace std;
#define TAM 15
int main()
{
int a[TAM], busca, temp, bajo, alto, central, c, i, j;
for (c = 0; c < TAM; c++) //llenar el arreglo con números
{
cout <<"Dime un valor : " << endl;
cin >> a[c];
}
//Implementacion de Ordenamiento por burbuja de menor a mayor
cout << "Ordenando arreglo..." << endl;
for (int j=1; j <= TAM; j++)
for (i=0; i< TAM-1; i++)
if (a[i] > a[i+1])
{
temp = a[i]; a[i] = a[i+1]; a[i+1] = temp;
}
//Implementacion de busqueda binaria
cout << "Introduce un numero a buscar: " << endl;
cin >> busca;
bajo = 0;
alto = TAM-1;
central = (bajo+alto)/2;
while (bajo < alto && busca != a[central])
{
if(busca > a[central]) bajo = central+1;
else alto = central-1;
central=(bajo+alto)/2;
}
if (busca == a[central]) cout << "encontrado en posicion: " << central<< endl;
else
cout << "no existe" << busca;
cout <<"El arreglo ordenado queda:"<< endl;
for (i=0; i< TAM; i++)
cout << a[i] << endl;
return 0;
}

Ejercicios de Prelaboratorio
Arreglos en C++
A continuación se presentan los enunciados del problema y su análisis, revisar y desarrollar el
programa en lenguaje C++, en el laboratorio de computación se procederá a compilar, corregir y
ejecutar el programa.

1) Dado un vector de 5 celdas, cargar números enteros en cada posición de dicho vector
con un número leído. El vector está declarado como valor entero.
ALGORITMO
VARIABLES
ENTERO numero [1. .. 5];
ENTERO indice;
INICIO
PARA indice = 1 HASTA 5 INCREMENTO 1
ESCRIBIR ( “Introduce un numero” );
LEER ( numero[indice] );
FIN_PARA
FIN
FIN_ALGORITMO

2) Leer una secuencia de 20 números enteros almacenados en un vector y mostrar la

posición donde se encuentra el mayor leído.
ALGORITMO
VARIABLES
ENTERO indice;
ENTERO mayor ;
ENTERO mayor_indice;
ENTERO numero [1. .. 20];
 INICIO
PARA indice = 1 HASTA 20 INCREMENTO 1
ESCRIBIR ( “Introduce un numero” ) ;
LEER ( numero[indice] ) ;
FIN_PARA
mayor = numero [1] ;
mayor_indice = 1;
PARA indice = 2 HASTA 20 INCREMENTO 1
SI ( numero[indice] > mayor ) ENTONCES
mayor = numero[indice] ;
mayor_indice = indice;
FIN_SI
FIN_PARA
ESCRIBIR ( “El mayor ocupa la posición:” + mayor_indice ) ;
FIN
FIN_ALGORITMO

3) Dado dos vectores A y B de 15 elementos cada uno obtener un vector C donde la

posición i se almacena la suma de A[i] + B[i] y mostrar el mayor de los C[i].
ALGORITMO
VARIABLES
ENTERO A[1....15] ;
ENTERO B[1. .. 15] ;
ENTERO C[1. .. 15] ;
ENTERO indice;
ENTERO suma;
INICIO
(* Cargar valores al arreglo A *)
PARA indice = 1 HASTA 15 INCREMENTO 1
ESCRIBIR ( “Introduce un numero” ) ;
LEER ( numero[indice] ) ;
FIN_PARA
 (* Cargar valores al arreglo B *)
PARA indice = 1 HASTA 15 INCREMENTO 1
ESCRIBIR ( “Introduce un numero” ) ;
LEER ( numero[indice] ) ;
FIN_PARA
(* Sumar los valores del arreglo A y B en C *)
PARA indice = 1 HASTA 15 INCREMENTO 1
C[indice] = A[indice] + B[indice] ;
FIN_PARA
PARA indice = 1 HASTA 15 INCREMENTO 1
ESCRIBIR ( C[indice] ) ;
FIN_PARA
mayor = C[1] ;
mayor_indice = 1;
(* Buscar el mayor valor cargado en el arreglo C *)
PARA indice = 2 HASTA 15 INCREMENTO 1
SI ( C[indice] > mayor ) ENTONCES
mayor = C[indice] ;
mayor_indice = indice;
FIN_PARA
ESCRIBIR ( “El mayor ocupa la posición:” + mayor_indice ) ;
FIN
FIN_ALGORITMO

4) Dado una secuencia de números leídos y almacenados en un vector A mostrar dichos

números en orden.
ALGORITMO
VARIABLES
ENTERO intercambio ;
ENTERO vector[1. ..5] ;
ENTERO intermedio;
ENTERO indice;
 FIN_VARIABLES
INICIO
PARA indice = 1 HASTA 15 INCREMENTO 1
ESCRIBIR ( “Introduce un numero” ) ;
LEER ( vector[indice] ) ;
FIN_PARA
REPETIR
intercambio = 0
PARA indice = 1 HASTA 14 INCREMENTO 1
SI (vector[indice] > vector[indice + 1]) ENTONCES
intermedio = vector[indice] ;
vector[indice] = vector[indice + 1] ;
vector[indice + 1 ] = intermedio;
intercambio = 1;
FIN_SI
FIN_PARA
HASTA (intercambio = 0)
PARA indice = 1 HASTA 15 INCREMENTO 1
ESCRIBIR ( “El vector ordenado es:” + vector[indice] ) ;
FIN_PARA
FIN_INICIO
FIN_ALGORITMO

5) Leer 20 números y mostrar la suma de todos. Se utiliza arreglos.

ALGORITMO
VARIABLES
numero [1. .. 20] de arreglos: ENTEROS
indice, suma: ENTERO
INICIO
suma = 0;
[* Cargar un número en arreglo numero *]
PARA indice = 1 HASTA 20 INCREMENTO 1
 ESCRIBIR ( “Introduce un numero” );
LEER ( numero[indice] );
FIN_PARA
[* Imprimir un número cargado de un arreglo numero *]
[* Se acumula en SUMA *]
PARA indice = 1 HASTA 20 INCREMENTO 1
suma = suma + numero[indice];
FIN_PARA
ESCRIBIR ( “La suma total es:” + suma );
FIN
FIN_ALGORITMO