Quicksort et ne vous embêtez pas?

Surtout lors de l'écriture d'applications «standard» (non HPC), considérez-vous quel algorithme de tri choisir, ou tout simplement régler avec quicksort (qui est ce que la plupart des bibliothèques appellent simplement tri)? Dans une certaine mesure, cela peut être rentable dans des situations spécifiques, mais d'autre part, une bonne optimisation nécessite un certain temps pour analyser le problème et établir des repères.

En général, l'utilisation des méthodes par défaut, sauf s'il existe un besoin spécifique de faire quelque chose de plus exotique, garde tout beaucoup plus lisible / compréhensible à mon humble avis.

Si vous rencontrez (ou dans certains cas, soupçonnez fortement) que vous avez un problème de performances, il est temps d'ajouter de la complexité.

D'un autre côté, si vous utilisez un langage suffisamment bas pour qu'il n'y ait pas de tri intégré pour le type d'objets que vous devez trier, essayez de choisir un ou deux qui couvrent toutes vos bases et implémentez-les.

Appelez toujours les routines de bibliothèque fournies, à moins que vous n'ayez de très, très bonnes raisons de ne pas le faire (et que vous ayez besoin de documenter pourquoi il en est ainsi).

C'est parce que les algorithmes de tri sont difficiles à obtenir absolument. Il y avait un bogue dans le quicksort Java avec de très grands ensembles de données, qui a été identifié, corrigé et remis aux clients par Sun, vous n'avez donc pas à le faire.

Le tri par défaut dans Java 7 a également été mis à niveau vers un tri plus récent et meilleur. Aussi gratuitement.

À moins que le défaut est un peu démontrable pas assez bon pour vous, rester avec elle.

Lors d'une conférence, j'ai entendu une belle histoire à ce sujet.

Chez Microsoft, quelqu'un écrivait une application VB (c. VB 3) et a envoyé un paquet de personnes disant qu'il avait une charge de valeurs et qu'il voulait qu'elles apparaissent dans la zone de liste déroulante dans l'ordre, comment devrait-il s'y prendre.

Tout le monde a plongé pour ses vieux manuels d'informatique, recherchant des routines très efficaces, les portant sur Visual Basic et les lui envoyant par la poste. Un gars vient de renvoyer "combien de valeurs dans la liste déroulante?".

"Environ 50" est venu la réponse.

Msgstr "Définissez simplement la propriété triée sur TRUE".

Dans 99,9999% des cas, le tri est mieux effectué à l'aide d'une bibliothèque, d'un contrôle ou de la sélection SQL car la différence de performances entre la routine de bibliothèque et tout ce que vous écrivez sera négligeable et l'effort et la surcharge de maintenance l'emporteront largement sur les conséquences.

C'est le moment de tirer la citation classique sur l'optimisation prématurée. Dans la plupart des cas, cela n'a pas vraiment d'importance. Heck, avec la vitesse des processeurs de nos jours, vous pourriez probablement trier à bulles la plupart des ensembles de données et ne pas vraiment remarquer beaucoup. Mais lorsque vous triez des ensembles de données très volumineux et que les performances de tri commencent à devenir un problème, vous devez absolument envisager d'autres options.

Bien que cela n'ait évidemment pas d'importance pour les bits et les tranches horaires. Je trouve que le tri par fusion est plus facile à écrire et à comprendre que le tri rapide. Donc, si je vais écrire mon propre algorithme de tri, je l'utiliserais.

Au moins dans une bibliothèque écrite avec compétence, je m'attendrais à ce que le module intégré sortsoit implémenté en tant qu'Introsort plutôt qu'en tant que Quicksort. La différence importe rarement beaucoup, mais Introsort élimine les mauvaises performances les plus défavorables de Quicksort avec un effet minimal sur les cas les plus courants.

Pour répondre à votre question, cependant: oui - c'est ce que vous devriez habituellement commencer par, et jusqu'à / à moins que vous ayez des résultats de profileur indiquant que c'est un problème, c'est là qu'il devrait rester.