Le tri à bulles n'est pas seulement considéré comme le plusméthode rapide, de plus, il ferme la liste des méthodes de commande les plus lentes. Cependant, il a aussi ses avantages. Ainsi, le tri par la méthode des bulles est la solution la plus logique et la plus naturelle au problème, si vous devez organiser les éléments dans un certain ordre. Une personne ordinaire, par exemple, l'utilisera manuellement - juste par intuition.
D'où vient ce nom inhabituel ?
Le nom de la méthode a été inventé en utilisant une analogie avecbulles d'air dans l'eau. Ceci est une métaphore. Tout comme les petites bulles d'air montent vers le haut - après tout, leur densité est supérieure à celle de n'importe quel liquide (dans ce cas, de l'eau), de sorte que chaque élément du réseau, plus sa valeur est petite, plus il se dirige progressivement vers le début de la liste des nombres.
Description de l'algorithme
Le tri par bulles se fait comme suit :
- premier passage : les éléments du tableau de nombres sont pris par deux et sont également comparés deux à deux. Si dans quelques deux éléments la première valeur s'avère supérieure à la seconde, le programme échange leurs places ;
- par conséquent, le plus grand nombre se retrouve à la fin du tableau. Alors que tous les autres éléments restent, pour ainsi dire, dans un ordre chaotique et nécessitent toujours un tri;
- par conséquent, la deuxième passe est nécessaire: elle est effectuée par analogie avec la précédente (déjà décrite) et comporte le nombre de comparaisons - moins une ;
- la passe numéro trois a une comparaison de moins que la seconde et deux de moins que la première. Etc;
- pour résumer, chaque passe a (valeurs totales dans le tableau, un nombre spécifique) moins (numéro de passe) comparaisons.
Encore plus court, l'algorithme du futur programme peut s'écrire comme suit :
- un tableau de nombres est vérifié jusqu'à ce que deux nombres soient trouvés, et le second d'entre eux doit être supérieur au premier ;
- le programme échange les éléments du tableau mal situés les uns par rapport aux autres.
Pseudocode basé sur l'algorithme décrit
La mise en œuvre la plus simple est la suivante :
La procédure Sortirovka_Puzirkom;
Le commencement
cycle pour j de nachalnii_index avant konechii_index;
cycle pour et de nachalnii_index avant konechii_index-1;
si masseiv [i]> masseiv [i + 1] (le premier élément est supérieur au second), alors :
(changer les valeurs par endroits);
la fin
Bien sûr, ici la simplicité ne fait qu'exacerbersituation : plus l'algorithme est simple, plus toutes les lacunes y apparaissent. Le coût du temps est trop élevé même pour un petit tableau (ici la relativité entre en jeu : pour un profane, le temps peut sembler petit, mais dans le métier d'un programmeur, chaque seconde ou même une milliseconde compte).
Une meilleure mise en œuvre s'imposait. Par exemple, en tenant compte de l'échange de valeurs dans le tableau par lieux :
La procédure Sortirovka_Puzirkom;
Le commencement
sortirovka = vrai ;
vélo au revoir sortirovka = vrai ;
sortirovka = faux ;
cycle pour et de nachalnii_index avant konechii_index-1;
si masseiv [i]> masseiv [i + 1] (le premier élément est supérieur au second), alors :
(on échange les éléments par endroits) ;
sortirovka = vrai ; (indiquait que l'échange avait été effectué).
La fin
Inconvénients de la méthode
Le principal inconvénient est la durée du processus. Combien de temps prend l'algorithme de tri à bulles ?
Le temps d'exécution est calculé à partir du carré du nombre de nombres dans le tableau - le résultat final lui est proportionnel.
Dans le pire des cas, le tableau sera parcouruautant de fois qu'il y a d'éléments moins une valeur. C'est parce qu'à la fin, il ne reste qu'un seul élément avec rien à comparer, et le dernier passage dans le tableau devient une action inutile.
De plus, la méthode de tri par simpleéchanges, comme on l'appelle aussi, uniquement pour les petits tableaux. Il ne sera pas possible de traiter de grandes quantités de données avec son aide: le résultat sera soit des erreurs, soit un échec du programme.
Avantages
Le tri à bulles est très facile à comprendre.Dans les programmes des universités techniques, lors de l'étude de l'ordre des éléments du tableau, il est le premier à le réussir. La méthode est facilement implémentée à la fois dans le langage de programmation Delphi (D (Delphi) et en C/C++ (C/C plus plus), un algorithme incroyablement simple pour organiser les valeurs dans le bon ordre, et en Pascal. Bubble. sort est idéal pour les débutants.
En raison de lacunes, l'algorithme n'est pas utilisé à des fins parascolaires.
Principe de tri clair
Vue initiale du réseau 8 22 4 74 44 37 1 7
Étape 1 8 22 4 74 44 37 1 7
8 22 4 74 44 1 37 7
8 22 4 74 1 44 37 7
8 22 4 1 74 44 37 7
8 22 1 4 74 44 37 7
8 1 22 4 74 44 37 7
1 8 22 4 74 44 37 7
Étape 2 1 8 22 4 74 44 7 37
1 8 22 4 74 7 44 37
1 8 22 4 7 74 44 37
1 8 22 4 7 74 44 37
1 8 4 22 7 74 44 37
1 4 8 22 7 74 44 37
Étape 3 1 4 8 22 7 74 37 44
1 4 8 22 7 37 74 44
1 4 8 22 7 37 74 44
1 4 8 7 22 37 74 44
1 4 7 8 22 37 74 44
Étape 4 1 4 7 8 22 37 44 74
1 4 7 8 22 37 44 74
1 4 7 8 22 37 44 74
1 4 7 8 22 37 44 74
Étape 5 1 4 7 8 22 37 44 74
1 4 7 8 22 37 44 74
1 4 7 8 22 37 44 74
Étape 6 1 4 7 8 22 37 44 74
1 4 7 8 22 37 44 74
Étape 7 1 4 7 8 22 37 44 74
Exemple de tri à bulles en Pascal
Exemple:
const kol_mas = 10;
var massiv : tableau [1..kol_mas] d'entiers ;
a, b, k : nombre entier ;
commencer
writeln ("entrée", kol_mas, "éléments du tableau");
pour a : = 1 à kol_mas do readln (massiv [a]) ;
pour a : = 1 à kol_mas-1 ne commence
pour b : = a + 1 à kol_mas ne commence
si massiv [a]> massiv [b] alors commencer
k : = massiv [a] ; masseiv [a] : = masseiv [b] ; masseiv [b] : = k ;
fin;
fin;
fin;
writeln ("après tri");
pour a : = 1 à kol_mas do writeln (massiv [a]) ;
finir.
Un exemple de tri à bulles en C (C)
Exemple:
#comprendre
#comprendre
int main (int argc, char * argv [])
{
int massiv [8] = {36, 697, 73, 82, 68, 12, 183, 88}, i, ff ;
pour (;;) {
ff = 0 ;
pour (i = 7; i> 0; i -) {
si (massiv [i] <massiv [i-1]) {
échanger (massiv [i], massiv [i-1]);
ff ++;
}
}
si (ff == 0) cassure ;
}
getch (); // délai d'écran
renvoie 0 ;
}.
