|
Tri d'un tableau de données est l'un des problèmes classiques de l'informatique , et il devrait donc pas s'étonner qu'une grande variété de méthodes de tri en Turbo C et d'autres langues ont été conçus . Elles vont de méthodes inefficaces mais simple à mettre en œuvre des méthodes beaucoup plus rapide mais plus complexe . Le meilleur algorithme pour une situation dépend de la taille attendue de l'ensemble à trier les données et l'importance de l'efficacité. Bubble Trier
The Bubble Trier est la plus simple et la plus lente , algorithme de tri . Il procède simplement à travers la matrice , en comparant l'élément en cours de l'élément en face de celle-ci . Si ces deux éléments sont en panne, ils changent de place . Lorsque la bulle Trier arrive à la fin , il vérifie pour voir si quelque chose a changé lieux . Si c'était le cas , il recommence depuis le début. Il continue en boucle à travers le réseau jusqu'à ce qu'il parvient à compléter un passage complet sans faire aucun échange . En moyenne, cela prend un temps O (n ² ) , mais si les données sont connus pour être très près triée , avec peut-être un seul élément à sa place , il peut travailler en O ( n). Donc, c'est une bonne méthode pour les petits réseaux qui ne sont pas classifiées souvent ou grands tableaux qui sont connus pour être déjà triés ( ou presque ) la plupart du temps .
Sélection Trier
la Sélection tri est légèrement plus raffiné que le tri à bulles . L'algorithme se déroule à travers l'ensemble du réseau de données pour trouver le plus petit élément . Chaque fois que cet élément est , il a troqué sa position avec le premier élément , et un compteur note que le premier élément du tableau est connu pour être correctement triés . Il procède ensuite à travers l'ensemble du réseau à nouveau , à l'exception du premier élément ( qui est connue pour être à la bonne place . ) Quand il trouve l' élément le plus bas , il se déplace à la deuxième place et incrémente le compteur pour indiquer que les deux premiers éléments sont connus pour être triés . Dans l'ensemble, la sélection Trier fonctionne en O ( n ² ) du temps, mais il a un avantage : tout au plus , seules les modifications n-1 se produisent jamais au tableau , puisque chaque élément est seulement déplacé lorsque sa position est connue. Cela en fait un bon algorithme dans certaines situations exotiques où l'écriture des données dans la mémoire prend considérablement plus que de le lire .
Quicksort
Comme son nom l'indique , l' QuickSort est rapide. En moyenne , il peut effectuer un tri en temps O ( n log n). Mais il est beaucoup plus complexe que de nombreux autres programmes et nécessite que le développeur sait un peu plus sur les données de la matrice avant la main. Tout d'abord, une «valeur pivot " doit être choisie. C'est la valeur que le promoteur croit est proche de la médiane de toutes les valeurs dans le tableau . Le mieux la valeur de pivot , plus le Quicksort se produira . Ensuite , le tableau est divisé en deux groupes: ceux au-dessus de la valeur pivot sont déplacés vers la droite , et ceux au-dessous de la valeur pivot sont déplacés vers le côté gauche. Espérons que les deux parties sont près d'être égaux en taille, mais ils n'ont pas besoin d' être exactement le même . Enfin, l'algorithme de tri rapide recommence à partir de zéro , de chaque côté , avec le nouveau pivot valeurs choisies , et ces moitiés sont finalement divisée en quartiers . Lorsque le tri rapide a subdivisé le tableau de sorte que chaque section a une seule valeur , le tableau a été trié .
Comme la plupart des algorithmes récursifs , cela peut être difficile à visualiser , vous êtes encouragés à voir le étape par étape - exemple donné dans la troisième référence .
|
