tri. STL (partie 12)




tri dans c ++, stlIl est un groupe spécial d'algorithmes de tri font - en pratique, il est nécessaire de trier une variété d'objets et sur une variété de critères. Une analyse des algorithmes de tri sont bien et étudié à fond, Plus que toute autre section de mathématiques computationnelles. Le principal problème de tout algorithme de tri est sa complexité de calcul - le nombre d'opérations de comparaison d'échange, nécessaire pour le tri d'une séquence de longueur N, que l'on appelle O( N ).

Le fait est que désagréable, que la complexité moyenne des différents algorithmes pour différents (sur la plupart des séquences de test) et la complexité maximale (au pire, d'un procédé de séquence de test). Depuis plusieurs dizaines d'algorithmes de tri, offert dans la programmation d'apprentissage, montré, que la grande majorité d'entre eux (intuitif) Il est le pire en termes de moyenne et en termes de complexité maximale. A titre d'exemple,, populaire parmi les étudiants bubble sort Il est le pire de tous généralement connus.

efficace (complexité) l'ensemble des méthodes ne sont que quelques méthodes de tri récursive rapide. Ils sont ensuite présentés aux implémentations de la STL d'algorithmes. Les normes ne pas insister sur une contrainte dure sur les mécanismes nationaux pour leur mise en œuvre, il peut donc être possible en fonction de la bibliothèque.

maintenant, ayant une certaine connaissance de algorithmes, foncteur et l'état général des affaires avec tri, nous sommes prêts à envisager des options pour la mise en œuvre tout cela dans votre code. Pour commencer une variété de façons séquence tri numérique. Exemple Velikon, mais il est non seulement, et que, pour illustrer le, pour la suite auto-expérimentation:

Avant de compiler le programme, en MVS appuyez sur Alt + F7 et entrez les arguments de commande ?30 +3:tri dans c ++

Quelques exemples gaucherie en raison du fait, que nous sommes dans le même code et combinons tous STL fourni des algorithmes de tri, et une variété de tests triée séquence, par exemple:

  • Plusieurs aléatoire (?) des séquences de longueur 30, sortable en utilisant (3) Comparaison de foncteur, et détaillé (+) des séquences d'entrée et de sortie du terminal:

    tri dans c ++

  • inverti (inverser, réduction) séquence, sortable (6) "Heap" en utilisant un arbre binaire (arguments de commande -30 +6 ):tri dans c ++

  • long (1000000) séquence, le même, le cas précédent, conditions de, mais seulement avec la conclusion de l'exactitude des résultats de diagnostic (arguments de commande -1000000 6 ):

    tri dans c ++

Les offres de la STL 3 algorithmes de groupe tri:

  • Trier() – le tri le plus rapide, en moyenne, ( la( N * bûche( N ) ), mais qui peut "tomber" dans le pire des cas à O( N * N ) (et il est un très mauvais indicateur);

  • sort_heap() – le tri "sur le tas", en utilisant un arbre binaire, dont la complexité toujours pas pire que O( N + N * bûche( N ) ) (pire Trier() en moyenne,, mais plutôt le pire des cas);

  • stable_sort() – "Stable" tri par fusion, ce qui signifie que la stabilité, qu'il maintienne l'ordre relatif des éléments égaux après triage. Il est parfois très important. La complexité de cet algorithme est bien inférieur Trier();

Utilisez l'algorithme, qui est le plus compatible avec les contraintes de votre problème.

Bulletin de nouvelles leçons sur la programmation:

tri. STL (partie 12)
3 (60%) 2 votes

Sur huile

une expérience pratique sur le développement de logiciels 40 ans. société de logiciels internationale Global Teacher Logic. IBM Developer Works auteur permanent des publications. éditeur scientifique de l'ordinateur littérature maison d'édition "Symbole-Plus", Saint-Pétersbourg.

Laisser un commentaire

Votre adresse email ne sera pas publiée. les champs requis sont indiqués *