Tris

Modérateur : Michel Quercia

Répondre
Boushaba
Messages : 24
Enregistré le : ven. nov. 17, 2017 10:04 pm
Classe : MPSI

Tris

Message par Boushaba » lun. nov. 27, 2017 5:34 pm

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?

Avatar du membre
U46406
Messages : 7242
Enregistré le : mer. juil. 27, 2016 7:38 pm
Classe : shadow CCO nobo CMT
Contact :

Re: algorithmes de tri ?

Message par U46406 » lun. nov. 27, 2017 5:44 pm

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:

Errys
Messages : 257
Enregistré le : mer. oct. 04, 2017 3:58 pm
Classe : MPSI

Re: Tris

Message par Errys » lun. nov. 27, 2017 7:43 pm

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

Lohengrin
Messages : 114
Enregistré le : dim. juin 18, 2017 1:21 pm
Classe : ETH (CS)

Re: Tris

Message par Lohengrin » mar. nov. 28, 2017 8:45 pm

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

Quentin Fortier
Messages : 10
Enregistré le : jeu. juil. 27, 2017 1:37 pm
Contact :

Re: Tris

Message par Quentin Fortier » mar. nov. 28, 2017 10:07 pm

Errys a écrit :
lun. nov. 27, 2017 7:43 pm

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 :
lun. nov. 27, 2017 7:43 pm
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/

Errys
Messages : 257
Enregistré le : mer. oct. 04, 2017 3:58 pm
Classe : MPSI

Re: Tris

Message par Errys » mar. nov. 28, 2017 10:46 pm

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

Boushaba
Messages : 24
Enregistré le : ven. nov. 17, 2017 10:04 pm
Classe : MPSI

Re: Tris

Message par Boushaba » dim. déc. 03, 2017 1:09 am

Merci pour les informations :)

Boushaba
Messages : 24
Enregistré le : ven. nov. 17, 2017 10:04 pm
Classe : MPSI

Re: Tris

Message par Boushaba » dim. déc. 03, 2017 1:09 am

C'est gentil de votre part !

Avatar du membre
fakbill
Messages : 11149
Enregistré le : mer. juil. 30, 2008 4:59 pm
Classe : Dr.-Ing

Re: Tris

Message par fakbill » dim. déc. 03, 2017 5:28 pm

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

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 1 invité