Les algorithmes de tri tels qu'ils sont

Le tri est un arrangementobjets dans un certain ordre, par exemple, dans l'ordre décroissant ou croissant. En général, la commande d'éléments est la manipulation la plus commune avec des données, ce qui facilite la recherche des bonnes informations dans le futur. Ceci s'applique largement à divers systèmes de gestion de base de données. Les algorithmes de tri existent actuellement en grand nombre, bien qu'ils présentent des caractéristiques (étapes) similaires: 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 eninterne 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 qu'il est possible d'obtenir un accès aléatoire à l'un d'entre eux. Ce dernier peut travailler 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 de manière séquentielle.

Il est plus pratique de trier les éléments lorsqu'ils sontdans la structure d'un tableau à une dimension. Chacun de ces éléments a un numéro de série et l'élément de tableau est accessible par index. Les algorithmes de tri dans ce cas s'avèrent être les plus simples et compréhensibles à utiliser.

Considérons un algorithme de tri interne pourdescendant par la méthode de la bulle et sa version améliorée, différant dans le temps passé pour le tri. Le tri par la méthode des bulles a en réalité plusieurs noms. On l'appelle aussi la méthode de tri linéaire ou la méthode de tri par échange. Mais, cependant, ce n'est pas un nom. Pourquoi une bulle? Une fois dans l'eau, la bulle d'air va flotter, car c'est plus facile. Ainsi, par exemple, en triant par ordre croissant, le plus petit des éléments apparaîtra en haut.

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

1. Placez le plus grand élément du tableau à la place du premier élément (mas [1]). Pour cela, 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 à mas [1], il est nécessaire de les échanger (via la variable supplémentaire buf).

2. Après avoir exclu l'élément mas [1], 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.

Implémentation de l'algorithme de tri à bulles en Pascal:

A propos de la deuxième option (une méthode amélioréebulle) on peut dire que c'est un algorithme de tri rapide. Donc, si vous essayez de l'utiliser pour trier un tableau déjà trié, l'algorithme terminera son travail après le premier passage à travers les éléments du tableau. Ainsi, nous ne dépenserons pas les ressources informatiques du système et le temps pour une comparaison sans signification des éléments.

Voici l'implémentation de cet algorithme de tri pour le langage de programmation Pascal:

Ainsi, les algorithmes de tri sont un moyen de commander des séquences de données. Lorsque vous choisissez un algorithme particulier, vous devez prendre en compte les coûts en termes de temps et de ressources du système.