Tri par sélection

GW-Basic, utilisé par PC-Basic
Programme avec Texte Seulement
PC-BASIC

Les algorithmes de tri se présentent sous de nombreuses formes et tailles ; certains sont sans doute plus efficaces que d'autres.

Par exemple, considérez le tri à bulles, qui permute simplement à plusieurs reprises les éléments adjacents s'ils se trouvent dans l'ordre décroissant ; une fois qu'il ne reste plus d'échanges à faire, la liste est triée.

Bien que la technique fonctionne bien, à mesure que le nombre d'éléments non triés augmente précocement, le temps de tri de ces éléments augmente de façon exponentielle (plus sur cette idée plus loin). Dans cette section, nous avons codé un algorithme de tri à bulles GW-BASIC Bubble Tri.

Une technique de tri plus optimisée est appelée le tri par sélection. Le tri par sélection divise une liste d'éléments non triés en deux parties : triés à gauche et non triés à droite, et trie séquentiellement la partie droite.

Voici le processus :

Ignorer le premier élément de la liste.

Recherche séquentiellement chaque élément après le premier élément, en trouvant le plus petit.

Si le premier élément est plus grand que le plus petit élément, placez le plus petit élément en premier ; sinon, placez le plus petit objet en second.

Ensuite, recherchez séquentiellement du troisième élément au dernier élément, en trouvant le plus petit ; placez cet élément en troisième.

Répétez ce processus, en recherchant séquentiellement de moins en moins d'éléments, jusqu'à ce que la liste entière soit dans l'ordre croissant.

Le programme SEL.BAS vous permet de tester le tri de la sélection sur votre propre ensemble de données. Saisissez au maximum 50 éléments (interrompez la saisie à tout moment en saisissant un nombre négatif) et attendez la fin du processus de tri.

Comme vous pouvez vous y attendre, plus vous saisissez d'éléments, plus le programme mettra de temps à les trier.

Une fois les données saisies par l'utilisateur (voir lies 60 à 120), une boucle WHILE-WEND, commençant à la ligne 205, se charge du reste : recherche séquentielle dans le tableau ARRAY (déclaré à l'aide de l'instruction DIM) et permutation des éléments si nécessaire.

5 REM SEL.BAS
18 KEY OFF:CLS
15 DIM ARRAY(50)
16 ELEM=1:I=0
20 PRINT "--- Tri par sélection ---"
30 PRINT
40 PRINT "Entrez votre tableau, un nombre à la fois. Entrez un nombre négatif pour terminer."
50 PRINT "Il y a un maximum de 50 éléments autorisés."
60 WHILE I>=0
70 PRINT "Élément #";ELEM;":";
80 INPUT I:ARRAY(ELEM)=I
90 ELEM=ELEM+1
100 IF ELEM>50 THEN I=-1
120 WEND
130 ELEM=ELEM-2 'Obtient le nombre total d'éléments du tableau
200 'Mettre en œuvre l'algorithme de tri par sélection
202 FIRST=2 'Sélectionne le "premier" élément
205 WHILE FIRST<ELEM
210 SMALL=FIRST
220 FOR SEARCH=FIRST TO ELEM
230 'Trouvez le plus petit de ces éléments
240 IF ARRAY(SMALL)>ARRAY(SEARCH) THEN SMALL=SEARCH
250 NEXT SEARCH
260 'Échangez les éléments, si nécessaire
265 IF ARRAY(FIRST-1)>ARRAY(SMALL) THEN GOTO 270 ELSE GOTO 280
270 TEMP=ARRAY(FIRST-1):ARRAY(FIRST-1)=ARRAY(SMALL):ARRAY(SMALL)=TEMP
280 FIRST=FIRST+1 'Incrémenter jusqu'à l'élément "actuel" suivant
290 WEND
300 'Affiche le tableau trié
310 FOR G=1 TO ELEM
320 PRINT ARRAY(G);" ,";
330 NEXT G

En soi, il est difficile d'améliorer beaucoup SEL.BAS, car il souffre des mêmes limitations que n'importe quel algorithme de tri par sélection : plus une liste contient d'éléments non triés, plus il faut (beaucoup) de temps pour les trier (bien que le le tri par sélection ne prend généralement pas aussi longtemps que le tri par bulles).

