[Powered by Google Translate] TOMMY: Jetons un coup d'oeil à tri par sélection, un algorithme pour prendre une liste de numéros et de les trier. Un algorithme, rappelez-vous, c'est simplement une étape-par-étape procédure à suivre pour accomplir une tâche. L'idée de base derrière tri par sélection consiste à diviser notre liste en deux parties - une partie triés et une partie non triés. À chaque étape de l'algorithme, un nombre est déplacé de la partie non triés à la partie triée jusqu'à ce que finalement l' liste complète est triée. Alors, voici une liste de six numéros - 23, 42, 4, 16, 8, et 15. En ce moment la liste entière est considérée comme non triés. Même si un certain nombre comme 16 peut-être déjà dans sa bonne emplacement, notre algorithme n'a aucun moyen de savoir que jusqu'à ce que le liste complète est triée. Donc, nous allons considérer chaque numéro à unsorted jusqu'à ce que nous trions nous-mêmes. Nous savons que nous voulons la liste pour être en ordre croissant. Donc, nous allons vouloir mettre en place la partie de notre liste triée de gauche à droite, le plus petit au plus grand. Pour ce faire, nous aurons besoin de trouver l'élément minimum non triés et le mettre à l'extrémité de la partie triée. Étant donné que cette liste n'est pas triée, la seule façon de le faire est de voir chaque élément dans la partie non triés, se souvenant lequel élément est la plus faible et la comparaison chaque élément à cela. Donc, nous allons d'abord examiner la 23. Ceci est le premier élément que nous avons vu, nous allons donc rappeler il est le minimum. Ensuite, nous allons examiner 42. 42 est supérieure à 23, de manière encore 23 est le minimum. Suivant est la 4 qui est inférieur à 23, donc nous nous souviendrons 4 que le nouveau minimum. Appelle 16 qui est plus grand que 4, de sorte 4 est toujours le minimum. 8 est plus grand que 4, et 15 est plus grand que 4, de sorte 4 doit être le plus petit élément non triés. Ainsi, même si en tant qu'êtres humains, nous pouvons immédiatement voir que 4 est l'élément minimum, notre algorithme doit se pencher sur tous les éléments non triés, même après que nous avons trouvé la 4 - la élément minimal. Alors, maintenant que nous avons trouvé l'élément minimum, 4, nous voulons pour le déplacer dans la partie de la liste triée. Puisque c'est la première étape, cela signifie que nous voulons mettre 4 à le début de la liste. En ce moment 23 est au début de la liste, nous allons échanger le 4 et le 23. Alors maintenant, notre liste ressemble à ceci. Nous savons que 4 doit être à son emplacement définitif, car il est à la fois le plus petit élément de l'élément et au début de la liste. Donc, cela signifie que nous n'avons pas toujours besoin de se déplacer à nouveau. Donc, nous allons répéter cette procédure pour ajouter un autre élément à la partie de la liste triée. Nous savons que nous n'avons pas besoin de regarder le 4, parce que c'est déjà triés. Ainsi, nous pouvons commencer à la 42, qui nous rappelle que le élément minimal. Donc nous allons examiner lors de la 23 qui est inférieur à 42, de sorte que nous rappelle 23 est le nouveau minimum. Ensuite, nous voyons les 16 qui est inférieur à 23, de sorte 16 est le nouveau minimum. Maintenant nous regardons le 8 qui est inférieur à 16, de sorte 8 est le nouveau minimum. Et enfin 8 est inférieur à 15, donc nous savons que 8 est un minimum élément non triés. Cela signifie donc que nous devrions ajouter 8 à la triées partie de la liste. À l'heure actuelle 4 est le seul élément triés, donc nous voulons placer la prochaine 8 de la 4. 42 depuis le premier élément dans la partie non triés de la liste, nous vous voulez échanger les 42 et les 8. Alors maintenant, notre liste ressemble à ceci. 4 et 8 représentent la partie de la liste triée, et l' autres chiffres représentent le non triés partie de la liste. Donc, nous allons continuer avec une autre itération. Nous commençons avec 23 cette fois, puisque nous n'avons pas besoin de regarder le 4 et le 8 plus parce qu'ils ont déjà été triés. 16 est inférieur à 23, donc nous allons rappeler 16 comme le nouveau minimum. 16 est inférieur à 42, mais inférieur à 15 est 16, donc 15 doit être l'élément minimum non triés. Alors maintenant, nous voulons échanger les 15 et les 23 à nous donner cette liste. La partie triée de la liste se compose de 4, 8 et 15, et ces éléments sont encore triées. Mais il se trouve que l'élément suivant non triés, 16, est déjà triée. Cependant, il n'existe aucun moyen pour notre algorithme de savoir que 16 est déjà à son emplacement correct, donc nous avons encore besoin de répéter exactement le même processus. Nous voyons donc que 16 est inférieur à 42, et 16 est inférieure à 23, de sorte 16 doit être l'élément minimum. Il est impossible d'échanger cet élément avec lui-même, afin que nous puissions tout simplement le laisser à cet endroit. Il nous faut donc passer un plus de notre algorithme. 42 est supérieur à 23, donc 23 doit être le minimale élément non triés. Une fois que nous échangeons le 23 et le 42, nous nous retrouvons avec notre finale liste triée - 4, 8, 15, 16, 23, 42. Nous savons que 42 doit être à la bonne place, puisque c'est la seul élément à gauche, et c'est une sorte de sélection. Nous allons maintenant formaliser notre algorithme avec une certaine pseudocode. Sur la première ligne, nous pouvons voir que nous avons besoin d'intégrer plus chaque élément de la liste. Sauf le dernier élément, puisque l'élément 1 liste déjà triée. Sur la deuxième ligne, nous considérons que le premier élément de la non triés partie de la liste pour être le minimum, comme nous l'avons fait avec notre Par exemple, si nous avons quelque chose à comparer. La ligne trois débute une deuxième boucle dans laquelle nous itérer sur chaque élément non triés. Nous savons que, après i itérations, la partie triée de notre liste doivent avoir i éléments qu'il contient, car chaque étape un élément de sortes. Ainsi, le premier élément non triés doivent être en position i + 1. Sur la quatrième ligne, nous comparons l'élément courant au minimum élément que nous avons vu jusqu'à présent. Si l'élément courant est inférieur au minimum élément, puis nous nous souvenons de l'élément courant que le nouveau minimum sur la ligne de cinq ans. Enfin, sur les lignes six et sept, nous échangeons le minimum élément avec le premier élément non triés, ainsi de l'ajouter à la portion de la liste triée. Une fois que nous avons un algorithme, une question importante à poser nous en tant que programmeurs est combien de temps prendrait-il? Nous allons d'abord poser la question combien de temps faut-il pour que cette algorithme à exécuter dans le pire des cas? Rappelons que nous avons représenter cette course temps avec notation grand O. Afin de déterminer l'élément minimum non triés, nous essentiellement dû à comparer chaque élément de la liste pour tous les autres éléments dans la liste. Intuitivement, cela ressemble à un joint de n opérations carré. En regardant notre pseudo-code, nous avons également une boucle imbriquée à l'intérieur une autre boucle, ce qui sonne bien comme un O n de fonctionnement au carré. Cependant, n'oubliez pas que nous n'avons pas besoin de regarder par-dessus l' liste entière lorsqu'il s'agit de déterminer l'élément minimum non triés? Une fois que nous savions que le 4 a été triée par exemple, nous n'avons pas besoin de regarder à nouveau. Il en va de cette baisse de la durée de fonctionnement? Pour notre liste de longueur 6, nous avions besoin de faire cinq les comparaisons pour le premier élément, pour quatre comparaisons le second élément, et ainsi de suite. Cela signifie que le nombre total d'étapes est la somme de les entiers de 1 à la longueur de la liste moins 1. On peut représenter cela avec une sommation. Nous n'entrerons pas dans sommations ici. Mais il s'avère que cette somme est égale à n fois n moins 1 sur 2. Ou de manière équivalente, n au carré de plus de 2 moins n supérieur à 2. Quand on parle d'exécution asymptotique, ce terme n au carré va dominer ce terme n. Donc, tri par sélection est O n carré. Rappelons que dans notre exemple, tri par sélection encore nécessaires pour vérifier si un numéro a déjà été trié doit être déplacé. Cela signifie donc que si nous avons couru tri par sélection sur une déjà liste triée, il faudra le même nombre de pas qu'il serait lors de l'exécution sur une liste complètement non triés. Donc, tri par sélection a un rendement meilleur des cas, de carré n, que nous représentons en oméga n carré. Et c'est tout pour le tri de sélection. Juste un des nombreux algorithmes que nous pouvons utiliser pour trier la liste. Mon nom est Tommy, et c'est CS50.