Tri est l'une des fonctions les plus élémentaires et les plus utiles appliquées aux données. Il vise à organiser les données d'une manière particulière, qui peut être croissante ou décroissante selon les besoins. Il existe une fonction intégrée dans C ++ STL sous le nom de «sort ()» qui nous permet d’exécuter facilement un algorithme de tri. Dans cet article, nous explorerons la fonction de tri en C ++,
Les pointeurs suivants seront traités dans cet article:
- Fonction Sort ()
- Exemple - Pour trier les données par ordre croissant
- Exemple - Pour trier les données par ordre décroissant
- Partial_sort
Passer à cet article sur la fonction de tri en C ++
Trier ( ) fonction
C'est une fonction intégrée du fichier d'en-tête d'algorithme, elle est utilisée pour trier les conteneurs comme un tableau, les vecteurs dans un ordre spécifié. En interne, cette fonction est implémentée en tant que tri rapide
Quicksort est un algorithme de division et de conquête. Quicksort divise d'abord une grande liste d'éléments en deux sous-listes plus petites: les éléments inférieurs et les éléments supérieurs. Quicksort trie ensuite récursivement les sous-listes.
Les étapes sont les suivantes:
1. Choisissez un élément aléatoire (généralement le dernier élément), appelé pivot, dans la liste.
2. Réorganisez la liste de telle sorte que tous les éléments avec des valeurs inférieures au pivot viennent avant le pivot, tandis que tous les éléments avec des valeurs supérieures au pivot viennent après lui et des valeurs égales peuvent aller dans les deux sens, ce processus est appelé opération de partition.
3. Triez récursivement la sous-liste des éléments inférieurs et la sous-liste des éléments supérieurs, sélectionnez à nouveau un pivot dans la sous-liste et divisez-les.
Le cas de base de la récursivité est des listes de taille zéro ou un, qui n'ont jamais besoin d'être triées et donc en les combinant, nous trions notre liste.
Quicksort est en pratique plus rapide que les autres algorithmes O (n log n) tels que le tri par insertion ou le tri par bulles. Quicksort peut être implémenté avec un algorithme de partitionnement sur place, ce qui signifie que tout le tri peut être effectué avec seulement O (log n) d'espace supplémentaire. Quicksort n'est pas une sorte stable.
Sa complexité est la suivante:
Meilleur cas - O (n log n)
Pire cas - O (n ^ 2)
Cas moyen - O (n log n)
Syntaxe:
trier (premier, dernier)
Ici,
first - est l'index (pointeur) du premier élément de la plage à trier.
last - est l'index (pointeur) du dernier élément de la plage à trier.
Par exemple, nous voulons trier les éléments d'un tableau «arr» de 1 à 10 positions, nous utiliserons sort (arr, arr + 10) et il triera 10 éléments par ordre croissant.
Valeur de retour
Aucun
Complexité
La moyenne d'une complexité de tri est N * log2 (N), où N = dernier - premier.
Plage de données
Les objets de la plage [premier, dernier) sont modifiés.
Exceptions
Les surcharges avec un paramètre de modèle nommé ExecutionPolicy signalent les erreurs comme suit:
Si l'algorithme ne parvient pas à allouer de la mémoire, std :: bad_alloc est renvoyé comme une exception.
Si l'exécution d'une fonction invoquée dans le cadre de l'algorithme, elle lève une exception std :: terminate.
Passer à cet article sur la fonction de tri en C ++
Exemple - Pour trier les données par ordre croissant:
#include using namespace std int main () {int array [] = {10, 35, 85, 93, 62, 77, 345, 43, 2, 10} int n = sizeof (array) / sizeof (array [0] ) // 'sizeof' donne la taille du tableau total ie la taille de chaque caractère * no. de caractères // donc pour obtenir non. de caractères // nous divisons la taille de (tableau) par la taille de n'importe quel caractère du tableau // ici c'est tableau [0] sort (tableau, tableau + n) cout<< 'nArray after sorting using ' 'default sort is : n' for (int i = 0 i < n ++i) cout << array[i] << ' ' return 0 } Production :
fonction fibonacci c ++
Explication
Dans l'exemple ci-dessus, nous voyons que la fonction sort () trie par défaut un tableau dans l'ordre croissant.
Passer à cet article sur la fonction de tri en C ++
Exemple - Pour trier les données par ordre décroissant:
Pour trier les données du tableau par ordre décroissant, nous devons introduire un troisième paramètre qui est utilisé pour spécifier l'ordre dans lequel les éléments doivent être triés. Nous pouvons utiliser la fonction «greater ()» pour trier les données par ordre décroissant.
#include using namespace std int main () {int array [] = {41, 53, 4, 459, 60, 7, 23, 4, 232, 10} int n = sizeof (array) / sizeof (array [0] ) sort (tableau, tableau + n, supérieur ()) cout<< 'Array after sorting : n' for (int i = 0 i < n ++i) cout << array[i] << ' ' return 0 } Production:
Exp l une nation
Ici, la fonction sort () fait une comparaison d'une manière qui place un plus grand élément avant.
Passer à cet article sur la fonction de tri en C ++
Partial_sort
C ++ STL nous fournit une fonction de tri partiel, la fonction est similaire à la fonction sort () mais contrairement à la fonction sort (), elle n'est pas utilisée pour trier toute la plage, elle est utilisée pour en trier seulement une sous-partie. Il trie les éléments dans la plage de [premier, dernier), de telle manière que les éléments avant l'élément central sont triés par ordre croissant, tandis que les éléments après le milieu sont laissés tels quels.
Il peut être utilisé pour trouver le plus grand élément si nous utilisons un objet fonction pour trier la première position
Exemple
tutoriel web ruby on rails
#include #include #include using namespace std int main () {vector vec = {10, 45, 60, 78, 23, 21, 30} vector :: iterator iptr partial_sort (vec.begin (), vec.begin () + 1, vec.end (), supérieur ()) iptr = vec.begin () cout<< 'The largest element is = ' << *iptr return 0 } Production:
Explication:
Le code ci-dessus peut être utilisé pour trouver le plus grand nombre d'une série, pour trouver le plus petit nombre d'une série, il suffit de supprimer la commande la plus grande.
Nous sommes donc arrivés à la fin de cet article sur «Fonction de tri en C ++». Si vous souhaitez en savoir plus, consultez la formation Java d'Edureka, une entreprise de formation en ligne de confiance. Edureka Ces cours sont conçus pour vous former aux concepts Java de base et avancés ainsi qu'à divers frameworks Java tels que Hibernate et Spring.
Vous avez une question pour nous? Veuillez le mentionner dans la section commentaires de ce blog et nous vous répondrons dans les plus brefs délais.