Arrays · Tableaux
| English | Français |
|---|---|
| array/əˈreɪ/ | tableau |
| element/ˈelɪmənt/ | élément |
| index/ˈɪndeks/ | index |
| lower bound/ˈləʊə baʊnd/ | borne inférieure |
| upper bound/ˈʌpə baʊnd/ | borne supérieure |
| dimension/daɪˈmenʃn/ | dimension |
| nested loops/ˈnestɪd luːps/ | boucles imbriquées |
| linear search/ˈlɪnɪə sɜːtʃ/ | recherche linéaire |
| bubble sort/ˈbʌbl sɔːt/ | tri à bulles |
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.
Siège 14C
- Un cinéma a 300 places. Son système de réservation ne dispose pas de 300 variables appelées
Seat1A,Seat1B,Seat1C. Il possède un seul tableau 数组, et votre billet est une adresse vers celui-ci : rangée 14, siège C. - Un nom, des centaines de valeurs, chacune trouvée par un nombre. Ajoutez une rangée et le code ne change pas ; bouclez sur les nombres et vous avez vérifié chaque place.
- Presque tout algorithme Paper 2 parcourt un tableau : le cherche, le somme, le trie, trouve sa plus grande valeur.
- Cette leçon est le vocabulaire, les déclarations et les quatre algorithmes demandés par l'examinateur en pseudocode et en mots.
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
Le vocabulaire
- Un tableau est une structure de données contenant un nombre fixe d'éléments 元素 du même type de données sous un même identifiant, chacun accédé par un index 索引.
- La borne inférieure 下界 et la borne supérieure 上界 sont le premier et le dernier index valide. Le nombre d'éléments est borne supérieure − borne inférieure + 1.
- La dimension 维度 est le nombre d'indices qu'un élément nécessite : un pour une liste, deux pour un tableau.
- Dans
ThisArray[n] ← 42le tableau a une dimension, l'index est la variableINTEGERn, et l'élément à cet index reçoit42.
Un identifiant, un index pour chaque élément, des bornes aux deux extrémités
An array stores: · Un tableau stocke :
An array is an ordered collection of same-type items accessed by index. (A record groups different types.) · Un tableau est une collection ordonnée d'éléments de même type accédés par index. (Un enregistrement regroupe des types différents.)
An array is a data structure holding many values of the ______ type under one name. · Un tableau est une structure de données contenant de nombreuses valeurs du type ______ sous un même nom.
Each value is reached by its index. · Chaque valeur est accessible par son index.
DECLARE Marks : ARRAY[0:99] OF INTEGER declares an array of ____ elements. · DECLARE Marks : ARRAY[0:99] OF INTEGER déclare un tableau de ____ éléments.
Upper bound minus lower bound plus one: 99 − 0 + 1 = 100. Both bounds are valid indices. · Borne supérieure moins borne inférieure plus un : 99 − 0 + 1 = 100. Les deux bornes sont des indices valides.
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.
Exemple résolu : déclarer le tableau dont une tâche a besoin
- Une déclaration nécessite l'identifiant, les bornes et le type de données.
- 120 relevés pouvant avoir une décimale :
DECLARE Data : ARRAY[1:120] OF REAL - Un tableau de 150 lignes et deux colonnes de texte :
DECLARE Names : ARRAY[1:150, 1:2] OF STRING - Dites le compte si on vous le demande :
[0:99]contient 100 éléments, pas 99.
Which declaration holds a table of 150 rows and 2 columns of text? · Quelle déclaration contient un tableau de 150 lignes et 2 colonnes de texte ?
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. · Deux dimensions, chacune avec une borne inférieure et supérieure, et le type d'élément. La deuxième option est une longue liste ; la troisième n'a pas de type ; la quatrième n'a pas de bornes inférieures.
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.
Traitement d'un tableau 1-D
DECLARE Names : ARRAY[1:5] OF STRING
Names[3] ← "Cara"
FOR i ← 1 TO 5
OUTPUT Names[i]
NEXT i
- Une boucle
FORde la borne inférieure à la borne supérieure visite chaque élément une fois. - Pour une somme, un compte, un maximum ou un minimum, initialisez une variable avant la boucle et mettez-la à jour dedans.
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
Tableaux 2-D
DECLARE Grid : ARRAY[1:3, 1:4] OF INTEGER
Grid[2, 3] ← 99 // row 2, column 3
- Le premier index est la ligne, le second la colonne. Les boucles imbriquées 嵌套循环 visitent chaque cellule : la boucle extérieure sur les lignes, l'intérieure sur les colonnes.
- Utilisez 1-D pour une séquence unique et 2-D lorsque les données ont deux dimensions naturelles, comme une grille de sièges ou un tableau de notes par élève et matière.
Grid[row, column], toujours dans cet ordre
Index a 2-D array by [row, column] · Indexez un tableau 2D par [ligne, colonne]
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. · Un tableau 2D est une grille. Grid[ligne, colonne] accède exactement à une cellule — changez la ligne et la colonne pour voir quelle valeur vous atterrissez.
In Grid[2, 3], which cell is accessed? · Dans Grid[2, 3], quelle cellule est accédée ?
The first index is the row, the second the column — so row 2, column 3. · Le premier index est la ligne, le second la colonne — donc ligne 2, colonne 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.
Exemple résolu : une recherche linéaire capable de dire "non trouvé"
- Une recherche linéaire 线性查找 vérifie chaque élément successivement depuis le premier jusqu'à ce que la cible soit trouvée ou la fin atteinte.
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
-1ne peut jamais être un index valide, donc cela signifie "non trouvé". Initialisez-le avant la boucle et testez-le après. Une recherche qui ne dit jamais "non trouvé" perd une marque.
A linear search finds a value by: · Une recherche linéaire trouve une valeur en :
A linear search examines elements one by one from the start until it finds the target (or reaches the end). · Une recherche linéaire examine les éléments un par un depuis le début jusqu'à trouver la cible (ou atteindre la fin).
Setting FoundAt to -1 before a linear search lets the program report "not found" after the loop. · Définir FoundAt à -1 avant une recherche linéaire permet au programme de signaler « non trouvé » après la boucle.
-1 is never a valid index, so if it is unchanged after the loop the target was not in the array. · -1 n'est jamais un index valide, donc s'il reste inchangé après la boucle, la cible n'était pas dans le tableau.
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.
Plus grande valeur, et où elle se trouve
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
- Commencez
Largestau premier élément, jamais à 0 : le tableau pourrait être entièrement négatif. - La même forme compte ou affiche les éléments non vides : comparez chaque élément avec le marqueur d'inutilisé,
""ou-1, et ne comptez que ceux qui diffèrent.
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
Tri bulle
- Un tri bulle 冒泡排序 effectue des passages répétés dans le tableau en comparant les paires adjacentes et en échangeant celles hors ordre, jusqu'à ce qu'un passage ne fasse aucun échange.
- Après chaque passage, la plus grande valeur non triée a remonté à la fin, donc le passage suivant peut s'arrêter une position plus tôt.
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
Chaque passage emmène la plus grande valeur restante à la fin
Put the steps of one bubble-sort pass, and its ending, in order. · Remettez les étapes d'une passe de tri bulle, et sa fin, dans l'ordre.
Reset the flag, sweep and swap, shrink the limit, stop when a whole pass made no swap. · Réinitialiser le drapeau, balayer et échanger, réduire la limite, s'arrêter quand une passe entière n'a fait aucun échange.
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.
Exemple résolu : où se trouvent les marques du tri bulle
- La boucle extérieure qui répète jusqu'à ce qu'un passage ne fasse aucun échange ; le drapeau
Swappedréinitialisé àFALSEau début de chaque passage et mis àTRUEà l'intérieur duIF. - L'échange de trois lignes via une variable temporaire. Deux lignes font perdre une valeur.
- La limite décroissante, d'une unité de moins à chaque passage, car la plus grande valeur a déjà atteint la fin.
- En mots, pour une question de raffinement progressif : répéter jusqu'à ce que ce soit trié ; à chaque passage comparer les paires adjacentes ; échanger toute paire hors ordre ; après chaque passage, la plus grande valeur non triée est à la fin.
Which features earn marks in an efficient bubble sort? Select all · tout that apply. · Quelles caractéristiques rapportent des points dans un tri bulle efficace ? Sélectionnez toutes celles qui s'appliquent.
Flag, swap with a temporary, shrinking limit: those are the marks. Copying the array is not part of the algorithm. · Drapeau, échange avec une variable temporaire, limite décroissante : ce sont là les points. Copier le tableau ne fait pas partie de l'algorithme.
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.
Exemple résolu : supprimer et insérer
- Supprimer un élément : trouver son index avec une recherche linéaire ; déplacer tous les éléments suivants d'une position vers le début pour combler le vide ; marquer le dernier élément comme inutilisé, ou réduire le compte.
- Insérer dans un tableau trié : trouver le premier index dont l'élément est plus grand ; déplacer cet élément et tous les suivants d'une position vers la fin, en commençant par le dernier ; stocker la nouvelle valeur dans le vide.
- Déplacez depuis la fin quand vous ouvrez un vide et depuis le début quand vous le fermez, sinon vous écrasez la valeur que vous allez déplacer.
An array holds many items of the SAME type reached by index, while a record groups fields of (possibly) DIFFERENT types reached by name. · Un tableau contient de nombreux éléments du MÊME type accessibles par index, tandis qu'un enregistrement regroupe des champs de types (éventuellement) DIFFÉRENTS accessibles par nom.
A 2-D array suits a grid (rows × columns); a record suits one thing described by several named fields. · Un tableau 2D convient pour une grille (lignes × colonnes) ; un enregistrement convient pour une entité décrite par plusieurs champs nommés.
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.
Pièges qui font perdre des points
[0:99]contient 100 éléments. Comptez les deux bornes.- Un index est un
INTEGER; une déclaration nécessite le type ainsi que les bornes. Grid[row, column]: ligne d'abord. Les inverser lit la mauvaise cellule à chaque boucle imbriquée.- Un swap nécessite une variable temporaire ; une recherche nécessite un chemin « non trouvé » ; un tri à bulles se termine lorsqu'un passage ne fait aucun swap, et non après un nombre fixe de passages.
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
Vous avez compris
- Un tableau contient un nombre fixe d'éléments de même type sous un seul identifiant, accessibles par un index compris entre la borne inférieure et la borne supérieure ; count = upper − lower + 1
- Le 1-D est une liste, le 2-D est une table
[row, column]parcourue par des boucles imbriquées ; déclarer avec des bornes et un type - Recherche linéaire :
FoundAt ← -1, boucle, stocker l'index, tester après la boucle ; valeur maximale : commencer àA[1], garder la position - Tri à bulles : passes de comparaison-échange adjacentes avec une variable temporaire, un indicateur
Swapped, une limite décroissante, jusqu'à ce qu'un passage ne fasse aucun swap