Tris

Messages : 0

Inscription : 17 nov. 2017 21:04

Profil de l'utilisateur : Élève de lycée

Tris

Message par Boushaba » 27 nov. 2017 16:34

Bonjour, Est ce que vous pouvez me donner des exercices d'entraînement des tris en général pour les tableaux en langage python?

Messages : 2426

Inscription : 27 juil. 2016 19:38

Profil de l'utilisateur : Élève de lycée

Re: algorithmes de tri ?

Message par U46406 » 27 nov. 2017 16:44

Peut-être en demandant à ton prof d'informatique directement.

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) :mrgreen:

Messages : 0

Inscription : 04 oct. 2017 15:58

Profil de l'utilisateur : Élève de lycée

Re: Tris

Message par Errys » 27 nov. 2017 18:43

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.
Lycée Édouard Branly 2015-2018
LLG HX1 2018-2019
LLG MP*3 2019-2020
Ulm 2020-?

Messages : 0

Inscription : 18 juin 2017 13:21

Profil de l'utilisateur : Élève de lycée

Re: Tris

Message par Lohengrin » 28 nov. 2017 19:45

Niveaux 3 et 5 sur france-ioi
http://www.france-ioi.org/algo/chapters.php

Messages : 0

Inscription : 27 juil. 2017 13:37

Profil de l'utilisateur : Élève de lycée

Re: Tris

Message par Quentin Fortier » 28 nov. 2017 21:07

Errys a écrit :
27 nov. 2017 18:43

Tris de complexité linearithmique ( O(n log n)):
- Quicksort
Non: Quicksort est en O(nlog(n)) en moyenne, mais seulement O(n^2) dans le pire cas.
Errys a écrit :
27 nov. 2017 18:43
Tris "linéaires":
- Counting sort
-LSD/MSD radix sort

Attention, les deux derniers tris ne sont pas plus efficaces que le quicksort et mergesort.
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/

Messages : 0

Inscription : 04 oct. 2017 15:58

Profil de l'utilisateur : Élève de lycée

Re: Tris

Message par Errys » 28 nov. 2017 21:46

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-?

Messages : 0

Inscription : 17 nov. 2017 21:04

Profil de l'utilisateur : Élève de lycée

Re: Tris

Message par Boushaba » 03 déc. 2017 00:09

Merci pour les informations :)

Messages : 0

Inscription : 17 nov. 2017 21:04

Profil de l'utilisateur : Élève de lycée

Re: Tris

Message par Boushaba » 03 déc. 2017 00:09

C'est gentil de votre part !

Messages : 9679

Inscription : 30 juil. 2008 16:59

Profil de l'utilisateur : Élève de lycée

Re: Tris

Message par fakbill » 03 déc. 2017 16:28

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 prof.
Prépa, école, M2, thèse (optique/images) ->ingé dans le privé.

Répondre