Est une sorte de sélection d'un algorithme efficace?

Question

Je sais qu'il est un algorithme quadratique, mais comment il compare à d'autres algorithmes de tri, tels que Tri rapide ou Tri Bubble?

Answer 1

tri des algorithmes varient généralement en fonction de la nature des données que vous avez.

Cependant, alors que sort sort de la bulle et la sélection sont faciles à comprendre (et mettre en œuvre) des algorithmes de tri leur temps d'exécution est O (n ^ 2) i.e. le pire moment que vous pouvez éventuellement obtenir.

En ce qui concerne tri rapide sur un avergage il faut O (n log n) d'où il est un excellent genre. Cependant, il peut aussi prendre O (n ^ 2) dans certains cas.

Answer 2

algorithmes de temps quadratiques, selon la taille de votre ensemble de données, peuvent être incroyablement plus lent.

n = 10e78 (sur le nombre d'atomes dans l'univers)

Pour un algorithme quadratique, qui est n * (10e78). Pour un nlog (n) algorithme, comme quicksort ou mergesort, qui est n * 262. C'est une énorme différence.

Mais si votre ensemble de données est relativement faible (<1000 articles, par exemple), la différence de performance est sans doute pas à être perceptible (à moins, peut-être, le genre est fait à plusieurs reprises). Dans ces cas, il est généralement préférable d'utiliser l'algorithme le plus simple, et d'optimiser plus tard si elle se révèle être trop lent.

« L'optimisation prématurée est la racine de tout le mal. » SiR Tony Hoare, popularisé par Donald Knuth

Answer 3

Wikipédia connaît tous.

La sélection sorte assez suce beaucoup.

Answer 4

Si les données que vous avez ne comprend que des nombres entiers positifs que vous pouvez regarder à Bucket Trier. L'algorithme peut avoir un temps de fonctionnement linéaire O (n) dans les bonnes conditions.