Les algorithmes de tri comme ils sont

Le tri est l'agencement d'objets dans un certain ordre, par exemple, par ordre décroissant ou par ordre croissant. En général, les éléments de commande sont la manipulation la plus courante avec les données, ce qui permet de trouver plus facilement les bonnes informations à l'avenir. Cela s'applique en grande partie aux différents systèmes de gestion de bases de données. Les algorithmes de tri existent actuellement en grand nombre, bien qu'ils aient des caractéristiques similaires (étapes): comparaison et permutation des éléments par paires jusqu'à ce que la séquence soit ordonnée.

Les algorithmes de tri peuvent être classés en interne et externe. Les premiers sont caractérisés par le fait que tous les éléments triés sont placés dans la RAM et il est possible d'avoir un accès aléatoire à l'un d'entre eux. Ce dernier peut fonctionner avec des données situées dans la mémoire externe (dans les fichiers). L'accès à de tels éléments peut être mis en œuvre séquentiellement.

Il est plus pratique de trier les éléments lorsqu'ils sont dans la structure d'un tableau unidimensionnel. Chacun de ces éléments a un numéro de série, et l'élément de tableau est accessible par l'index. Les algorithmes de tri dans ce cas se révèlent être les plus simples et compréhensibles à utiliser.

Nous considérons un algorithme de tri descendant interne selon la méthode de la bulle et sa version améliorée, différant du temps passé pour le tri. Le tri par la méthode de la bulle a beaucoup de noms. On l'appelle aussi la méthode de tri linéaire ou la méthode d'échange par choix. Mais, cependant, ce n'est pas un nom. Pourquoi une bulle? Une fois dans l'eau, la bulle d'air flottera, car elle est plus facile. Ainsi, par exemple, lors du tri par ordre croissant, le plus petit des éléments apparaîtra en haut.

Considérons la première variante de l'algorithme de tri d'un tableau par une méthode à bulle. L'algorithme verbal pour trier un tableau qui a l'identifiant mas et qui comprend N éléments ressemble à ceci:

1. Placez le plus grand élément du tableau à la place du premier élément (mas [1]). Pour ce faire, nous allons le comparer à tour de rôle avec tous les éléments restants (mas [2], mas [3] … mas [N]). S'il s'avère que l'un des éléments restants est supérieur à [1], il est nécessaire de les échanger (via la variable supplémentaire buf).

2. Après avoir exclu l'élément mas [1] de la considération, répétez le paragraphe 1 pour l'élément mas [2].

3. Ces actions doivent être répétées pour tous les éléments sauf le dernier.

Mise en œuvre de l'algorithme de tri des bulles dans le langage de programmation Pascal:

À propos de la deuxième option (une méthode de bulle améliorée), on peut dire qu'il s'agit d'un algorithme de tri rapide . Donc, si vous essayez de l'utiliser pour trier un tableau déjà trié, l'algorithme finira son travail après le premier passage dans les éléments du tableau. Cela signifie que nous ne dépenserons pas les ressources informatiques du système et le temps pour une comparaison sans importance des éléments.

Voici la mise en œuvre de cet algorithme de tri pour le langage de programmation Pascal:

Ainsi, les algorithmes de tri sont un moyen de séquençage des séquences de données. Lors du choix d'un algorithme particulier, vous devez tenir compte des coûts en termes de temps et de ressources système.