Tri à bulles
Mettre le temps le plus court en premier
- Trois temps de course sont dans un tableau :
14,9,11. Le plus petit doit venir en premier. - Comparez chaque paire de voisins. Si celui de gauche est plus grand, échangez-les.
- Cette unique comparaison ne termine pas la liste. La paire suivante est comparée après celle-ci.
DECLARE Score : ARRAY[1:3] OF INTEGER
DECLARE J, Temp : INTEGER
Score[1] ← 14
Score[2] ← 9
Score[3] ← 11
FOR J ← 1 TO 2
IF Score[J] > Score[J + 1]
THEN
Temp ← Score[J]
Score[J] ← Score[J + 1]
Score[J + 1] ← Temp
ENDIF
NEXT J
OUTPUT Score[1]
OUTPUT Score[2]
OUTPUT Score[3]
Répéter la passe
- Une passe de la boucle interne fait remonter la plus grande valeur qu'elle voit vers la fin.
- La boucle externe répète la passe. Pour quatre valeurs, trois passes suffisent.
- C'est le tri à bulles du programme officiel. Une recherche linéaire, que vous avez écrite plus tôt, se contente de regarder. Un tri réorganise.
DECLARE Score : ARRAY[1:4] OF INTEGER
DECLARE I, J, Temp : INTEGER
Score[1] ← 4
Score[2] ← 1
Score[3] ← 3
Score[4] ← 2
FOR I ← 1 TO 3
FOR J ← 1 TO 3
IF Score[J] > Score[J + 1]
THEN
Temp ← Score[J]
Score[J] ← Score[J + 1]
Score[J + 1] ← Temp
ENDIF
NEXT J
NEXT I
OUTPUT Score[1]
OUTPUT Score[2]
OUTPUT Score[3]
OUTPUT Score[4]
Attention
- Échangez avec une variable
Temp.Score[J] ← Score[J + 1]seul supprime la valeur de gauche. - L'
NEXTinterne porte le nomJ. L'NEXTexterne porte le nomI.
Arrêter quand aucun échange n'a lieu
- La version fixée effectue toujours toutes les passes, même si la liste est déjà triée.
- Un drapeau
BOOLEAN,Swap, mémorise si un passage a échangé quoi que ce soit. Un passage sans échange signifie que la liste est triée, donc la boucle s'arrête. - Après chaque passage, la plus grande valeur restante est déjà en place, donc
Lastdiminue d'une unité.
DECLARE Score : ARRAY[1:5] OF INTEGER
DECLARE J, Last, Temp : INTEGER
DECLARE Swap : BOOLEAN
Score[1] ← 2
Score[2] ← 1
Score[3] ← 3
Score[4] ← 4
Score[5] ← 5
Last ← 4
REPEAT
Swap ← FALSE
FOR J ← 1 TO Last
IF Score[J] > Score[J + 1]
THEN
Temp ← Score[J]
Score[J] ← Score[J + 1]
Score[J + 1] ← Temp
Swap ← TRUE
ENDIF
NEXT J
Last ← Last - 1
UNTIL NOT Swap OR Last = 0
FOR J ← 1 TO 5
OUTPUT Score[J]
NEXT J
Ici, le premier passage échange 2 et 1, et le second passage n'échange rien, donc le tri s'arrête après deux passages au lieu de quatre.
Erreurs courantes
- Le test est « gauche est supérieur », donc la valeur plus petite se déplace vers la gauche. L'autre sens trie dans l'ordre inverse.
- Les tableaux dans ce cours commencent à 1. La dernière paire est la case juste avant la fin, et la dernière case.
FOR J ← 1 TO 4sur un tableau à 4 cases litScore[5], qui n'existe pas. La boucle intérieure s'arrête une position avant la fin.- Initialiser
Swap ← FALSEune seule fois, avant laREPEAT. Il doit être réinitialisé au début de chaque passage.
À vous maintenant
- La première tâche correspond à un passage. La seconde au tri complet. La troisième lit cinq valeurs et les trie par ordre décroissant avec un indicateur
Swap. Afficher chaque valeur sur sa propre ligne. - Appuyez sur Vérifier la réponse pour tester.
Difficulté 4/5 · 280 pièces + un petit bonus lors de la première réussite aujourd'hui
Le tableau Score contient 14, 9, 11. Effectuer un seul passage qui échange un voisin lorsque la valeur de gauche est plus grande. Afficher les trois valeurs, une par ligne (9, puis 11, puis 14).
Cliquez sur Exécuter pour voir le résultat ici.
Difficulté 4/5 · 280 pièces + un petit bonus lors de la première réussite aujourd'hui
Le tableau Score contient 4, 1, 3, 2. Triez-le par ordre croissant avec le tri bulle et affichez les quatre valeurs, une par ligne.
Cliquez sur Exécuter pour voir le résultat ici.
Difficulté 3/5 · 200 pièces + un petit bonus lors de la première réussite aujourd'hui
Lisez cinq entiers dans Score : ARRAY[1:5] OF INTEGER. Tri-bulles-les par ordre décroissant, en utilisant un indicateur booléen BOOLEAN Swap pour arrêter lorsqu'un passage ne provoque aucun échange. Affichez les cinq valeurs, une par ligne.
Cliquez sur Exécuter pour voir le résultat ici.