|
Avec littéralement des dizaines d' algorithmes de tri disponibles , de déterminer ce qui fonctionnera le mieux avec votre système dépendra des comparaisons de plusieurs facteurs, tels que la taille de la liste , la vitesse ou la complexité de l'algorithme, et si vous allez utiliser une clé de tri . Complexité
La complexité d'un algorithme de tri est mesurée par O ( n) , ou «l'ordre de n ", où n est la taille de la liste. Il mesure le nombre passe qu'il faut pour trier la liste et calcule son meilleur, le pire et le temps moyen de le faire. Complexités communs comprennent la N comme le meilleur des cas pour les sortes telles que tri par insertion et le tri de la coquille , n log n, (en utilisant un logarithme en base 2 , pas une base -10) , qui est la complexité de tri par fusion et heapsort , et n ² , ce qui est plus lente que la première fois et est la vitesse de la sélection sorte
liste Condition
Parfois, vous saurez comment les éléments non triés dans la liste sont organisées. : par exemple, si elles sont presque triés, dans l'ordre inverse , ou une liste avec quelques pièces uniques . Cette connaissance vous permet de sélectionner un algorithme efficace de faire le tri . Par exemple , en utilisant le tri par insertion pour trier la liste dans l'ordre inverse a une durée de n ² , tandis tas tri peut le faire plus rapidement , en n log n fois . Sur une liste qui est presque réglé , le tri par insertion est plus rapide que tas sorte . Lorsque la liste contient un ensemble complètement aléatoire de données , sélectionnez un algorithme avec une complexité en moyenne de n log n fois consécutive, comme tas tri , le tri rapide ou le tri par fusion .
Liste Taille
Certains algorithmes sont plus difficiles à utiliser que les autres, de sorte que le nombre d'éléments dans une liste et combien de fois vous avez besoin de trier peut aider à déterminer l'algorithme que vous choisirez . Trie comme le tri par insertion sont rapides et fonctionnent bien quand vous triez petites listes , et sont faciles à mettre en œuvre, mais ils sont lents avec des listes plus larges. Trie qui utilisent un fossé et conquérir algorithme tel que le tri rapide et le tri par fusion sont plus difficiles à mettre en œuvre, mais ils listes sorte plus rapidement dans les cas moyens.
Stabilité
stabilité de l'algorithme décrit si le tri conserve l'ordre des éléments basés sur une clé de tri. Par exemple , en utilisant le premier caractère comme une clé pour une liste qui a " John ", " Steve " et " Jim " dans cet ordre , une écurie sortes d'algorithmes la liste de « John », « Jim » et « Steve », tandis que un algorithme instable peut ou ne peut pas trier "Jim" avant " John ". Fusion, tri d'insertion et tri à bulles sont stables tandis que tous les algorithmes sorte de coquille , tri par sélection et tri en tas sont pas.
|
