Je veux savoir ce qui sera le meilleur cas pour un tri de bulles? Il peut y avoir un cas dans lequel il ne peut y avoir aucun échange pour les 2 derniers passages, par exemple. Je fais mon programme en C langue. Supposons que j'ai un tableau de 5 éléments et je donne les éléments comme 1 2 5 4 3, alors il n'y aurait pas de changement dans les 2 derniers passes?
9 Réponses :
Le meilleur scénario de cas est un seul passage. La liste serait déjà triée.
Aucun échange = fait.
@Jon Sans spécifier l'algorithme Comment pouvez-vous parler de la meilleure complexité des cas. Je pouvais voir beaucoup de mises en œuvre de tri de bulles
@ user567879 Quelle que soit la mise en oeuvre de tri de la bulle, au moins une passe complète est nécessaire pour assurer le tri de la liste. Le meilleur cas est la liste est triée et nécessitera une seule passe pour vérifier cela. en.wikipedia.org/wiki/bubble_sort
@Jon Si vous utilisez une bulle genre comme ceci (premier algorithme) algorithmist.com/index.php/bubble_sort . La meilleure complexité des cas est-elle (n ^ 2)?
@ user567879 n ^ 2 serait votre pire des cas. Pensez à ce qui se passe quand un tri de bulles est exécuté. Si votre liste est déjà triée, il fonctionnera via votre liste une fois pour chaque article. Le meilleur cas est N (nombre d'éléments de la collection), car un tri de bulles nécessitera une vérification de chaque article une fois.
S'il vous plaît voir Tri de bulle :
Le tri des bulles a le pire cas et la moyenne complexité à la fois о (n²), où n est le Nombre d'éléments triés. Là existent beaucoup d'algorithmes de tri avec sensiblement mieux le pire cas ou complexité moyenne de O (n log n). Même autre ® (n²) algorithmes de tri, tels que comme trier l'insertion, a tendance à avoir mieux performance que le tri de la bulle. Donc, le tri de bulles n'est pas un algorithme de tri pratique lorsque n est grand.
- Performance pire des cas o (n²)
meilleures performances de cas o (n) performance moyenne moyenne o (n²) - Complexité pire des espaces O (n) Total, O (1) auxiliaire
- optimal non
Il est difficile de dire si vous voulez dire
o ( n ) ) > Pour une entrée déjà triée.
- Quand, si jamais, vous devriez envisager d'utiliser un tri bulle.
Dans ce dernier cas, vous ne le faites pas, car pour les petits cas, le Tri coquillage et Trier d'insertion surperformera les deux. Certaines des routines de tri les plus performantes que j'ai vues sont des hybrides tri rapides qui utilisent un tri de coquille pour "petites" sections de la matrice.
Ce n'est pas possible pour un tri de bulles de ne pas échanger pour deux passes.
Un laissez-passer sans échange signifie que la liste est déjà triée.
Le meilleur cas est lorsque les données sont déjà triées. Une autre bonne affaire est quand il y a un nombre minuscule d'articles à trier - je l'ai utilisé une fois lorsque ma liste typique était de deux articles et devenue parfois quatre.
Un tri de bulle est rarement votre meilleur cas pour faire une sorte. Il est exceptionnellement lent et inefficace. De nombreux autres algorithmes de tri sont plus rapides. Par exemple, vous pouvez envisager d'utiliser quelque chose comme un tour rapide.
L'algorithme de tri le plus rapide dont je suis au courant a été développé par Steffan Nilsson et est décrit dans l'article suivant.
Si vous voulez simplement savoir comment implémenter un type de bulle, vous pouvez trouver un bon article ici.
Vous voudrez peut-être noter que les sorties les plus rapides sont très souvent spécifiques à une application, bien que presque toutes les applications soient insensibles à ce bénéfice, à côté des dépenses d'optimisation au-delà d'un algorithme général bien écrit (bibliothèque).
meilleur cas: le meilleur cas serait si la liste était déjà triée. a) Il y aura des comparaisons, mais aucun échange d'échanges ni de temps d'exécution n'est dans O (N2) b) Mais si nous gardons une piste d'échanges à chaque passage et résiliant la vérification du programme si aucun échange. Ensuite, le programme n'exigerait qu'une seule passe et max. Les comparaisons (N-1) sont nécessaires dans cette seule passe et nous pouvons dire que la complexité est d'ordre de O (n).
Wikipedia ou je me trompe, mais pour moi, le meilleur cas et les pires cas sont les deux (N2), c'est
à partir de l'introduction du livre à des algorithmes considère si la matrice est triée ou non, il n'y a personne
Becoz même si la ligne 4 est sauté la ligne 2 et 3 sont exécutées de manière proportionnelle
à N2 fois éditer:
Je pense que je l'ai eu Wikipedia, c'est juste après tout, mais il faut modifier le
algorithme en ajoutant allons dire que la variable booléenne is_exchange le réglage sur False avant d'entrer dans la seconde boucle et si c'est faux à nouveau après avoir sorti la boucle, nous sommes terminés et dans ce cas, O (n) Becoz Deuxième boucle est exécutée n Times
Il existe de multiples façons d'écrire l'algorithme de tri des bulles, il semble que, au fil du temps, l'algorithme s'est amélioré et plus efficace. Le premier algorithme de tri des bulles que j'ai appris est ci-dessous. L'algorithme de dessous le meilleur et le pire des cas est O (n ^ 2).
procedure bubbleSort( A : list of sortable items )
n = length(A)
repeat
swapped = false
for i = 1 to n-1 inclusive do
/* if this pair is out of order */
if A[i-1] > A[i] then
/* swap them and remember something changed */
swap( A[i-1], A[i] )
swapped = true
end if
end for
until not swapped
end procedure
Si, par exemple, dans un programme, le tri antérieur de la bulle nécessitait toutes les itérations à effectuer. Cet échange = FALSE aide notre programme à arrêter à tout moment afin de réduire de nombreuses étapes. bien réponse.
Le meilleur cas serait si la liste était déjà triée mais je ne pense pas que c'est ce que vous demandez. Pourriez-vous être plus précis?
Je ne vois pas non plus ce que cela a à voir avec c #