Day: 24 Desember 2018

Exemple de tri a bulle

Le tableau 1 indique le nombre de comparaisons pour chaque passe. Pour faciliter le problème, nous utilisons une variable de drapeau échangé qui nous aidera à voir si un swap est arrivé ou non. L`algorithme a besoin d`une passe entière sans aucun swap pour savoir qu`il est trié. Le tri à bulles doit être évité dans le cas de grandes collections. Si le plus petit élément est à la fin de la liste, il faudra n − 1 passes pour le déplacer au début. Le tri de cocktail est un tri de bulle bidirectionnel qui va du début à la fin, puis se renverse, se termine au commencement. Lignes 5-7 dans ActiveCode 1 effectuez l`échange des éléments (i ) et ((i + 1) th ) à l`aide de la procédure en trois étapes décrite précédemment. Cas limites: le tri par bulles prend un minimum de temps (ordre de n) lorsque les éléments sont déjà triés. Il reste des éléments (n-1 ) à trier, ce qui signifie qu`il y aura des paires (n-2 ). L`algorithme, qui est un tri de comparaison, est nommé pour la façon dont les éléments plus petits ou plus grands “bulle” vers le haut de la liste. ActiveCode 1 affiche la fonction bubbleSort complète.

Bien que le tri par bulles soit l`un des algorithmes de tri les plus simples à comprendre et à implémenter, sa complexité O (N2) signifie que son efficacité diminue considérablement sur les listes de plus d`un petit nombre d`éléments. C`est un bon rappel à regarder sur le contenu en temps réel. Une autre question que nous n`avons pas l`adresse dans notre algorithme d`origine et son Pseudo improvisé, c`est que, après chaque itération les valeurs les plus élevées s`installe à la fin de la matrice. Ces opérations d`échange «gaspillées» sont très coûteuses. En règle générale, l`échange de deux éléments dans une liste nécessite un emplacement de stockage temporaire (un emplacement de mémoire supplémentaire). L`instruction a, b = b, a entraînera l`exécution de deux instructions d`assignation en même temps (voir la figure 2). Complexité du temps de cas le plus défavorable et moyen: O (n * n). Cela peut provoquer quelques problèmes de complexité comme ce que si le tableau n`a pas besoin de plus d`échange que tous les éléments sont déjà ascendants. Et quand il n`y a aucun swap requis, les sortes de bulles apprend qu`un tableau est complètement trié. Pour ces raisons beaucoup de manuels d`algorithme modernes évitent d`utiliser l`algorithme de tri de bulle en faveur du tri d`insertion. En raison de sa simplicité, le tri par bulles est souvent utilisé pour introduire le concept d`un algorithme de tri. Pour être précis, nous montrons maintenant comment un tableau doit ressembler après chaque itération.

Sans le stockage temporaire, une des valeurs serait remplacée. Le pire cas se produit lorsque Array est inversé trié. Cependant, certains chercheurs comme Owen Astrachan ont fait de grands efforts pour démêler le genre de bulle et sa popularité continue dans l`éducation en informatique, recommandant qu`il ne soit plus même enseigné. Toutefois, étant donné que le tri par bulles effectue des passages à travers la partie non triée entière de la liste, il a la capacité de faire quelque chose que la plupart des algorithmes de tri ne peuvent pas. Cela signifie que pour les listes qui nécessitent seulement quelques passes, un tri de bulle peut avoir un avantage en ce qu`il reconnaîtra la liste triée et s`arrêtera. Implémentation optimisée: la fonction ci-dessus exécute toujours O (n ^ 2) temps même si le tableau est trié. Il prend la liste comme un paramètre, et le modifie en échangeant des éléments si nécessaire. Le tri par bulles compare la valeur du nœud actuel avec le nœud suivant immédiat et les swaps en fonction de l`exigence et va jusqu`au dernier élément. Le tri par peigne compare les éléments séparés par de grandes lacunes, et peut déplacer les tortues très rapidement avant de passer à des intervalles plus petits et plus petits pour lisser la liste.

Notez que nous aurions également pu utiliser l`assignation simultanée pour échanger les éléments. Deuxième passe: (1 4 2 5 8) – > (1 4 2 5 8) (1 4 2 5 8) – > (1 2 4 5 8), swap depuis 4 > 2 (1 2 4 5 8) – > (1 2 4 5 8) (1 2 4 5 8) – > (1 2 4 5 8) maintenant , le tableau est déjà trié, mais notre algorithme ne sait pas si elle est terminée. Dans chaque étape, les éléments écrits en gras sont comparés. Les expériences par les chaînes de tri Astrachan dans le type de bulle de Java montrent à environ un cinquième aussi rapide qu`un tri d`insertion et 70% aussi rapide qu`un tri de sélection. Des modifications alternatives, telles que la tentative de tri Shaker cocktail pour améliorer la performance de tri à bulles tout en gardant la même idée de comparer à plusieurs reprises et d`échanger des éléments adjacents.