|
Tri bulle est l'un des algorithmes de tri les plus faciles. Il est appelé tri à bulle parce que la il sera valeurs «bulle» dans votre liste vers le haut ( ou en bas selon la façon dont vous pensez à lui ) . S'il est un genre facile , il n'est pas aussi efficace que les sortes les plus avancés , et ne devrait vraiment être utilisé à des fins d'apprentissage (sauf si vous savez que votre liste est presque réglé , auquel cas il n'est pas mauvais ) Choses que vous devez
Un ordinateur qui permet de compiler un langage de programmation ou
Crayon et papier de passer par l'exemple
Afficher plus Instructions
1 je pense que la meilleure façon de discuter de tri à bulles est un exemple. Je vais vous donner un aperçu de l'algorithme , puis nous allons travailler à travers une étape - par - étape pour vous donner une idée de comment cela fonctionne exemple . Alors d'abord , l'idée .
2 Bubble tri est utilisé pour trier la liste des éléments en ordre croissant ou décroissant . Supposons pour ce genre que vous voulez mettre la liste dans l'ordre croissant (ie 1,2,3 , etc.) Le tri fonctionne en passant sur chaque élément de votre liste et en le comparant à l'élément suivant dans la liste. Si le premier élément est plus grand que le deuxième élément , les deux sont commutées . Si le premier élément est inférieure ou égale à la seconde , rien ne se passe . Après avoir regardé cet élément, l'élément suivant est regardé , et le processus se répète .
3 Lorsque le type a examiné chaque élément, un 'pass' est terminée. Après un passage, vous savez avec certitude que seul numéro doit être dans la bonne position . Dans notre ordre croissant, la plus grande valeur sera «bulle» à la fin de la liste . Malheureusement, vous ne savez pas si le reste de la liste est triée , si vous devez prendre un autre passage . Cependant, sur ce passage, vous pouvez vous arrêter un élément avant la fin puisque vous savez que ce nombre est déjà dans la position correcte .
4 Bubble sort ( généralement ) nécessite plusieurs passages à compléter. Les plupart des passes , il demandera est égal au nombre d'éléments dans la liste moins 1. Donc, si vous avez 10 dans votre liste , il pourrait prendre 9 passes pour terminer la sorte . Passons en revue un exemple pour mieux expliquer
5 nous allons utiliser la liste suivante non triés : . 6 , 3, 1 , 8, 2 , 4
Nous tenons la liste à ressembler à ceci: 1 , 2, 3 , 4, 6 , 8
au premier passage , nous allons comparer les chiffres un à la fois , et nous savons que, après un passage que nous devrions avoir le plus grand nombre tout le chemin à droite , donc dans ce cas, ce sera 8. Pour notre exemple , le signe ^ pointera vers la place dans la liste que nous examinons actuellement .
6 6 , 3, 1 , 8, 2 , 4
Col 1 , étape 1) Comparer le 6 et le 3. 6 est supérieur à 3, donc nous allons échanger elles3 , ^ 6, 1 , 8, 2 , 4
Col 1, Step 2 ) Comparez le 6 et le 1. 6 est supérieur à 1, donc nous allons échanger elles3 , 1, ^ 6, 8, 2 , 4
Col 1, étape 3) Comparer le 6 et le 8. 6 est inférieure ou égale à 8 , donc rien happens.3 , 1, 6, 8 ^ , 2, 4
Col 1, étape 4) Comparer le 8 et le 2. 8 est supérieur à 2 , alors échanger elles3 , 1, 6, 2, ^ 8 , 4
Col 1, étape 5) Comparer le 8 et le 4. 8 est supérieur à 4, ainsi échanger elles3 , 1, 6 , 2, 4 , 8
et vous avez terminé la première passe !
7 3, 1, 6, 2, 4, 8 n'est guère une liste triée , mais vous pouvez le voir, comme promis, le 8 est sur la fin. Je vais maintenant écrire ce que la liste ressemble après chaque passage. Essayez vous-même et voir si le vôtre correspond au mien : Pass 2: 1 , 3, 2 , 4, 6 , 8 ( en regardant mieux ) Col 3: 1, 2 , 3, 4 , 6, 8 (fait) Pass 4 : 1 , 2, 3 , 4, 6 , 8 ( euh ... nous n'étions pas déjà fait ? ) Pass 5 : ( ! encore fait) 1, 2 , 3, 4 , 6, 8
8 < p> Comme vous pouvez le voir, la liste a été triée après 3 passes , mais le tri à bulles continué. Pourquoi est-ce? Eh bien, l'algorithme de base de tri bulle est assez stupide . Il veut s'assurer que cela fonctionnera dans le pire des cas (ce qui est une liste qui est complètement à l'envers comme 9, 8, 7, 6, 5). Vous pouvez ajouter une vitesse allant jusqu'à faire votre tri à bulles courir un peu plus vite. À chaque passage , un drapeau qui se prépare à vrai que si vous changez en fait deux chiffres. Avant de faire la passe suivante , vérifier pour voir si le drapeau est vraie ou fausse . Si c'est vrai, vous échangé deux chiffres, et vous devez faire un autre passage . Si c'est faux , votre liste est triée , et vous pouvez être fait. Dans notre exemple, même si la liste a été triée après 3 passes , nous aurions encore besoin de faire une 4ème passe parce que nous avons fait un swap dans le 3ème passage.
9 Maintenant, vous savez comment faire un sorte de bulle . Laissez des commentaires pour toute question que vous pourriez avoir . Merci pour la lecture!
|
