Taille de bulles avec java

Le tri des bulles est l'algorithme de tri le plus simple: supposons qu'il y a des éléments consécutifs qui ne sont pas triés. Le tri de bulles scanne la ligne de la gauche, échangeant n'importe quelle paire d'éléments adjacents qui ne sont pas dans le bon ordre. Ce balayage de toute la ligne est répété à plusieurs reprises jusqu'à ce que toute la ligne soit triée. Si le tri doit s'assembler, la paire adjacente est échangée pour rendre l'élément à gauche moins que l'élément à droite. Si le tri descendant, alors la paire adjacente est échangée pour rendre l'élément à gauche supérieur à l'élément à droite.

Illustration de tri à bulles sans code

Considérez la liste de lignes non triées suivantes des caractères de l'alphabet:

Q w e r t y u i o p

Cette liste sera triée par ordre croissant comme suit. Dans le premier scan, Q et W sont comparés; Q est inférieur à W, il n'y a donc pas d'échange. Pourtant, dans le premier scan, W et E sont comparés; E est inférieur à W, il y a donc un échange. Le nouveau troisième élément, W, est comparé à R; R est inférieur à W, il y a donc un échange. Le nouveau quatrième élément, W, est comparé à t; T est moins que w, donc il y a des échanges. Le nouvel cinquième élément, W, est comparé à Y; W est inférieur à Y, et il n'y a pas d'échange. Pourtant, dans le premier scan, y est comparé à u; U est moins de y, donc il y a des échanges. Le nouvel septième élément, y, est comparé à i; Je suis moins de Y, et il y a des échanges. Le nouvel huitième élément, y, est comparé à O; O est inférieur à Y, et il y a des échanges. Le nouvel élément neuvième, Y, est comparé à P; P est inférieur à Y, et il y a des échanges. Le premier scan se termine là. Le résultat pour le premier scan est,

Q e r t w u i o p y

Notez que le plus grand élément est à la fin après le premier scan. Le balayage de tous les dix éléments résultants et l'échange possible est répété à nouveau pour avoir:

E r q t u i o p w y

Notez que le prochain élément le plus grand est maintenant le dernier mais un élément, et il n'était pas nécessaire de le comparer avec le dernier élément, donc un petit temps n'aurait pas été gaspillé. Le balayage de tous les dix éléments résultants et l'échange possible est répété à nouveau pour avoir:

E q r t i o p u w y

Notez que le troisième plus grand élément vers la fin est maintenant à la troisième position de la fin, et il n'était pas nécessaire de le comparer avec les deux derniers éléments, et pas besoin de comparer les deux derniers éléments eux-mêmes, et donc un peu de petit temps n'aurait pas été gaspillé. Le balayage de tous les dix éléments résultants et l'échange possible est répété à nouveau pour avoir:

E q r i o p t u w y

Notez que le quatrième plus grand élément vers la fin est maintenant à la quatrième position de la fin, et il n'était pas nécessaire de le comparer avec les trois derniers éléments, et pas besoin de comparer les trois derniers éléments eux-mêmes, et donc un certain temps ne serait pas ont été gaspillés. Le balayage de tous les dix éléments résultants et l'échange possible est répété à nouveau pour avoir:

E q i o p r t u w y

Notez que le cinquième plus grand élément vers la fin est maintenant à la cinquième position de la fin, et il n'était pas nécessaire de le comparer avec les quatre derniers éléments, et pas besoin de comparer les quatre derniers éléments eux-mêmes, et donc le temps n'aurait pas été gaspillé. Le balayage de tous les dix éléments résultants et l'échange possible est à nouveau répété pour avoir:

E i o p q r t u w y

Le reste des résultats de numérisation est le suivant:

E i o p q r t u w y
E i o p q r t u w y
E i o p q r t u w y
E i o p q r t u w y

Notez qu'aucun tri n'a eu lieu pour ces quatre derniers résultats.

L'inverse de tous les algorithmes ci-dessus peut être fait pour le tri descendant.

