Arrays · Arreglos
| English | Español |
|---|---|
| array/əˈreɪ/ | array |
| element/ˈelɪmənt/ | elemento |
| index/ˈɪndeks/ | índice |
| lower bound/ˈləʊə baʊnd/ | límite inferior |
| upper bound/ˈʌpə baʊnd/ | límite superior |
| dimension/daɪˈmenʃn/ | dimensión |
| nested loops/ˈnestɪd luːps/ | bucles anidados |
| linear search/ˈlɪnɪə sɜːtʃ/ | búsqueda lineal |
| bubble sort/ˈbʌbl sɔːt/ | bubble sort |
Seat 14C
- A cinema has 300 seats. Its booking system does not have 300 variables called
Seat1A,Seat1B,Seat1C. It has one array 数组, and your ticket is an address into it: row 14, seat C. - One name, hundreds of values, each found by a number. Add a row and the code does not change; loop over the numbers and you have checked every seat.
- Almost every Paper 2 algorithm walks an array: searching it, summing it, sorting it, finding its largest value.
- This lesson is the vocabulary, the declarations, and the four algorithms the examiner asks for in pseudocode and in words.
Asiento 14C
- Una sala de cine tiene 300 asientos. Su sistema de reservas no utiliza 300 variables denominadas
Seat1A,Seat1B,Seat1C. Utiliza un array 数组, y tu entrada es una dirección dentro de él: fila 14, asiento C. - Un nombre, cientos de valores, cada uno identificado por un número. Se añade una fila y el código no cambia; se recorre con bucles los números y se han verificado todos los asientos.
- Casi todos los algoritmos del Paper 2 recorren un array: lo buscan, lo suman, lo ordenan o encuentran su valor más grande.
- Esta lección trata el vocabulario, las declaraciones y los cuatro algoritmos que pide el examinador en pseudocódigo y en palabras.
The vocabulary
- An array is a data structure holding a fixed number of elements 元素 of the same data type under one identifier, each reached by an index 索引.
- The lower bound 下界 and upper bound 上界 are the first and last valid index. The number of elements is upper bound − lower bound + 1.
- The dimension 维度 is how many indices an element needs: one for a list, two for a table.
- In
ThisArray[n] ← 42the array has one dimension, the index is theINTEGERvariablen, and the element at that index receives42.
One identifier, an index for each element, bounds at both ends
El vocabulario
- Un array es una estructura de datos que almacora un número fijo de elementos 元素 del mismo tipo de datos bajo un único identificador, cada uno accesible mediante un índice 索引.
- El límite inferior 下界 y el límite superior 上界 son el primer y último índice válido. El número de elementos es límite superior − límite inferior + 1.
- La dimensión 维度 es cuántos índices necesita un elemento: uno para una lista, dos para una tabla.
- En
ThisArray[n] ← 42el array tiene una dimensión, el índice es la variableINTEGERn, y el elemento en ese índice recibe el valor42.
Un identificador, un índice para cada elemento, límites en ambos extremos
An array stores: · Una matriz almacena:
An array is an ordered collection of same-type items accessed by index. (A record groups different types.) · Una matriz es una colección ordenada de elementos del mismo tipo que se acceden por índice. (Un registro agrupa diferentes tipos.)
An array is a data structure holding many values of the ______ type under one name. · Una matriz es una estructura de datos que contiene muchos valores del tipo ______ bajo un solo nombre.
Each value is reached by its index. · Cada valor se accede mediante su índice.
DECLARE Marks : ARRAY[0:99] OF INTEGER declares an array of ____ elements. · DECLARE Marks : ARRAY[0:99] OF INTEGER declara una matriz de ____ elementos.
Upper bound minus lower bound plus one: 99 − 0 + 1 = 100. Both bounds are valid indices. · Límite superior menos límite inferior más uno: 99 − 0 + 1 = 100. Ambos límites son índices válidos.
Worked example: declaring the array a task needs
- A declaration needs the identifier, the bounds and the data type.
- 120 readings that may have a decimal place:
DECLARE Data : ARRAY[1:120] OF REAL - A table of 150 rows and two columns of text:
DECLARE Names : ARRAY[1:150, 1:2] OF STRING - Say the count if asked:
[0:99]holds 100 elements, not 99.
Ejemplo resuelto: declarar el array que necesita una tarea
- Una declaración requiere el identificador, los límites y el tipo de datos.
- 120 lecturas que pueden tener decimales:
DECLARE Data : ARRAY[1:120] OF REAL - Una tabla de 150 filas y dos columnas de texto:
DECLARE Names : ARRAY[1:150, 1:2] OF STRING - Si se pregunta por el conteo:
[0:99]contiene 100 elementos, no 99.
Which declaration holds a table of 150 rows and 2 columns of text? · ¿Cuál declaración contiene una tabla de 150 filas y 2 columnas de texto?
Two dimensions, each with a lower and upper bound, and the element type. The second option is one long list; the third has no type; the fourth has no lower bounds. · Dos dimensiones, cada una con un límite inferior y superior, y el tipo de elemento. La segunda opción es una lista larga; la tercera no tiene tipo; la cuarta no tiene límites inferiores.
Processing a 1-D array
- A
FORloop from the lower bound to the upper bound visits every element once. - For a sum, count, maximum or minimum, set a running variable before the loop and update it inside.
Procesamiento de un array de 1D
DECLARE Names : ARRAY[1:5] OF STRING
Names[3] ← "Cara"
FOR i ← 1 TO 5
OUTPUT Names[i]
NEXT i
- Un bucle
FORdesde el límite inferior hasta el superior visita cada elemento una vez. - Para una suma, cuenta, máximo o mínimo, inicialice una variable acumuladora antes del bucle y actualízela en su interior.
2-D arrays
- The first index is the row, the second the column. Nested loops 嵌套循环 visit every cell: the outer loop over rows, the inner over columns.
- Use 1-D for a single sequence and 2-D when the data has two natural dimensions, such as a grid of seats or a table of marks by student and subject.
Grid[row, column], always in that order
Arrays de 2D
DECLARE Grid : ARRAY[1:3, 1:4] OF INTEGER
Grid[2, 3] ← 99 // row 2, column 3
- El primer índice es la fila, el segundo la columna. Los bucles anidados 嵌套循环 visitan todas las celdas: el bucle exterior sobre filas, el interior sobre columnas.
- Use 1-D para una secuencia única y 2-D cuando los datos tienen dos dimensiones naturales, como una grilla de asientos o una tabla de notas por alumno y asignatura.
Grid[row, column], siempre en ese orden
Index a 2-D array by [row, column] · Indexar una matriz 2-D con [fila, columna]
A 2-D array is a grid. Grid[row, column] reaches exactly one cell — change the row and column to see which value you land on. · Una matriz 2-D es una cuadrícula. Grid[row, column] accede a una única celda: cambia la fila y la columna para ver en qué valor terminas.
In Grid[2, 3], which cell is accessed? · En Grid[2, 3], ¿qué celda se accede?
The first index is the row, the second the column — so row 2, column 3. · El primer índice es la fila, el segundo la columna — así que fila 2, columna 3.
Worked example: a linear search that can say "not found"
- A linear search 线性查找 checks each element in turn from the first until the target is found or the end is reached.
-1can never be a valid index, so it means "not found". Initialise it before the loop and test it after. A search that never says "not found" loses a mark.
Ejemplo resuelto: búsqueda lineal que puede indicar "no encontrado"
- Una búsqueda lineal 线性查找 revisa cada elemento secuencialmente desde el primero hasta encontrar el objetivo o llegar al final.
FoundAt ← -1
FOR i ← 1 TO n
IF A[i] = Target THEN
FoundAt ← i
ENDIF
NEXT i
IF FoundAt = -1 THEN
OUTPUT "Not found"
ELSE
OUTPUT "Found at ", FoundAt
ENDIF
-1nunca puede ser un índice válido, por lo que significa "no encontrado". Inicialícelo antes del bucle y compruébelo después. Una búsqueda que nunca indica "no encontrado" pierde una nota.
A linear search finds a value by: · Una búsqueda lineal encuentra un valor mediante:
A linear search examines elements one by one from the start until it finds the target (or reaches the end). · Una búsqueda lineal examina los elementos uno por uno desde el principio hasta encontrar el objetivo (o llegar al final).
Setting FoundAt to -1 before a linear search lets the program report "not found" after the loop. · Establecer FoundAt en -1 antes de una búsqueda lineal permite que el programa informe "no encontrado" después del bucle.
-1 is never a valid index, so if it is unchanged after the loop the target was not in the array. · -1 nunca es un índice válido, por lo que si permanece sin cambiar tras el bucle, el objetivo no estaba en la matriz.
Largest value, and where it is
- Start
Largestat the first element, never at 0: the array might be all negative. - The same shape counts or outputs the non-blank elements: compare each with the marker for unused,
""or-1, and count only those that differ.
Valor más grande y dónde se encuentra
Largest ← A[1]
Position ← 1
FOR i ← 2 TO n
IF A[i] > Largest THEN
Largest ← A[i]
Position ← i
ENDIF
NEXT i
OUTPUT Largest, " at ", Position
- Inicialice
Largesten el primer elemento, nunca en 0: el array podría contener solo valores negativos. - La misma estructura cuenta o muestra los elementos no vacíos: compare cada uno con el marcador de no utilizado,
""o-1, y cuente solo aquellos que difieran.
Bubble sort
- A bubble sort 冒泡排序 makes repeated passes through the array comparing adjacent pairs and swapping those out of order, until a pass makes no swaps.
- After each pass the largest unsorted value has bubbled to the end, so the next pass can stop one place earlier.
Each pass carries the largest remaining value to the end
Ordenamiento burbuja
- Un ordenamiento burbuja 冒泡排序 realiza pasadas repetidas comparando pares adyacentes e intercambiándolos si están desordenados, hasta que una pasada no realiza ningún intercambio.
- Tras cada pasada, el valor sin ordenar más grande ha "subido" al final, por lo que la siguiente pasada puede detenerse un lugar antes.
REPEAT
Swapped ← FALSE
FOR Index ← 1 TO Limit - 1
IF Data[Index] > Data[Index + 1] THEN
Temp ← Data[Index]
Data[Index] ← Data[Index + 1]
Data[Index + 1] ← Temp
Swapped ← TRUE
ENDIF
NEXT Index
Limit ← Limit - 1
UNTIL Swapped = FALSE
Cada pasada transporta el valor restante más grande hacia el final
Put the steps of one bubble-sort pass, and its ending, in order. · Ordena los pasos de una pasada de bubble sort y su finalización.
Reset the flag, sweep and swap, shrink the limit, stop when a whole pass made no swap. · Restablecer la bandera, barrer e intercambiar, reducir el límite, detenerse cuando una pasada completa no realiza ningún intercambio.
Worked example: where the bubble-sort marks are
- The outer loop that repeats until a pass makes no swaps; the
Swappedflag reset toFALSEat the start of each pass and setTRUEinside theIF. - The three-line swap through a temporary variable. Two lines lose a value.
- The shrinking limit, one less each pass, because the largest value has already reached the end.
- In words, for a stepwise-refinement question: repeat until sorted; on each pass compare adjacent pairs; swap any pair out of order; after each pass the largest unsorted value is at the end.
Ejemplo resuelto: dónde se marcan los pasos del ordenamiento burbuja
- El bucle exterior que se repite hasta que una pasada no hace intercambios; la bandera
Swappedse restablece aFALSEal inicio de cada pasada y se establece enTRUEdentro delIF. - El intercambio de tres líneas a través de una variable temporal. Dos líneas pierden un valor.
- El límite decreciente, uno menos cada pasada, porque el valor más grande ya ha llegado al final.
- En palabras, para una pregunta de refinamiento paso a paso: repetir hasta ordenar; en cada pasada comparar pares adyacentes; intercambiar cualquier par desordenado; tras cada pasada, el valor sin ordenar más grande queda al final.
Which features earn marks in an efficient bubble sort? Select all · todos that apply. · ¿Qué características obtienen puntos en un bubble sort eficiente? Selecciona todos los que correspondan.
Flag, swap with a temporary, shrinking limit: those are the marks. Copying the array is not part of the algorithm. · Bandera, intercambio con una variable temporal, límite decreciente: esas son las características. Copiar la matriz no forma parte del algoritmo.
Worked example: removing and inserting
- Remove an item: find its index with a linear search; move every later element one place towards the start so the gap closes; mark the last element as unused, or reduce the count.
- Insert into a sorted array: find the first index whose element is larger; move that element and every later one one place towards the end, starting from the last; store the new value in the gap.
- Move from the end when opening a gap and from the start when closing one, or you overwrite the value you are about to move.
Ejemplo resuelto: eliminar e insertar
- Eliminar un ítem: encuentre su índice con una búsqueda lineal; mueva cada elemento posterior un lugar hacia el inicio para cerrar el hueco; marque el último elemento como no utilizado, o reduzca el conteo.
- Insertar en un array ordenado: encuentre el primer índice cuyo elemento sea mayor; mueva ese elemento y todos los posteriores un lugar hacia el final, comenzando desde el último; almacene el nuevo valor en el hueco.
- Mueva desde el final al abrir un hueco y desde el inicio al cerrarlo, o sobrescribirá el valor que está a punto de mover.
An array holds many items of the SAME type reached by index, while a record groups fields of (possibly) DIFFERENT types reached by name. · Una matriz contiene muchos elementos del MISMO tipo accesibles por índice, mientras que un registro agrupa campos de (posiblemente) TIPOS DIFERENTES accesibles por nombre.
A 2-D array suits a grid (rows × columns); a record suits one thing described by several named fields. · Una matriz 2-D es adecuada para una cuadrícula (filas × columnas); un registro es adecuado para describir una cosa mediante varios campos nombrados.
Marks that slip away
[0:99]holds 100 elements. Count both bounds.- An index is an
INTEGER; a declaration needs the type as well as the bounds. Grid[row, column]: row first. Swapping them reads the wrong cell in every nested loop.- A swap needs a temporary variable; a search needs a "not found" path; a bubble sort ends when a pass makes no swaps, not after a fixed number of passes.
Notas que se escapan
[0:99]contiene 100 elementos. Cuente ambos límites.- Un índice es un
INTEGER; una declaración necesita el tipo además de los límites. Grid[row, column]: fila primero. Intercambiarlos lee la celda incorrecta en cada bucle anidado.- Un intercambio necesita una variable temporal; una búsqueda necesita una ruta de "no encontrado"; un ordenamiento burbuja termina cuando una pasada no hace intercambios, no después de un número fijo de pasadas.
You've got it
- an array holds a fixed number of same-type elements under one identifier, reached by an index between the lower and upper bound; count = upper − lower + 1
- 1-D is a list, 2-D is a table
[row, column]walked by nested loops; declare with bounds and type - linear search:
FoundAt ← -1, loop, store the index, test after the loop; largest value: start atA[1], keep the position - bubble sort: passes of adjacent compare-and-swap with a temporary, a
Swappedflag, a shrinking limit, until a pass makes no swaps
Lo has logrado
- un array almacena un número fijo de elementos del mismo tipo bajo un identificador, accesibles mediante un índice entre el límite inferior y el límite superior; conteo = superior − inferior + 1
- 1-D es una lista, 2-D es una tabla
[row, column]recorrida por bucles anidados; declare con límites y tipo - búsqueda lineal:
FoundAt ← -1, bucle, almacene el índice, compruebe después del bucle; valor más grande: inicie enA[1], conserve la posición - ordenamiento burbuja: pasadas de comparación e intercambio adyacente con una variable temporal, una bandera
Swapped, un límite decreciente, hasta que una pasada no haga intercambios