Tri des bulles d'un tableau unidimensionnel: algorithme, code de programme en langage C

En travaillant avec l'information la plus rentableles moyens de stockage sont des structures et des tableaux. Ce dernier peut contenir des données de type unique, ce qui est pratique à utiliser dans le programme. Ils sont souvent utilisés dans le travail des magasins en ligne et dans le développement de jeux. Par conséquent, les données qu'ils contiennent sont triées et échangées de manière répétée, et des opérations logiques ou mathématiques sont effectuées sur celles-ci. Un moyen de mettre de l'ordre dans le tableau est le tri des bulles. Cette publication étudiera son code C et la logique des permutations.

Algorithme de tri de tableaux

Difficultés techniques pour le programmeurle tri à bulle d'un tableau unidimensionnel ne représente pas, bien qu'il soit utilisé assez rarement en raison de sa faible efficacité. Il est plus souvent considéré au stade de la formation comme le plus simple. Cependant, il est loin d'être le plus efficace. Son algorithme consiste à comparer alternativement les chiffres et à écraser mutuellement les cellules si la condition est remplie.

Description de tri étape par étape

À la première itération, deuxnuméros voisins. Si la gauche est plus grande, alors elle est réécrite dans les endroits avec la bonne. Moins 8 et 0 les conditions ne satisfont pas. C'est pourquoi ils ne changent pas par endroits. Zéro et 5 ne correspondent pas non plus. 5 et 3 conviennent. Cependant, à cette itération, le cadre de lecture ne tombe pas dans les cinq premiers, mais se décale vers la droite, puisque 5 avant cela a été comparé à zéro. Cela signifie que la prochaine paire - 3 et 9 change de place.Puis le lecteur se propose de passer en revue toutes les substitutions indépendamment sans commentaires de l'auteur et d'étudier l'algorithme de tri à bulles.

À la suite de toutes les itérations, le tableau progressivementest trié, et c'est essentiellement le cas: les grands nombres positifs se déplacent rapidement vers la droite, alors que les plus petits et les négatifs sont lentement décalés vers la gauche. On dirait que des bulles de gaz dans un liquide se lèvent rapidement. En raison de cette analogie, l'algorithme a été appelé tri à bulles.

Estimation de la complexité de calcul

L'algorithme de tri idéal devrait êtreaussi vite que possible. Dans le même temps, il devrait prendre une petite quantité de ressources CPU et mémoire. Et un tel processus comme un tri à bulles d'un tableau ne peut pas être le plus économe en énergie et rentable. En raison d'une large application, il n'a pas trouvé. S'il y a moins de problèmes avec la mémoire en ce moment, alors les ressources du processeur devraient être inquiètes. Puisque les baies numériques peuvent être non seulement grandes, mais énormes, alors la consommation de ressources informatiques sera imprévisible.

Si le tri à bulles est, en principe, rapidefait face à l'établissement de l'ordre dans une gamme relativement petite, puis dans l'ensemble il peut y avoir des échecs en raison de la sur-dépense des ressources. Cela signifie que la propriété d'universalité inhérente à l'algorithme sera violée. Et le tri par une bulle a une complexité N-carré et est très loin du logarithme de la complexité N. En outre, le risque d'échec dans le traitement d'un grand réseau augmente les risques de perte de données due à l'écrasement des cellules. Beaucoup plus rentable à cet égard sera le tri de l'insertion ou l'algorithme de Shell.

Code logiciel

Ce qui suit est dans l'application graphiquecode informatique pour le langage C vous permet d'effectuer un tri à bulles. Il est rendu comme une fonction séparée de type void. Il ne renvoie aucune valeur, mais l'utilisation de pointeurs permute les éléments en fonction des conditions de tri. Dans ce cas, le code résout le problème du tri à bulles d'un tableau d'entiers dans l'ordre croissant.

Pour effectuer cette fonction, l'utilisateur doitcréer un tableau qui doit être rempli avec les valeurs souhaitées. Cela peut être fait manuellement, en définissant la dimension et le nombre d'éléments au début du programme. Ensuite, vous pouvez remplir le tableau avec des valeurs constantes. La deuxième option consiste à créer un programme universel en déclarant un grand tableau unidimensionnel de 100 éléments.

Déclaration et initialisation d'un tableau

Affecter une variable entière et l'affecterLa valeur lue sur le clavier peut limiter le nombre de cellules à remplir. Vous pouvez également implémenter la fonction de saisie des éléments d'un tableau par l'utilisateur à partir du clavier, en utilisant la fonction scanf ("% d", & value). Dans cet exemple, "% d" est une chaîne de modification qui indique au compilateur qu'une valeur entière sera reçue après l'analyse. La valeur de la variable stockera une valeur correspondant à la taille d'un tableau d'entiers à une dimension.

Pour utiliser l'algorithme de tri, vous devriezpasser dans la fonction le nom du tableau et sa taille. Dans la situation présentée dans l'application graphique, l'appel à la fonction de tri ressemblera à ceci: BubleSort (dataArray, sizeDataArray). Bien sûr, à la fin de la ligne après la fonction, vous devez placer un point-virgule au lieu d'un point, comme requis par les règles de syntaxe du programme. Donc, dataArray est le nom du tableau que vous voulez trier, et sizeDataArray est sa taille.

Passer ces paramètres à la fonction BubleSort ()Il en résultera qu'au lieu d'utiliser sizeArray, comme vous pouvez le voir sur la figure, dans un vrai programme, les opérations seront effectuées avec sizeDataArray. Cela signifie également que la fonction BubleSort () utilisera un dataArray entier. De même, les fonctions printArrayFunction () et ArrayIntegerInputFunction () sont appelées. Le premier est responsable de l'impression, c'est-à-dire de la sortie vers la console des éléments. Et le second est nécessaire pour le remplir avec des éléments entrés par l'utilisateur à partir du clavier.

Ce style de programmation, lorsqu'il est isoléles opérations sont réalisées sous forme de fonctions, augmente significativement la lisibilité du code et accélère son développement. Dans un tel programme, le tableau est rempli séparément du clavier, imprimé et le tri à bulles lui-même. Ce dernier peut être utilisé pour organiser les données ou comme une fonction secondaire conçue pour trouver le minimum et le maximum du tableau.

Tri d'insertion

En tri par la méthode d'insertioncomparer alternativement chaque élément et construire une chaîne d'éléments déjà triés en fonction de la condition. Par conséquent, le résultat de chaque comparaison ultérieure est la recherche d'une cellule dans laquelle une nouvelle valeur peut être placée. Mais l'insertion de chacun d'eux est effectuée dans la partie déjà triée du tableau.

Un tel traitement est plus rapide et a moins de complexité de calcul. Le code C est présenté dans l'application graphique.

Il est également rendu sous la forme d'une fonction dans laquelleEn tant qu'arguments, le nom du tableau qui doit être commandé et la taille du tableau sont transférés. Ici vous pouvez voir à quel point le type de bulle est lent. Insère un travail similaire est beaucoup plus rapide et a un code compact.