Arreglos Unidimensionales

Arreglos unidimensionales
• Actualización y borrado
Insertar un elemento en el arreglo
6
2

4

8

0

1

2

2

4

6

8

10

0

1

2

3

4

A[j+1]=A[j]

10
+1

3

+1

Arreglos unidimensionales
• Actualización y borrado
Borrar un elemento en el arreglo
Eliminar

2

4

6

8

10

0

1

2

3

4

-1

-1

2

4

8

10

01

2

3

A[j]=A[j+1]

Arreglos unidimensionales
• Ordenamiento
Método Burbuja
Supongamos que tenemos una función flota()
que “flota” el elemento más pequeño arriba (al
inicio del arreglo) y los elemento pesados
hacia abajo (hasta el final del arreglo).
Ejemplo: int a[] = {12,8, 4, 9, 3 };
flota(a);

a

8 4 9 3 12

Arreglos unidimensionales
• Ordenamiento
Método BurbujaVemos un ejemplo sencillo. Supongamos que queremos
ordenar estos valores con el algoritmo de la burbuja: 45,
52, 21, 37, 49, así pues, n=5
1ª pasada: comparamos cada uno de los cuatro primeros
(n-1) con los que le siguen. Si un elemento no está en
orden con respecto al siguiente, los intercambiamos de
sitio y seguimos. El elemento de mayor valor (52) irá
"ascendiendo" hasta la últimaposición.

Arreglos unidimensionales
• Ordenamiento
Método Burbuja
45, 52, 21, 37, 49 → Comparar 45 y 52. (1º y 2º) Están en
orden. Seguimos.
45, 52, 21, 37, 49 → Comparar 52 y 21. (2º y 3º) No están en
orden. Intercambio.
45, 21, 52, 37, 49 → seguimos
45, 21, 52, 37, 49 → Comparar 52 y 37 (3º y 4º). No están en
orden. Intercambio.
45, 21, 37, 52, 49 → seguimos
45, 21, 37, 52, 49 →Comparar 52 y 49. (4º y 5º). No están en
orden. Intercambio.
45, 21, 37, 49, 52 → Ya hemos terminado esta pasada.
45, 21, 37, 49, 52 → El 5º elemento ya está en su sitio.

Arreglos unidimensionales
• Ordenamiento
Método Burbuja
• 2ª pasada: comparamos cada uno de los tres primeros (n-2) con los que le
siguen. No llegamos a hacer comparaciones que involucren al 5º
elemento, porque la primerapasada hizo que el mayor de todos los
elementos ocupara la última posición, con lo cual, sabemos que ese ya
está en su sitio. Trabajaremos sólo con los cuatro que quedan.
45, 21, 37, 49, 52 → Comparar 1º y 2º. No están en orden. Intercambio.
21, 45, 37, 49, 52 → seguimos
21, 45, 37, 49, 52 → Comparar 2º y 3º. No están en orden. Intercambio.
21, 37, 45, 49, 52 → seguimos
21, 37, 45, 49, 52 →Comparar 3º y 4º. Están en orden. Pasada terminada.
21, 37, 45, 49, 52 → El 4º elemento ya está en su sitio. (Fíjate en que el
array ya está en orden, pero algoritmicamente, eso no lo sabemos).

Arreglos unidimensionales
• Ordenamiento
Método Burbuja
3ª pasada: Comparamos cada uno de los dos primeros (n-3) con los
siguientes.
21, 37, 45, 49, 52 → 1º y 2º. Están en orden. Seguimos.
21,37, 45, 49, 52 → 2º y 3º. Están en orden. Pasada terminada.
21, 37, 45, 49, 52 → Ya tenemos tres en orden.

Arreglos unidimensionales
• Ordenamiento
Método Burbuja
• 4ª y última pasada: Comparamos el primero con el segundo.
21, 37, 45, 49, 52 → 1º y 2º están en orden. Pasada terminada.
21, 37, 45, 49, 52 → Ya tenemos los cuatro últimos en orden.
21, 37, 45, 49, 52 → Así pues, el primerotambién lo está.

Arreglos unidimensionales
• Búsquedas
Búsqueda secuencial
La búsqueda secuencial busca un elemento de una lista utilizando
un valor destino llamado clave.
En una búsqueda secuencial (a veces llamada búsqueda lineal ), los
elementos de una lista o vector se exploran (se examinan) en
secuencia, uno después de otro. La búsqueda secuencial es
necesaria, por ejemplo, si sedesea encontrar la persona cuyo
número de teléfono es 958-220000 en un directo-rio o listado
telefónico de su ciudad. Los directorios de teléfonos están
organizados alfabéticamente por el nombre del abonado en lugar
de por números de teléfono, de modo que deben explorarse todos
los números, uno después de otro, esperando encontrar el número
958-220000.

Arreglos unidimensionales
•...