Tris
Re: algorithmes de tri ?
Peut-être en demandant à ton prof d'informatique directement.
Faut oser parfois dans la vie.
Faut oser parfois dans la vie.
« Occupez-vous d’abord des choses qui sont à portée de main. Rangez votre chambre avant de sauver le monde. Ensuite, sauvez le monde. » (Ron Padgett, dans Comment devenir parfait)
Re: Tris
En général tu utilises le tri de la bibliothèque python pour trier... Si tu veux vraiment comprendre comment les tris marchent (ça peut aider parfois), tu peux toujours essayer d'implémenter les différents algorithmes de tris.
Voici une liste non exhaustive de tris :
Algorithmes quadratiques:
- Tri à Bulle
- Insertion sort
Tris de complexité linearithmique ( O(n log n)):
- Merge sort
- Quicksort
Tris "linéaires":
- Counting sort
-LSD/MSD radix sort
Attention, les deux derniers tris ne sont pas plus efficaces que le quicksort et mergesort. Dans le meilleur cas, ils sont plus efficaces mais dans le cas moyen, ils le sont moins. Le tris utilisé dans la std C et C++ est le quicksort, j'imagine que c'est pareil en python.
Tu peux aussi t'amuser à implémenter des arbres binaires de recherche qui sont souvent utilisé pour conserver une structure de donnée trié avec accès, insertion et suppression en O(log n) (pour des arbres équilibrés, si il ne l'est pas, ça peut passer en O(n) dans le pire cas : arbre linéaire).
EDIT: Je ne connais pas encore le programme de prépa donc je ne sais pas si tu as des notions de complexité mais globalement, j'ai classé les algorithmes par ordre croissant d'efficacité: Les algorithmes quadratiques sont bien pour des petits tableau mais au-delà de l'ordre de 10,000 éléments, ça devient plus compliquer. Pour les 2 autres classes, tu peux trier plusieurs millions d'entiers en moins d'une seconde sans soucis.
Voici une liste non exhaustive de tris :
Algorithmes quadratiques:
- Tri à Bulle
- Insertion sort
Tris de complexité linearithmique ( O(n log n)):
- Merge sort
- Quicksort
Tris "linéaires":
- Counting sort
-LSD/MSD radix sort
Attention, les deux derniers tris ne sont pas plus efficaces que le quicksort et mergesort. Dans le meilleur cas, ils sont plus efficaces mais dans le cas moyen, ils le sont moins. Le tris utilisé dans la std C et C++ est le quicksort, j'imagine que c'est pareil en python.
Tu peux aussi t'amuser à implémenter des arbres binaires de recherche qui sont souvent utilisé pour conserver une structure de donnée trié avec accès, insertion et suppression en O(log n) (pour des arbres équilibrés, si il ne l'est pas, ça peut passer en O(n) dans le pire cas : arbre linéaire).
EDIT: Je ne connais pas encore le programme de prépa donc je ne sais pas si tu as des notions de complexité mais globalement, j'ai classé les algorithmes par ordre croissant d'efficacité: Les algorithmes quadratiques sont bien pour des petits tableau mais au-delà de l'ordre de 10,000 éléments, ça devient plus compliquer. Pour les 2 autres classes, tu peux trier plusieurs millions d'entiers en moins d'une seconde sans soucis.
Lycée Édouard Branly 2015-2018
LLG HX1 2018-2019
LLG MP*3 2019-2020
Ulm 2020-?
LLG HX1 2018-2019
LLG MP*3 2019-2020
Ulm 2020-?
Re: Tris
Niveaux 3 et 5 sur france-ioi
http://www.france-ioi.org/algo/chapters.php
http://www.france-ioi.org/algo/chapters.php
Re: Tris
Non: Quicksort est en O(nlog(n)) en moyenne, mais seulement O(n^2) dans le pire cas.
Si: ils sont effectivement linéaires, mais demandent des conditions supplémentaires sur les éléments à trier (des entiers bornés pour Counting sort)
Professeur d'informatique en CPGE
http://quentinfortier.fr/
http://quentinfortier.fr/
Re: Tris
Merci pour les indications par rapport aux deux derniers tris, je ne savais pas ! Ce qui explique pourquoi la std C utilise le quicksort pour trier et non un algorithme linéaire.
Lycée Édouard Branly 2015-2018
LLG HX1 2018-2019
LLG MP*3 2019-2020
Ulm 2020-?
LLG HX1 2018-2019
LLG MP*3 2019-2020
Ulm 2020-?
Re: Tris
Non: Quicksort est en O(nlog(n)) en moyenne, mais seulement O(n^2) dans le pire cas.
Pas "non". Il faut justement dire de quoi on parle.Est ce une complexité moyenne? Pire cas? En temps? En espace?
La complexité moyenne (on voit parfois "amortie" mais là encore il faut lire les petites lignes... ) est parfois complexe à calculer car il faut déjà avoir la répartition des cas.
Le pire cas c'est intéressant dans l'embarqué par exemple ou en temps réel si on veut être certain que l'algo se termine en N millisecondes. On peut aussi parfois s'arranger pour que LE pire cas (car parfois il est unique) n'arrive jamais.
Pas "non". Il faut justement dire de quoi on parle.Est ce une complexité moyenne? Pire cas? En temps? En espace?
La complexité moyenne (on voit parfois "amortie" mais là encore il faut lire les petites lignes... ) est parfois complexe à calculer car il faut déjà avoir la répartition des cas.
Le pire cas c'est intéressant dans l'embarqué par exemple ou en temps réel si on veut être certain que l'algo se termine en N millisecondes. On peut aussi parfois s'arranger pour que LE pire cas (car parfois il est unique) n'arrive jamais.
Pas prof.
Prépa, école, M2, thèse (optique/images) ->ingé dans le privé.
Prépa, école, M2, thèse (optique/images) ->ingé dans le privé.