Optimisation du tri des bulles

D'après la définition de base du tri des bulles, s'il y a n éléments, alors il y aura n analyses complètes. Un scan est une itération. Ainsi, les dix éléments ci-dessus signifient dix itérations complètes. La durée totale pour trier une liste (tableau) peut être réduite pour de nombreuses listes non triées. Cela implique des stratégies de tri de bulles. Le tri des bulles est optimisé avec deux stratégies.

Première stratégie d'optimisation

Remarquez de ce qui précède que, après la première itération complète, le plus grand élément est à la fin, et ce serait une perte de temps y accéder dans la deuxième itération. Après la deuxième itération, les deux derniers éléments sont dans leurs bonnes positions, et le temps ne devrait pas être gaspillé en y accédant dans la troisième itération. Cela signifie que la deuxième itération devrait se terminer à N-1. Après la troisième itération, les trois derniers éléments sont dans leurs bonnes positions, et le temps ne devrait pas être gaspillé en y accédant dans la quatrième itération. Cela signifie que la troisième itération devrait se terminer à N-2. Après la quatrième itération, les quatre derniers éléments sont dans leurs bonnes positions, et le temps ne devrait pas être gaspillé en y accédant dans la cinquième itération. Cela signifie que la quatrième itération devrait se terminer à N-3. Cela continue.

D'après la définition de base du tri des bulles, l'itération doit être effectuée n fois. Si le compteur pour les n itérations est à I, alors l'itération doit accéder aux éléments n - i pour éviter de perdre du temps à la fin du tableau; Et avec je commençant à partir de 0. Il doit donc y avoir deux boucles Java: la boucle extérieure itère n fois, et la boucle intérieure itère n - i fois, pour les éléments du tableau, pour chacun des n fois. Ilérer un tableau N - I Times est la première stratégie.

Deuxième stratégie d'optimisation

Si la boucle externe est-elle vraiment itrérée n fois? Si la boucle externe pour la liste ci-dessus itérera 10 fois? - Non, parce que ses quatre dernières itérations ne changeraient rien (il ne fait aucun tri). Cela signifie que la liste a été triée dès qu'elle est détectée; La boucle extérieure doit se casser, donc le tri doit s'arrêter. Cela gagnera plus de temps. Cela peut être réalisé en ayant une variable booléenne pour la boucle externe, qui resterait fausse dans la boucle intérieure lors de l'échange de arrêts.

Code java pour le tri des bulles

La classe suivante a la méthode pour faire le tri:

classe ACLASS
Vide Bubblesort statique (char arr [])
int n = arr.longueur;
booléen échangé = false;
pour (int i = 0; i < N; i++)
échangé = false;
pour (int j = 1; j < N - i; j++)
if (arr [j] < arr[j - 1])
char temp = arr [j];
arr [j] = arr [j - 1];
arr [j - 1] = temp;
échangé = true;


if (échangé == false) Break;

Notez la condition de la condition: «J < N - i;” for the inner for-loop, for the first strategy. Note the use of the boolean variable in the outer for-loop and the inner for-loop for the second strategy.

Une classe principale appropriée pour cela est:

classe publique TheClass
public static void main (String [] args)
char ar [] = 'q', 'w', 'e', ​​'r', 't', 'y', 'u', 'i', 'o', 'p';
Une classe.Bubblesort (AR);
pour (int i = 0; iSystème.dehors.print (ar [i]); Système.dehors.imprimer(' ');

Système.dehors.println ();

Le tableau est passé par référence à la méthode bubblesort () dans une classe différente. Donc son contenu est modifié. La sortie est:

E i o p q r t u w y

Conclusion

Toi de bulles en échangeant des éléments adjacents du début à la fin de la liste. Cette procédure est répétée encore et encore jusqu'à ce que toute la liste soit complètement triée. Le tri est monté ou descendant. Le tri des bulles doit être optimisé, comme expliqué ci-dessus.