Un algorithme est un ensemble de règles bien définies utilisées pour résoudre un problème en un nombre limité d'étapes. Pour faire simple, il s’agit du processus de résolution informatique de problèmes. Dans ce processus, que vous formiez une idée pour résoudre un problème ou que vous écriviez un programme, vous implémentez un certain algorithme. Le premier est un algorithme implémenté par raisonnement, et le second est un algorithme implémenté par opération.
Un algorithme doit avoir les cinq caractéristiques importantes suivantes :
1. Finitude : un algorithme doit garantir qu'il se termine après l'exécution d'un nombre fini d'étapes ;
2. Exactitude : Chaque étape de l’algorithme doit être clairement définie ;
3. Entrée : un algorithme a 0 ou plusieurs entrées pour décrire la situation initiale de l'opérande ;
4. Sortie : un algorithme a une ou plusieurs sorties pour refléter les résultats du traitement des données d'entrée. Un algorithme sans résultat n’a aucun sens ;
5. Faisabilité : En principe, l’algorithme peut fonctionner avec précision et peut être complété par des personnes utilisant un stylo et du papier pour effectuer un nombre limité d’opérations.
Le tri par fusion (MERGE SORT) est un autre type de méthode de tri différente. La signification de la fusion est de fusionner deux ou plusieurs séquences de données ordonnées en une nouvelle séquence de données ordonnées, c'est pourquoi on l'appelle également algorithme de fusion. Son idée de base est de supposer que le tableau A a N éléments, alors le tableau A peut être considéré comme constitué de N sous-séquences ordonnées, chaque sous-séquence a une longueur de 1, puis fusionnée deux par deux pour obtenir une sous-séquence ordonnée N/2 de la longueur 2 ou 1 est ensuite fusionnée deux par deux, et ceci est répété jusqu'à ce qu'une séquence de données ordonnée de longueur N soit obtenue. Cette méthode de tri est appelée tri par fusion bidirectionnelle.
Par exemple, le tableau A contient 7 données, qui sont : 49 38 65 97 76 13 27. Ensuite, le processus opérationnel d'utilisation de l'algorithme de tri par fusion est illustré à la figure 7 :
Valeur initiale[49][38][65][97][76][13][27]
Considéré comme constitué de 7 sous-séquences de longueur 1. Après la première fusion [38 49] [65 97] [13 76] [27]
Considéré comme constitué de 4 sous-séquences de longueur 1 ou 2. Après la deuxième fusion [38 49 65 97] [13 27 76]
Considéré comme constitué de 2 sous-séquences de longueur 4 ou 3. Après la troisième fusion [13 27 38 49 65 76 97]
Figure 6 Diagramme du processus de l'algorithme de tri par fusion L'opération principale de l'algorithme de fusion consiste à fusionner deux séquences ordonnées adjacentes dans un tableau unidimensionnel en une seule séquence ordonnée. L'algorithme de fusion peut également être mis en œuvre à l'aide d'un algorithme récursif, qui est de forme relativement simple, mais peu pratique.
Le nombre de fusions dans l'algorithme de fusion est une quantité très importante selon les calculs, lorsqu'il y a 3 à 4 éléments dans le tableau, le nombre de fusions est de 2, lorsqu'il y a 5 à 8 éléments, le nombre de fusions est de 3. , et lorsqu'il y a 9 à Lorsqu'il y a 16 éléments, le nombre de fusions est de 4. Selon cette règle, lorsqu'il y a N sous-séquences, on peut en déduire que le nombre de fusions est
X (2>=N, le plus petit X qui remplit la sous-condition).
Description de l'algorithme de bulle :
Avant d'expliquer l'algorithme de tri à bulles, introduisons d'abord un algorithme qui place le plus grand nombre parmi 10 nombres (dans le tableau A) en dernière position. L'algorithme est décrit comme suit :
(1) Du tableau A[1] à A[10], comparez deux nombres adjacents par paires. Autrement dit, A[1] est comparé à A[2], et après la comparaison, A[2] est comparé à A[3],... et enfin A[9] est comparé à A[10].
(2) Lors de chaque comparaison, si le nombre précédent est supérieur au dernier nombre, les deux nombres seront intervertis, c'est-à-dire que le plus grand nombre sera déplacé vers l'arrière et le plus petit nombre sera déplacé vers l'avant. Par exemple, dans la première comparaison, si A[1] est supérieur à A[2], les valeurs de A[1] et A[2] sont interchangées. La figure ci-dessous utilise 6 données pour illustrer l'algorithme ci-dessus.
Supposons que les 6 données soient : A[]=5 7 4 3 8 6
Un[1] Un[2] Un[3] Un[4] Un[5] Un[6]
5 7 4 3 8 6 La première fois, A[1]=5 et A[2]=7 sont comparés, 7>5, aucun échange n'est effectué.
5 7 4 3 8 6 La deuxième fois, A[2]=7 et A[3]=4 sont comparés, 4<7, swap.
Ensuite, les données après la deuxième comparaison sont 5 4 7 3 8 6
5 4 7 3 8 6 La troisième fois, A[3]=7 et A[4]=3 sont comparés, 3<7, swap.
Ensuite, les données après la troisième comparaison sont 5 4 3 7 8 6
5 4 3 7 8 6 La quatrième fois, A[4]=7 et A[5]=8 sont comparés, 8>7, aucun échange n'est effectué.
5 4 3 7 8 6 La cinquième fois, A[6]=6 et A[5]=8 sont comparés, 6<8, swap.
Alors le cinquième et dernier résultat est
5 4 3 7 6 8
************************************************** * *****
Description de l'algorithme de tri par sélection :
Avant d'introduire la méthode de tri par sélection, introduisons un algorithme qui met le plus petit nombre en première position. Bien sûr, vous pouvez également utiliser la méthode de tri à bulles mentionnée ci-dessus. Nous utilisons maintenant un nouvel algorithme : Son idéologie directrice Je ne suis pas dans un. dépêchez-vous de changer de position au début, mais commencez par A[1] commence à vérifier un par un. Pour voir quel nombre est le plus petit, notez la position P du nombre. Une fois l'analyse terminée, échangez A[P] et A[1]. [1] à A[ 10] est déplacé vers l'avant. Les étapes de l'algorithme sont les suivantes :
1) Tout d’abord, supposons que le nombre dans A[1] est le plus petit et notez la position P=1 à ce moment ;
2) Comparez A[P] et A[I] dans l'ordre (I change de 2 à 10). Lors de chaque comparaison, si le nombre dans A[I] est inférieur au nombre dans A[P], alors I La valeur). est affecté à P, de sorte que P pointe toujours vers la position du plus petit nombre actuellement scanné, c'est-à-dire que A[P] est toujours égal au plus petit nombre de tous les nombres scannés. Après avoir comparé un par un, P pointe vers la position du plus petit nombre parmi les 10 nombres, c'est-à-dire que A[P] est le plus petit nombre parmi les 10 nombres ;
3) Inversez les nombres de A[P] et A[1], alors le plus petit nombre sera dans A[1], c'est-à-dire au début.
Si vous répétez maintenant cet algorithme, mais à chaque fois qu'il est répété, la plage de la série comparée est reculée d'une position. Autrement dit, dans la deuxième comparaison, la plage va du 2ème nombre au Nème nombre. Trouvez la position P du plus petit nombre dans cette plage, puis échangez A[P] et A[2], de sorte qu'à partir du 2ème. Le plus petit nombre du début au Nième nombre est en A [2] réussit, la troisième fois consiste à trouver le plus petit nombre du 3ème nombre au Nème nombre, puis à échanger A[P] et A[3]... Après avoir répété ce processus N-1 fois, arrangez simplement les N nombres du tableau A de petit à grand. Cette méthode de tri est le tri par sélection.
************************************************** * ***************
Description de l'algorithme de tri par insertion :
En apprenant les deux méthodes ci-dessus, vous pouvez comprendre l'idée de base du tri et vous pouvez également organiser n'importe quel tableau non ordonné du grand au petit (ordre décroissant) ou du petit au grand (ordre croissant). Supposons maintenant qu'il existe une séquence de données déjà ordonnée et qu'il est nécessaire d'insérer un nombre dans cette séquence de données déjà organisée, mais il est nécessaire que la séquence de données soit toujours ordonnée après l'insertion. À ce stade, une nouvelle méthode de tri sera utilisée. être utilisé - Méthode de tri par insertion, l'opération de base du tri par insertion consiste à insérer une donnée dans les données ordonnées qui ont été triées, afin d'obtenir une nouvelle donnée ordonnée avec le nombre plus un.
Question : Il y a N éléments de données dans le tableau A, classés du plus petit au plus grand. Entrez un nombre X et insérez la valeur de X dans le tableau A, de sorte que le tableau A inséré soit toujours classé du plus petit au plus grand. .
Alors l’algorithme pour résoudre ce problème est :
1) Trouvez la position où X doit être inséré en comparant la taille, s'il doit être placé à la I-ième position ;
2) Déplacez tous les éléments du tableau à partir de I (y compris I) d'une position vers l'arrière, c'est-à-dire A[I+1]:=A[I];
Le tri rapide est une amélioration du tri à bulles. Son idée de base est de diviser les données à trier en deux parties indépendantes grâce à un tri unidirectionnel. Toutes les données d'une partie sont plus petites que toutes les données de l'autre partie, puis les deux parties des données sont triées séquentiellement. Pour un tri rapide, l'ensemble du processus de tri peut être effectué de manière récursive, de sorte que l'ensemble des données devienne une séquence ordonnée.
Supposons que le tableau à trier est A[1]...A[N]. Tout d'abord, sélectionnez au hasard une donnée (généralement la première donnée) comme donnée clé, puis placez tous les nombres supérieurs à celle-ci devant elle, et tous les nombres supérieurs à celui-ci. De grands nombres sont placés derrière. Ce processus est appelé tri rapide. L'algorithme de tri rapide est le suivant :
1) Définissez deux variables I et J. Lorsque le tri démarre, I:=1, J:=N ;
2) Utilisez le premier élément du tableau comme données clés et attribuez-le à X, c'est-à-dire X:=A[1] ;
3) Rechercher vers l'avant à partir de J, c'est-à-dire rechercher vers l'avant depuis l'arrière (J:=J-1), trouver la première valeur inférieure à X et échanger les deux ;
4) Rechercher en arrière à partir de I, c'est-à-dire rechercher d'avant en arrière (I:=I+1), trouver la première valeur supérieure à X et échanger les deux ;
5) Répétez les étapes 3 et 4 jusqu'à ce que I=J ;
Par exemple : les valeurs du tableau A à trier sont : (données clés initiales X :=49)
A[1] A[2] A[3] A[4] A[5] A[6] A[7] :
49 38 65 97 76 13 27
Après le premier échange : 27 38 65 97 76 13 49
(Après recherche par l'arrière selon la troisième étape de l'algorithme pour le deuxième échange : 27 38 49 97 76 13 65
(Suivez la quatrième étape de l'algorithme et commencez par le début pour trouver la valeur >
Après le troisième échange : 27 38 13 97 76 49 65
(Selon la cinquième étape de l'algorithme, la troisième étape de l'algorithme sera réexécutée à partir de la fin pour retrouver le quatrième échange : 27 38 13 49 76 97 65
(Suivez la quatrième étape de l'algorithme et partez de l'avant pour trouver une valeur supérieure à X, 97>49, échangez les deux, à cet instant J:=4)
A ce moment, lors de l'exécution de la troisième étape, on constate que I=J, mettant ainsi fin au tri rapide. Le résultat après le tri rapide est : 27 38 13 49 76 97 65, c'est-à-dire que tous les nombres supérieurs à 49 sont dans 49. , donc les nombres inférieurs à 49 sont tous devant 49.
Le tri rapide consiste à appeler ce processus de manière récursive - diviser la séquence de données avec 49 comme point médian, effectuer un tri rapide similaire sur la partie avant et la partie arrière respectivement, complétant ainsi le tri rapide de toute la séquence de données, et enfin transformer la séquence de données en une séquence ordonnée. Selon cette idée, l'ensemble du processus de tri rapide du tableau A ci-dessus est illustré à la figure 6 :
État initial {49 38 65 97 76 13 27}
Après un tri rapide, il est divisé en {27 38 13} 49 {76 97 65}
Triez rapidement les parties avant et arrière respectivement {13} 27 {38}
fin fin {49 65} 76 {97} 49 {65} fin fin
************************************************** * *************************
Figure 6 Description de l'algorithme de tri rapide tout au long du processus de tri rapide
1). Supposons que N (en supposant que N = 10) nombres soient stockés dans le tableau S ;
2), dans S[1. . Prenez n'importe quel élément de N] comme base de comparaison, par exemple, prenez T=S[1]. Le but initial est de déterminer la position K où T doit être dans le résultat du tri. La position de K est : S[1]. . . K-1]<=S[K]<=S[K+1..N], c'est-à-dire que les nombres avant S[K] sont tous plus petits que S[K], et les nombres après S[K] sont tous plus grands que S[ K] ;
3) L’utilisation de l’idée diviser pour régner (c’est-à-dire la stratégie consistant à faire en sorte que les grands et les petits soient petits) peut encore améliorer S[1. . K-1] et S[K+1. . N] Les deux ensembles de données sont ensuite rapidement triés jusqu'à ce qu'il n'y ait qu'une seule donnée dans l'objet de regroupement.
Si les données spécifiques sont les suivantes, alors le premier processus de tri rapide est :
Indice du tableau : 1 2 3 4 5 6 7 8 9 10
45 36 18 53 72 30 48 93 15 36
je
(1) 36 36 18 53 72 30 48 93 15 45
(2) 36 36 18 45 72 30 48 93 15 53
(3) 36 36 18 15 72 30 48 93 45 53
(4) 36 36 18 15 45 30 48 93 72 53
(5) 36 36 18 15 30 45 48 93 72 53