Algorithme pour nombre entier maximal dans un tableau d'entiers

Question

Si nous avons besoin d'implémenter une fonction qui prend un tableau d'entiers et renvoie l'entier maximum dans la collection, en supposant que la longueur du tableau est inférieure à 1000. Utiliseriez-vous Bubble Trier ou fusionner Trier et pourquoi?

En outre, qu'arrive-t-il au choix de l'algorithme ci-dessus, si la longueur du tableau est supérieure à 1000? Je suis un peu confus sur pourquoi je devrais utiliser un algorithme particulier sur un autre. Est-ce juste à cause de sa complexité et du temps ou d'autres facteurs impliqués dans cela? Que faire si je dois tester la fonction ci-dessus et que cela prend beaucoup plus de temps pour un algorithme simple et moins de temps pour un algorithme complexe?

Answer 1

Je ne voudrais pas trier du tout. Je traverse juste la rangée et garde la plus grande comme je vais. Cela prend le temps O (N), alors que les algorithmes de tri ne feront généralement pas mieux que O (N * log (N)).

Answer 2

Appelons la longueur de votre tableau N.

Tri tableau à l'aide Trier Bubble prend à peu près dans l'ordre des unités N * N de temps. Le tri en utilisant Merge Sort prend dans l'ordre de N * log N unités de temps.

Il suffit de regarder chaque élément un après l'autre et de garder une trace de l'élément le plus grand qui prendra de l'ordre de N unités de temps.

Par conséquent, utilisez la dernière méthode.

Answer 3

Eh bien, si vous devez trier, alors utilisez le tri par fusion car c'est beaucoup plus rapide que le tri à bulles. Pour 1000 éléments et un seul tri vous ne remarquerez probablement pas la différence sur un ordinateur moderne, mais pour plus d'éléments (je pense> 10 000) la différence devient notieceable.

Answer 4

Ce site roches

http://www.sorting-algorithms.com/