techniques de tri dans la programmation: le tri « bulle »

sorte de bulle est non seulement considérée comme la méthode la plus rapide, de plus, il ferme la liste des plus lentes façons d'organiser. Cependant, elle a ses avantages. Ainsi, la méthode de tri des bulles – plus que ni est une solution naturelle et logique au problème, si vous voulez organiser les éléments dans un ordre spécifique. Une personne ordinaire manuellement, par exemple, il va les utiliser – juste par intuition.

D'où vient un tel nom inhabituel?

Nom de la méthode est venu, en utilisant l'analogie des bulles d'air dans l'eau. Il est une métaphore. De même que les petites bulles d'air vers le haut – parce que leur densité est supérieure à un fluide (dans ce cas – l'eau), et chaque élément de réseau, plus il est la valeur, de façon plus progressive vers le haut des numéros de la liste.

Description de l'algorithme

tri à bulles est réalisée comme suit:

• premier passage: les éléments des numéros de réseau est pris par les deux paires et également comparées. Si certains éléments de l'équipe de deux première valeur est supérieure à la seconde, le programme qui les rend lieux d'échange;
• par conséquent, le plus grand nombre de misses la fin du tableau. Alors que tous les autres éléments restent tels qu'ils étaient, d'une manière chaotique, et nécessitent plus de tri;
• et nécessitent donc un second passage: il est fabriqué par analogie avec la précédente (déjà décrite) et a un certain nombre de comparaisons – moins un;
• au nombre de passage de trois comparaisons, l'une inférieure à la seconde, et les deux, que la première. Et ainsi de suite;
• résumer ce que chaque passage possède (toutes les valeurs de la matrice, le nombre particulier de comparaisons) moins (numéro de passage).

algorithme encore plus court d'un programme peut être écrit:

• un tableau de nombres est sélectionnée aussi longtemps que deux nombres sont trouvés, le second d'entre eux est lié à être plus grande que la première;
• incorrectement positionné par rapport à l'autre des éléments des échanges de logiciels de réseau.

Pseudocode basé sur l'algorithme décrit

La mise en œuvre plus simple est réalisée comme suit:

procédure Sortirovka_Puzirkom;

début

cycle pour j de nachalnii_index à konechii_index;

cycle pour i allant de nachalnii_index à konechii_index-1;

si massif [i]> massiv [i + 1] (premier élément supérieur à une seconde), alors:

(Changer de place des valeurs);

fin

Bien sûr, cette simplicité ne fait qu'aggraver la situation: le plus simple de l'algorithme, plus il manifeste tous les défauts. Taux d'investissement de temps est trop grande, même pour un petit tableau (ici vient en relativité: La quantité de temps pour le profane peut sembler faible, mais en fait un programmeur tous les chefs d'accusation deuxième ou même milliseconde).

Il a fallu la meilleure mise en œuvre. Par exemple, compte tenu de l'échange de valeurs dans des emplacements de tableau:

procédure Sortirovka_Puzirkom;

début

sortirovka = true;

cycle jusqu'à sortirovka = true;

sortirovka = false;

cycle pour i allant de nachalnii_index à konechii_index-1;

si massif [i]> massiv [i + 1] (premier élément supérieur à une seconde), alors:

(Changer de place éléments);

sortirovka = true; (Identifié que l'échange a été fait).

Fin.

limites

Le principal inconvénient – la durée du processus. Combien de temps est effectué algorithme de tri bulle?

délai de réception est calculée à partir du nombre de nombres carrés dans le réseau – le résultat final de celui-ci est proportionnelle.

Si le pire des cas, le tableau est passé autant de fois qu'il a des éléments moins une valeur. Cela se produit parce qu'à la fin il n'y a qu'un seul élément, qui n'a rien à comparer, et la dernière passe à travers le réseau devient une action inutile.

En outre, la méthode efficace de tri d'un simple échange, comme on l'appelle, que pour les tableaux de petite taille. De grandes quantités de données à l'aide de processus ne fonctionnera pas: le résultat sera une erreur ou l'échec du programme.

dignité

sorte de bulle est très facile à comprendre. Les programmes des universités techniques dans l'étude des éléments de commande de sa gamme passe en premier lieu. La méthode est facilement mis en œuvre comme un langage de programmation Delphi (D (Delphi), et le C / C ++ (C / C plus plus), un algorithme très simple pour l'emplacement des valeurs dans l'ordre et au Pascal (Pascal). Genre Bubble est idéal pour les débutants.

En raison des inconvénients de l'algorithme n'est pas utilisé à des fins parascolaires.

Principe de tri visuel

La vue initiale de la matrice 8 22 4 74 44 37 1 7

Étape 8 22 1 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

8 22 4 1 74 44 37 7

Étape 2 1 8 22 4 74 44 7 37

8 22 4 1 74 7 44 37

8 22 4 1 7 74 44 37

8 22 4 1 7 74 44 37

1 8 4 22 7 74 44 37

4 8 22 1 7 74 44 37

Etape 1 4 8 3 22 7 74 37 44

4 8 22 1 7 37 74 44

4 8 22 1 7 37 74 44

1 4 8 7 22 37 74 44

8 1 4 7 22 37 74 44

Étape 4 1 4 7 8 22 37 44 74

8 1 4 7 22 37 44 74

8 1 4 7 22 37 44 74

8 1 4 7 22 37 44 74

Etape 5 1 4 7 8 22 37 44 74

8 1 4 7 22 37 44 74

8 1 4 7 22 37 44 74

Etape 1 4 7 6 8 22 37 44 74

8 1 4 7 22 37 44 74

Etape 1 4 7 7 8 22 37 44 74

exemple de tri bulle Pascal

exemple:

const kol_mas = 10;

var massif: Array [1..kol_mas] de nombre entier;

a, b, k: nombre entier;

commencer

writeln ( 'entrée', kol_mas, 'éléments de réseau');

pour a: = 1 à kol_mas do readln (massif [a ]);

pour: = 1 à kol_mas-1 ne commencent

pour b: = a + 1 à kol_mas ne commencent

si massiv [a]> massiv [ b] then begin

k: = massif [a]; massiv [a]: = massif [ b]; massiv [b]: = k;

fin;

fin;

fin;

writeln ( 'après tri');

pour a: = 1 à kol_mas do writeln (massif [a ]);

fin.

Exemple bulle de tri en langage C (C)

exemple:

#include

#include

int main (int argc, char * argv [])

{

int massiv [8] = {36, 697, 73, 82, 68, 12, 183, 88}, i, ff;

for (;;) {

ff = 0;

for (i = 7; i> 0; i -) {

if (massif [i] <massiv [i- 1]) {

swap (massif [i], massif [i- 1]);

ff ++;

}

}

if (ff == 0) break;

}

getch (); // retard d'affichage

return 0;

}.