Pour améliorer les choses, envisagez d'écrire du code pour une routine de tri plus optimale, telle que le tri rapide. Bien que cela présente aussi ses propres complications, comme nous le verrons dans une section ultérieure sur la récursivité.

Avant de terminer cette section, cependant, il m'incombe de mentionner brièvement l'idée de la complexité de l'analyse temporelle des algorithmes (nous ignorerons les problèmes d'espace, car la mémoire disponible n'est plus vraiment un problème avec les ordinateurs).

La manière typique de classer la complexité consiste à utiliser la notation Big O. Le "O" signifie ordre et décrit le taux de croissance d'une fonction à mesure que les entrées augmentent.

S'il n'y a pas de répétition dans le code, la valeur Big O est 1, exprimée sous la forme O(1). C'est ce qu'on appelle le temps constant.

Voici un exemple:

i0 CLS
20 X=1
30 Y=6
40 Z=X+Y
50 PRINT Z

Mais avec une seule boucle dans le code, la valeur Big O gonfle à n, exprimée sous la forme O{n) et appelée temps linéaire.

Considérez le programme suivant :

10 CLS
15 INPUT "INPUT MAXIMUM";N
20 FOR X=1 TO N
30 PRINT N
40 NEXT X

Plus un N que vous entrez est grand, plus il faut d'étapes pour parcourir la boucle. Plus précisément, le nombre d'étapes nécessaires pour parcourir la boucle est proportionnel à la valeur de la variable d'entrée N.

De même, avec O(n²), ou temps quadratique, le nombre d'étapes pour implémenter l'algorithme est proportionnel aux entrées au carré.

Considérez une boucle dans une boucle comme une instance de temps quadratique :

10 CLS
15 INPUT "INPUT OUTER MAXIMUM";N
16 INPUT "INPUT INNER MAXIMUM";M
20 FOR X=1 TO N
25 FOR Y=1 TO M
30 PRINT M
35 NEXT Y
40 NEXT X

Et, sans surprise, une boucle dans une boucle dans une boucle a un Big O de O(n³). De telles puissances de n — quadratique, cubique, etc. — sont appelées temps polynomial de degré supérieur à 1 (notez ce temps linéaire = un polynôme avec un degré de 1).

Mais il existe d'autres possibilités avec des tâches impliquant des boucles, selon comment, précisément, les boucles sont parcourues.

Si vous parcourez une boucle par des sauts toujours croissants, plutôt que d'incrémenter d'une quantité constante, alors vous travaillez en temps logarithmique, c'est-à-dire O(log n).

Aussi commun est n log n temps, ou O(n log n) ainsi que (généralement) le plus lent du groupe, le temps exponentiel, ou O(aⁿ).

Vous devez garder à l'esprit ces problèmes de complexité temporelle, d'autant plus que l'exécution de code une par une via un interpréteur est un tel obstacle au bon fonctionnement des programmes ; écrire du code GW-BASIC de manière à réduire au maximum la complexité temporelle des algorithmes rapportera des dividendes en termes de vitesse d'exécution.

En général, mais pas toujours*, l'ensemble d'inégalités suivant s'applique en ce qui concerne le temps d'exécution requis :

temps constant < temps logarithmique < temps linéaire <
< temps n log n < temps polynomial de degré supérieur à 1 <
< temps exponentiel

Nous devons également être particulièrement conscients de la complexité temporelle lors de l'écriture d'algorithmes de tri.

Prenez le tri par sélection, par exemple ; cette méthode de tri, qui est de nature incrémentale, est de la variété O(n²), ou temps quadratique. Le tri à bulles a également une complexité de O(n²).

*Il y a des cas où les valeurs de n sont "relativement" petites dans lesquelles, par exemple, une fonction avec une complexité temporelle linéaire s'exécuterait plus rapidement qu'une avec une complexité temporelle logarithmique. En général, cependant, si n est grand, les inégalités énoncées ci-dessus sont vraies.