Tu vas découvrir les algorithmes de tri et de recherche,...
NSI84 vues·Mis à jour 12 août 2026·4 pagesLes Algorithmes de Tri et leur Complexité Simplifiés
Amélie@amlie_xhrkm
1 / 4
1
of 4
Recherche dichotomique et tri par sélection
La recherche dichotomique est ton meilleur ami quand tu cherches quelque chose dans une liste triée. L'idée ? Tu regardes l'élément du milieu et tu élimines la moitié du tableau à chaque étape.
Le principe est simple : si l'élément du milieu est plus petit que ce que tu cherches, tu regardes à droite. S'il est plus grand, tu regardes à gauche. Tu continues jusqu'à trouver ta valeur ou épuiser les possibilités.
Complexité : O(log₂) - c'est hyper efficace ! Même avec un million d'éléments, tu n'auras besoin que de 20 étapes maximum.
💡 Astuce : La recherche dichotomique ne fonctionne QUE sur des tableaux déjà triés !
Pour le tri par sélection, on prouve sa correction avec un invariant de boucle : à chaque étape, la partie gauche du tableau est triée et contient les plus petites valeurs.
2
of 4
Tri par insertion
Le tri par insertion fonctionne comme quand tu tries des cartes dans ta main. Tu prends chaque élément et tu l'insères à sa place dans la partie déjà triée.
L'algorithme utilise deux fonctions : inserer() qui place un élément à sa position, et tri_insertion() qui applique ce processus à tout le tableau.
Complexité : O(n²) dans le pire cas. Chaque insertion peut nécessiter jusqu'à n comparaisons, et on fait ça n fois au total.
💡 Bon à savoir : Le tri par insertion est très efficace sur de petits tableaux ou des tableaux presque triés !
Le variant de boucle est crucial pour prouver qu'un algorithme se termine. C'est une valeur entière positive qui diminue strictement à chaque passage de boucle.
3
of 4
4
of 4
Si on te demande...
Notre compagnon IA est spécialement conçu pour répondre aux besoins des étudiants. Sur la base des millions d'éléments de contenu que nous avons sur la plateforme, nous pouvons fournir des réponses vraiment significatives et pertinentes aux étudiants. Mais il ne s'agit pas seulement de réponses, le compagnon a encore plus pour but de guider les élèves dans leurs défis d'apprentissage quotidiens, avec des plans d'étude personnalisés, des quiz ou des éléments de contenu dans le chat et une personnalisation à 100% basée sur les compétences et les développements de l'étudiant.
Tu peux télécharger l'application dans Google Play Store et dans l'App Store d'Apple.
Oui, tu as un accès entièrement gratuit à tous les contenus de l'appli, tu peux chatter ou suivre les créateurs à tout moment. De plus, nous proposons Knowunity Premium, qui te permet de réviser sans limites!
Contenus similaires
Contenus les plus populaires en NSI
9NSICommandes SQL Essentielles
Explorez les commandes fondamentales du langage SQL, y compris INSERT, DELETE, UPDATE, et SELECT. Ce résumé couvre également les contraintes de domaine, de relation et de référence, ainsi que les opérations de tri et de jointure. Idéal pour les étudiants préparant le bac en NSI.
Tle5,596234
NSIArbres Binaires Essentiels
Découvrez les concepts clés des arbres binaires, y compris la taille, la profondeur, et les parcours (préfixe, infixe, suffixe). Ce résumé est idéal pour préparer le bac de NSI et comprend des définitions et des exemples pratiques.
Tle3,892149
NSIGraphes et Arbres Binaires
Explorez les concepts fondamentaux des graphes et des arbres binaires, y compris les types de graphes, les matrices et listes d'adjacences, ainsi que les différentes méthodes de parcours d'arbres. Ce document est essentiel pour comprendre les structures de données en NSI.
Tle1,43339
NSIStructures de Données: Liste, Pile, File
Explorez les concepts fondamentaux des structures de données en NSI, y compris les listes, les piles et les files. Apprenez les principes FIFO et LIFO, ainsi que leur implémentation en Python. Ce document présente des schémas explicatifs et des exemples pratiques pour une meilleure compréhension.
Tle2,09864
NSIIntroduction à la POO
Explorez les concepts fondamentaux de la programmation orientée objet (POO), y compris son histoire, la représentation des classes, la conception d'objets, et l'instanciation. Ce résumé est essentiel pour les étudiants en NSI préparant le bac, avec des exemples pratiques de code Python.
Tle3,824127
NSIRéseaux Sociaux et Graphes
Explorez les concepts clés des réseaux sociaux et leur représentation graphique. Ce document couvre l'utilisation de Python pour générer des valeurs aléatoires, les structures de graphes, et les conditions avec des instructions if. Idéal pour comprendre les dynamiques de groupe et les technologies des réseaux sociaux.
2nde56318
SIÉquations RC et Condensateurs
Explorez les concepts clés des dipôles RC, y compris les formules essentielles, le chargement et le déchargement des condensateurs dans une résistance, ainsi que les équations différentielles associées. Ce résumé est idéal pour les étudiants en physique cherchant à maîtriser ces notions fondamentales.
2nde1203
NSISujets Innovants pour le Grand Oral
Explorez une sélection de sujets captivants pour le Grand Oral en NSI, incluant des thèmes sur l'intelligence artificielle, la bio-informatique, et les crypto-monnaies. Idéal pour stimuler la réflexion et préparer des présentations percutantes. Type : Proposition de sujets.
Tle3,393101
NSIStructures Linéaires: Piles et Files
Explorez les concepts fondamentaux des structures linéaires, y compris les listes, les piles et les files. Ce résumé couvre les constructeurs, accesseurs et opérations essentielles pour manipuler ces structures de données. Idéal pour les étudiants en programmation et en informatique.
Tle1744
Contenus les plus populaires
9D
HistoireDéfaite de 1940 et Régime de Vichy
Comprendre l'armistice de juin 1940, la fin de la IIIe République et la mise en place du nouveau régime autoritaire de Philippe Pétain.
3e3,8210
I
HistoireIntroduction à la Seconde Guerre mondiale
Identifiez les causes du conflit, les alliances et les dates clés du déclenchement de la guerre en Europe et dans le Pacifique.
3e6,3050
C
HistoireCollaboration sous l'Occupation Allemande
Analyser les différentes formes de collaboration de l'État français, l'exclusion des Juifs et les rafles durant la Seconde Guerre mondiale.
3e2,5860
PhilosophieConscience en Philosophie
Explorez la notion de conscience en philosophie à travers ses implications sur la justice, la liberté, et la connaissance. Cette fiche de révision aborde les débats philosophiques sur la conscience, le cogito, et les valeurs morales, tout en intégrant des perspectives contemporaines. Idéale pour les étudiants en philosophie cherchant à approfondir leur compréhension des enjeux éthiques et existentiels.
Tle107,3685,431
A
FrançaisAnalyse des figures de style en contexte
Repérer les figures de style dans des extraits littéraires et analyser l'effet produit sur le lecteur.
3e3,0370
I
FrançaisIdentification des figures de style courantes
Apprenez à reconnaître les métaphores, comparaisons, personnifications et allégories dans des phrases simples.
2nde1,5060
C
HistoireCrises majeures de la Guerre froide
Analyser les moments de tension extrême tels que le blocus de Berlin et la crise des missiles de Cuba.
3e1,9390
Q
HistoireQuiz entre-deux-guerres 3e
Quiz histoire entre-deux-guerres 3e
3e7,73057
L
HistoireLa Résistance Française de 1940 à 1944
Étudier l'appel du 18 juin, la formation des mouvements de résistance intérieure et le rôle de Jean Moulin dans leur unification.
3e1,3610
Les étudiants nous adorent — il ne manque plus que toi.
4.6/5App Store
4.7/5Google Play
L'application est très facile d'utilisation et bien conçue. Jusqu'à présent, j'ai trouvé tout ce que je cherchais et j'ai pu apprendre beaucoup de choses grâce aux présentations ! Je vais certainement utiliser l'application pour un travail en classe ! Et comme source d'inspiration personnelle, elle est bien sûr aussi très utile.
Stefan Sutilisateur iOS
Cette application est vraiment super. Il y a tellement de fiches de révision et d'aide, [...]. Par exemple, la matière qui me pose problème est le français et l'appli a un choix d'aide très large. Grâce à cette application, je me suis améliorée en français. Je la recommanderais à tout le monde.
Samantha Klichutilisatrice Android
Waouh, je suis vraiment abasourdi. J'ai essayé l'application parce que je l'avais déjà vue plusieurs fois dans la publicité et j'ai été absolument choquée. Cette appli est L'AIDE dont on rêve pour l'école et surtout, elle propose tellement de choses, comme des rédactions et des fiches qui m'ont personnellement TRÈS bien aidé.
Annautilisatrice iOS
NSI84 vues·Mis à jour 12 août 2026·4 pagesLes Algorithmes de Tri et leur Complexité Simplifiés
Amélie@amlie_xhrkm
Tu vas découvrir les algorithmes de tri et de recherche, des outils super utiles en programmation ! On va voir comment la recherche dichotomique permet de trouver un élément rapidement, et comment prouver mathématiquement que nos algorithmes fonctionnent correctement.
1
of 4
Inscris-toi pour voir le contenu. C'est gratuit!
- Accès à tous les documents
- Améliore tes notes
- Rejoins des millions d'étudiants
En t'inscrivant, tu acceptes les Conditions d'utilisation et la Politique de confidentialité.
Recherche dichotomique et tri par sélection
La recherche dichotomique est ton meilleur ami quand tu cherches quelque chose dans une liste triée. L'idée ? Tu regardes l'élément du milieu et tu élimines la moitié du tableau à chaque étape.
Le principe est simple : si l'élément du milieu est plus petit que ce que tu cherches, tu regardes à droite. S'il est plus grand, tu regardes à gauche. Tu continues jusqu'à trouver ta valeur ou épuiser les possibilités.
Complexité : O(log₂) - c'est hyper efficace ! Même avec un million d'éléments, tu n'auras besoin que de 20 étapes maximum.
💡 Astuce : La recherche dichotomique ne fonctionne QUE sur des tableaux déjà triés !
Pour le tri par sélection, on prouve sa correction avec un invariant de boucle : à chaque étape, la partie gauche du tableau est triée et contient les plus petites valeurs.
2
of 4Inscris-toi pour voir le contenu. C'est gratuit!
- Accès à tous les documents
- Améliore tes notes
- Rejoins des millions d'étudiants
En t'inscrivant, tu acceptes les Conditions d'utilisation et la Politique de confidentialité.
Tri par insertion
Le tri par insertion fonctionne comme quand tu tries des cartes dans ta main. Tu prends chaque élément et tu l'insères à sa place dans la partie déjà triée.
L'algorithme utilise deux fonctions : inserer() qui place un élément à sa position, et tri_insertion() qui applique ce processus à tout le tableau.
Complexité : O(n²) dans le pire cas. Chaque insertion peut nécessiter jusqu'à n comparaisons, et on fait ça n fois au total.
💡 Bon à savoir : Le tri par insertion est très efficace sur de petits tableaux ou des tableaux presque triés !
Le variant de boucle est crucial pour prouver qu'un algorithme se termine. C'est une valeur entière positive qui diminue strictement à chaque passage de boucle.
3
of 4Inscris-toi pour voir le contenu. C'est gratuit!
- Accès à tous les documents
- Améliore tes notes
- Rejoins des millions d'étudiants
En t'inscrivant, tu acceptes les Conditions d'utilisation et la Politique de confidentialité.
4
of 4Inscris-toi pour voir le contenu. C'est gratuit!
- Accès à tous les documents
- Améliore tes notes
- Rejoins des millions d'étudiants
En t'inscrivant, tu acceptes les Conditions d'utilisation et la Politique de confidentialité.
Si on te demande...
Notre compagnon IA est spécialement conçu pour répondre aux besoins des étudiants. Sur la base des millions d'éléments de contenu que nous avons sur la plateforme, nous pouvons fournir des réponses vraiment significatives et pertinentes aux étudiants. Mais il ne s'agit pas seulement de réponses, le compagnon a encore plus pour but de guider les élèves dans leurs défis d'apprentissage quotidiens, avec des plans d'étude personnalisés, des quiz ou des éléments de contenu dans le chat et une personnalisation à 100% basée sur les compétences et les développements de l'étudiant.
Tu peux télécharger l'application dans Google Play Store et dans l'App Store d'Apple.
Oui, tu as un accès entièrement gratuit à tous les contenus de l'appli, tu peux chatter ou suivre les créateurs à tout moment. De plus, nous proposons Knowunity Premium, qui te permet de réviser sans limites!
Contenus similaires
Contenus les plus populaires en NSI
9NSICommandes SQL Essentielles
Explorez les commandes fondamentales du langage SQL, y compris INSERT, DELETE, UPDATE, et SELECT. Ce résumé couvre également les contraintes de domaine, de relation et de référence, ainsi que les opérations de tri et de jointure. Idéal pour les étudiants préparant le bac en NSI.
Tle5,596234
NSIArbres Binaires Essentiels
Découvrez les concepts clés des arbres binaires, y compris la taille, la profondeur, et les parcours (préfixe, infixe, suffixe). Ce résumé est idéal pour préparer le bac de NSI et comprend des définitions et des exemples pratiques.
Tle3,892149
NSIGraphes et Arbres Binaires
Explorez les concepts fondamentaux des graphes et des arbres binaires, y compris les types de graphes, les matrices et listes d'adjacences, ainsi que les différentes méthodes de parcours d'arbres. Ce document est essentiel pour comprendre les structures de données en NSI.
Tle1,43339
NSIStructures de Données: Liste, Pile, File
Explorez les concepts fondamentaux des structures de données en NSI, y compris les listes, les piles et les files. Apprenez les principes FIFO et LIFO, ainsi que leur implémentation en Python. Ce document présente des schémas explicatifs et des exemples pratiques pour une meilleure compréhension.
Tle2,09864
NSIIntroduction à la POO
Explorez les concepts fondamentaux de la programmation orientée objet (POO), y compris son histoire, la représentation des classes, la conception d'objets, et l'instanciation. Ce résumé est essentiel pour les étudiants en NSI préparant le bac, avec des exemples pratiques de code Python.
Tle3,824127
NSIRéseaux Sociaux et Graphes
Explorez les concepts clés des réseaux sociaux et leur représentation graphique. Ce document couvre l'utilisation de Python pour générer des valeurs aléatoires, les structures de graphes, et les conditions avec des instructions if. Idéal pour comprendre les dynamiques de groupe et les technologies des réseaux sociaux.
2nde56318
SIÉquations RC et Condensateurs
Explorez les concepts clés des dipôles RC, y compris les formules essentielles, le chargement et le déchargement des condensateurs dans une résistance, ainsi que les équations différentielles associées. Ce résumé est idéal pour les étudiants en physique cherchant à maîtriser ces notions fondamentales.
2nde1203
NSISujets Innovants pour le Grand Oral
Explorez une sélection de sujets captivants pour le Grand Oral en NSI, incluant des thèmes sur l'intelligence artificielle, la bio-informatique, et les crypto-monnaies. Idéal pour stimuler la réflexion et préparer des présentations percutantes. Type : Proposition de sujets.
Tle3,393101
NSIStructures Linéaires: Piles et Files
Explorez les concepts fondamentaux des structures linéaires, y compris les listes, les piles et les files. Ce résumé couvre les constructeurs, accesseurs et opérations essentielles pour manipuler ces structures de données. Idéal pour les étudiants en programmation et en informatique.
Tle1744
Contenus les plus populaires
9D
HistoireDéfaite de 1940 et Régime de Vichy
Comprendre l'armistice de juin 1940, la fin de la IIIe République et la mise en place du nouveau régime autoritaire de Philippe Pétain.
3e3,8210
I
HistoireIntroduction à la Seconde Guerre mondiale
Identifiez les causes du conflit, les alliances et les dates clés du déclenchement de la guerre en Europe et dans le Pacifique.
3e6,3050
C
HistoireCollaboration sous l'Occupation Allemande
Analyser les différentes formes de collaboration de l'État français, l'exclusion des Juifs et les rafles durant la Seconde Guerre mondiale.
3e2,5860
PhilosophieConscience en Philosophie
Explorez la notion de conscience en philosophie à travers ses implications sur la justice, la liberté, et la connaissance. Cette fiche de révision aborde les débats philosophiques sur la conscience, le cogito, et les valeurs morales, tout en intégrant des perspectives contemporaines. Idéale pour les étudiants en philosophie cherchant à approfondir leur compréhension des enjeux éthiques et existentiels.
Tle107,3685,431
A
FrançaisAnalyse des figures de style en contexte
Repérer les figures de style dans des extraits littéraires et analyser l'effet produit sur le lecteur.
3e3,0370
I
FrançaisIdentification des figures de style courantes
Apprenez à reconnaître les métaphores, comparaisons, personnifications et allégories dans des phrases simples.
2nde1,5060
C
HistoireCrises majeures de la Guerre froide
Analyser les moments de tension extrême tels que le blocus de Berlin et la crise des missiles de Cuba.
3e1,9390
Q
HistoireQuiz entre-deux-guerres 3e
Quiz histoire entre-deux-guerres 3e
3e7,73057
L
HistoireLa Résistance Française de 1940 à 1944
Étudier l'appel du 18 juin, la formation des mouvements de résistance intérieure et le rôle de Jean Moulin dans leur unification.
3e1,3610
Les étudiants nous adorent — il ne manque plus que toi.
4.6/5App Store
4.7/5Google Play
L'application est très facile d'utilisation et bien conçue. Jusqu'à présent, j'ai trouvé tout ce que je cherchais et j'ai pu apprendre beaucoup de choses grâce aux présentations ! Je vais certainement utiliser l'application pour un travail en classe ! Et comme source d'inspiration personnelle, elle est bien sûr aussi très utile.
Stefan Sutilisateur iOS
Cette application est vraiment super. Il y a tellement de fiches de révision et d'aide, [...]. Par exemple, la matière qui me pose problème est le français et l'appli a un choix d'aide très large. Grâce à cette application, je me suis améliorée en français. Je la recommanderais à tout le monde.
Samantha Klichutilisatrice Android
Waouh, je suis vraiment abasourdi. J'ai essayé l'application parce que je l'avais déjà vue plusieurs fois dans la publicité et j'ai été absolument choquée. Cette appli est L'AIDE dont on rêve pour l'école et surtout, elle propose tellement de choses, comme des rédactions et des fiches qui m'ont personnellement TRÈS bien aidé.
Annautilisatrice iOS