1 00:00:06,762 --> 00:00:09,980 [Powered by Google Translate] TOMMY: Jetons un coup d'oeil à tri par sélection, un algorithme 2 00:00:09,980 --> 00:00:12,800 pour prendre une liste de numéros et de les trier. 3 00:00:12,800 --> 00:00:15,750 Un algorithme, rappelez-vous, c'est simplement une étape-par-étape 4 00:00:15,750 --> 00:00:18,370 procédure à suivre pour accomplir une tâche. 5 00:00:18,370 --> 00:00:21,470 L'idée de base derrière tri par sélection consiste à diviser 6 00:00:21,470 --> 00:00:23,390 notre liste en deux parties - 7 00:00:23,390 --> 00:00:26,810 une partie triés et une partie non triés. 8 00:00:26,810 --> 00:00:30,200 À chaque étape de l'algorithme, un nombre est déplacé de la 9 00:00:30,200 --> 00:00:33,800 partie non triés à la partie triée jusqu'à ce que finalement l' 10 00:00:33,800 --> 00:00:35,880 liste complète est triée. 11 00:00:35,880 --> 00:00:38,510 Alors, voici une liste de six numéros - 12 00:00:38,510 --> 00:00:44,010 23, 42, 4, 16, 8, et 15. 13 00:00:44,010 --> 00:00:47,680 En ce moment la liste entière est considérée comme non triés. 14 00:00:47,680 --> 00:00:51,770 Même si un certain nombre comme 16 peut-être déjà dans sa bonne 15 00:00:51,770 --> 00:00:56,040 emplacement, notre algorithme n'a aucun moyen de savoir que jusqu'à ce que le 16 00:00:56,040 --> 00:00:57,980 liste complète est triée. 17 00:00:57,980 --> 00:01:01,355 Donc, nous allons considérer chaque numéro à unsorted jusqu'à ce que nous trions 18 00:01:01,355 --> 00:01:03,800 nous-mêmes. 19 00:01:03,800 --> 00:01:06,890 Nous savons que nous voulons la liste pour être en ordre croissant. 20 00:01:06,890 --> 00:01:10,200 Donc, nous allons vouloir mettre en place la partie de notre liste triée 21 00:01:10,200 --> 00:01:13,280 de gauche à droite, le plus petit au plus grand. 22 00:01:13,280 --> 00:01:17,970 Pour ce faire, nous aurons besoin de trouver l'élément minimum non triés 23 00:01:17,970 --> 00:01:21,350 et le mettre à l'extrémité de la partie triée. 24 00:01:21,350 --> 00:01:25,370 Étant donné que cette liste n'est pas triée, la seule façon de le faire est de 25 00:01:25,370 --> 00:01:29,330 voir chaque élément dans la partie non triés, se souvenant 26 00:01:29,330 --> 00:01:32,010 lequel élément est la plus faible et la comparaison 27 00:01:32,010 --> 00:01:33,770 chaque élément à cela. 28 00:01:33,770 --> 00:01:36,150 Donc, nous allons d'abord examiner la 23. 29 00:01:36,150 --> 00:01:38,650 Ceci est le premier élément que nous avons vu, nous allons donc rappeler 30 00:01:38,650 --> 00:01:40,050 il est le minimum. 31 00:01:40,050 --> 00:01:42,320 Ensuite, nous allons examiner 42. 32 00:01:42,320 --> 00:01:46,720 42 est supérieure à 23, de manière encore 23 est le minimum. 33 00:01:46,720 --> 00:01:51,210 Suivant est la 4 qui est inférieur à 23, donc nous nous souviendrons 4 34 00:01:51,210 --> 00:01:52,880 que le nouveau minimum. 35 00:01:52,880 --> 00:01:56,380 Appelle 16 qui est plus grand que 4, de sorte 4 36 00:01:56,380 --> 00:01:57,980 est toujours le minimum. 37 00:01:57,980 --> 00:02:03,670 8 est plus grand que 4, et 15 est plus grand que 4, de sorte 4 doit être 38 00:02:03,670 --> 00:02:05,980 le plus petit élément non triés. 39 00:02:05,980 --> 00:02:09,350 Ainsi, même si en tant qu'êtres humains, nous pouvons immédiatement voir que 4 est 40 00:02:09,350 --> 00:02:12,300 l'élément minimum, notre algorithme doit se pencher sur 41 00:02:12,300 --> 00:02:15,710 tous les éléments non triés, même après que nous avons trouvé la 4 - la 42 00:02:15,710 --> 00:02:16,860 élément minimal. 43 00:02:16,860 --> 00:02:19,900 Alors, maintenant que nous avons trouvé l'élément minimum, 4, nous voulons 44 00:02:19,900 --> 00:02:23,410 pour le déplacer dans la partie de la liste triée. 45 00:02:23,410 --> 00:02:27,320 Puisque c'est la première étape, cela signifie que nous voulons mettre 4 à 46 00:02:27,320 --> 00:02:29,680 le début de la liste. 47 00:02:29,680 --> 00:02:33,040 En ce moment 23 est au début de la liste, 48 00:02:33,040 --> 00:02:36,080 nous allons échanger le 4 et le 23. 49 00:02:36,080 --> 00:02:38,870 Alors maintenant, notre liste ressemble à ceci. 50 00:02:38,870 --> 00:02:42,710 Nous savons que 4 doit être à son emplacement définitif, car il est 51 00:02:42,710 --> 00:02:45,890 à la fois le plus petit élément de l'élément et au début 52 00:02:45,890 --> 00:02:46,960 de la liste. 53 00:02:46,960 --> 00:02:50,650 Donc, cela signifie que nous n'avons pas toujours besoin de se déplacer à nouveau. 54 00:02:50,650 --> 00:02:53,910 Donc, nous allons répéter cette procédure pour ajouter un autre élément à la 55 00:02:53,910 --> 00:02:55,910 partie de la liste triée. 56 00:02:55,910 --> 00:02:58,950 Nous savons que nous n'avons pas besoin de regarder le 4, parce que c'est 57 00:02:58,950 --> 00:03:00,000 déjà triés. 58 00:03:00,000 --> 00:03:03,540 Ainsi, nous pouvons commencer à la 42, qui nous rappelle que le 59 00:03:03,540 --> 00:03:05,290 élément minimal. 60 00:03:05,290 --> 00:03:08,700 Donc nous allons examiner lors de la 23 qui est inférieur à 42, de sorte que nous 61 00:03:08,700 --> 00:03:11,620 rappelle 23 est le nouveau minimum. 62 00:03:11,620 --> 00:03:14,870 Ensuite, nous voyons les 16 qui est inférieur à 23, de sorte 63 00:03:14,870 --> 00:03:16,800 16 est le nouveau minimum. 64 00:03:16,800 --> 00:03:19,720 Maintenant nous regardons le 8 qui est inférieur à 16, de sorte 65 00:03:19,720 --> 00:03:21,130 8 est le nouveau minimum. 66 00:03:21,130 --> 00:03:25,900 Et enfin 8 est inférieur à 15, donc nous savons que 8 est un minimum 67 00:03:25,900 --> 00:03:27,780 élément non triés. 68 00:03:27,780 --> 00:03:30,660 Cela signifie donc que nous devrions ajouter 8 à la triées 69 00:03:30,660 --> 00:03:32,450 partie de la liste. 70 00:03:32,450 --> 00:03:35,990 À l'heure actuelle 4 est le seul élément triés, donc nous voulons placer 71 00:03:35,990 --> 00:03:38,410 la prochaine 8 de la 4. 72 00:03:38,410 --> 00:03:41,920 42 depuis le premier élément dans la partie non triés de la 73 00:03:41,920 --> 00:03:47,260 liste, nous vous voulez échanger les 42 et les 8. 74 00:03:47,260 --> 00:03:49,680 Alors maintenant, notre liste ressemble à ceci. 75 00:03:49,680 --> 00:03:53,830 4 et 8 représentent la partie de la liste triée, et l' 76 00:03:53,830 --> 00:03:56,440 autres chiffres représentent le non triés 77 00:03:56,440 --> 00:03:58,260 partie de la liste. 78 00:03:58,260 --> 00:04:00,630 Donc, nous allons continuer avec une autre itération. 79 00:04:00,630 --> 00:04:03,850 Nous commençons avec 23 cette fois, puisque nous n'avons pas besoin de regarder 80 00:04:03,850 --> 00:04:05,770 le 4 et le 8 plus parce qu'ils ont 81 00:04:05,770 --> 00:04:07,660 déjà été triés. 82 00:04:07,660 --> 00:04:10,270 16 est inférieur à 23, donc nous allons rappeler 83 00:04:10,270 --> 00:04:12,070 16 comme le nouveau minimum. 84 00:04:12,070 --> 00:04:18,149 16 est inférieur à 42, mais inférieur à 15 est 16, donc 15 doit être 85 00:04:18,149 --> 00:04:20,480 l'élément minimum non triés. 86 00:04:20,480 --> 00:04:24,580 Alors maintenant, nous voulons échanger les 15 et les 23 à 87 00:04:24,580 --> 00:04:26,310 nous donner cette liste. 88 00:04:26,310 --> 00:04:30,500 La partie triée de la liste se compose de 4, 8 et 15, et 89 00:04:30,500 --> 00:04:33,210 ces éléments sont encore triées. 90 00:04:33,210 --> 00:04:36,900 Mais il se trouve que l'élément suivant non triés, 16, 91 00:04:36,900 --> 00:04:38,480 est déjà triée. 92 00:04:38,480 --> 00:04:42,060 Cependant, il n'existe aucun moyen pour notre algorithme de savoir que 16 93 00:04:42,060 --> 00:04:45,230 est déjà à son emplacement correct, donc nous avons encore besoin de 94 00:04:45,230 --> 00:04:47,870 répéter exactement le même processus. 95 00:04:47,870 --> 00:04:53,750 Nous voyons donc que 16 est inférieur à 42, et 16 est inférieure à 23, de sorte 96 00:04:53,750 --> 00:04:56,230 16 doit être l'élément minimum. 97 00:04:56,230 --> 00:04:59,010 Il est impossible d'échanger cet élément avec lui-même, afin que nous puissions 98 00:04:59,010 --> 00:05:01,780 tout simplement le laisser à cet endroit. 99 00:05:01,780 --> 00:05:04,660 Il nous faut donc passer un plus de notre algorithme. 100 00:05:04,660 --> 00:05:09,370 42 est supérieur à 23, donc 23 doit être le 101 00:05:09,370 --> 00:05:10,970 minimale élément non triés. 102 00:05:10,970 --> 00:05:17,410 Une fois que nous échangeons le 23 et le 42, nous nous retrouvons avec notre finale 103 00:05:17,410 --> 00:05:18,530 liste triée - 104 00:05:18,530 --> 00:05:23,390 4, 8, 15, 16, 23, 42. 105 00:05:23,390 --> 00:05:26,830 Nous savons que 42 doit être à la bonne place, puisque c'est la 106 00:05:26,830 --> 00:05:30,210 seul élément à gauche, et c'est une sorte de sélection. 107 00:05:30,210 --> 00:05:32,100 Nous allons maintenant formaliser notre algorithme avec une certaine 108 00:05:32,100 --> 00:05:34,540 pseudocode. 109 00:05:34,540 --> 00:05:37,760 Sur la première ligne, nous pouvons voir que nous avons besoin d'intégrer plus 110 00:05:37,760 --> 00:05:39,530 chaque élément de la liste. 111 00:05:39,530 --> 00:05:42,150 Sauf le dernier élément, puisque l'élément 1 112 00:05:42,150 --> 00:05:44,230 liste déjà triée. 113 00:05:44,230 --> 00:05:48,100 Sur la deuxième ligne, nous considérons que le premier élément de la non triés 114 00:05:48,100 --> 00:05:51,080 partie de la liste pour être le minimum, comme nous l'avons fait avec notre 115 00:05:51,080 --> 00:05:53,750 Par exemple, si nous avons quelque chose à comparer. 116 00:05:53,750 --> 00:05:57,260 La ligne trois débute une deuxième boucle dans laquelle nous itérer sur 117 00:05:57,260 --> 00:05:59,170 chaque élément non triés. 118 00:05:59,170 --> 00:06:02,150 Nous savons que, après i itérations, la partie triée 119 00:06:02,150 --> 00:06:05,330 de notre liste doivent avoir i éléments qu'il contient, car chaque étape 120 00:06:05,330 --> 00:06:06,890 un élément de sortes. 121 00:06:06,890 --> 00:06:11,770 Ainsi, le premier élément non triés doivent être en position i + 1. 122 00:06:11,770 --> 00:06:15,440 Sur la quatrième ligne, nous comparons l'élément courant au minimum 123 00:06:15,440 --> 00:06:17,750 élément que nous avons vu jusqu'à présent. 124 00:06:17,750 --> 00:06:20,560 Si l'élément courant est inférieur au minimum 125 00:06:20,560 --> 00:06:23,870 élément, puis nous nous souvenons de l'élément courant que le nouveau 126 00:06:23,870 --> 00:06:26,250 minimum sur la ligne de cinq ans. 127 00:06:26,250 --> 00:06:29,900 Enfin, sur les lignes six et sept, nous échangeons le minimum 128 00:06:29,900 --> 00:06:33,080 élément avec le premier élément non triés, ainsi 129 00:06:33,080 --> 00:06:36,990 de l'ajouter à la portion de la liste triée. 130 00:06:36,990 --> 00:06:40,030 Une fois que nous avons un algorithme, une question importante à poser 131 00:06:40,030 --> 00:06:43,370 nous en tant que programmeurs est combien de temps prendrait-il? 132 00:06:43,370 --> 00:06:46,970 Nous allons d'abord poser la question combien de temps faut-il pour que cette 133 00:06:46,970 --> 00:06:50,070 algorithme à exécuter dans le pire des cas? 134 00:06:50,070 --> 00:06:51,640 Rappelons que nous avons représenter cette course 135 00:06:51,640 --> 00:06:55,060 temps avec notation grand O. 136 00:06:55,060 --> 00:06:58,650 Afin de déterminer l'élément minimum non triés, nous 137 00:06:58,650 --> 00:07:01,880 essentiellement dû à comparer chaque élément de la liste pour 138 00:07:01,880 --> 00:07:04,040 tous les autres éléments dans la liste. 139 00:07:04,040 --> 00:07:08,430 Intuitivement, cela ressemble à un joint de n opérations carré. 140 00:07:08,430 --> 00:07:12,050 En regardant notre pseudo-code, nous avons également une boucle imbriquée à l'intérieur 141 00:07:12,050 --> 00:07:14,420 une autre boucle, ce qui sonne bien comme un O 142 00:07:14,420 --> 00:07:16,480 n de fonctionnement au carré. 143 00:07:16,480 --> 00:07:19,250 Cependant, n'oubliez pas que nous n'avons pas besoin de regarder par-dessus l' 144 00:07:19,250 --> 00:07:23,460 liste entière lorsqu'il s'agit de déterminer l'élément minimum non triés? 145 00:07:23,460 --> 00:07:26,600 Une fois que nous savions que le 4 a été triée par exemple, nous n'avons pas 146 00:07:26,600 --> 00:07:28,170 besoin de regarder à nouveau. 147 00:07:28,170 --> 00:07:31,020 Il en va de cette baisse de la durée de fonctionnement? 148 00:07:31,020 --> 00:07:34,510 Pour notre liste de longueur 6, nous avions besoin de faire cinq 149 00:07:34,510 --> 00:07:37,990 les comparaisons pour le premier élément, pour quatre comparaisons 150 00:07:37,990 --> 00:07:40,750 le second élément, et ainsi de suite. 151 00:07:40,750 --> 00:07:44,690 Cela signifie que le nombre total d'étapes est la somme de 152 00:07:44,690 --> 00:07:49,160 les entiers de 1 à la longueur de la liste moins 1. 153 00:07:49,160 --> 00:07:51,005 On peut représenter cela avec une sommation. 154 00:07:57,980 --> 00:07:59,910 Nous n'entrerons pas dans sommations ici. 155 00:07:59,910 --> 00:08:04,900 Mais il s'avère que cette somme est égale à n fois 156 00:08:04,900 --> 00:08:07,540 n moins 1 sur 2. 157 00:08:07,540 --> 00:08:14,220 Ou de manière équivalente, n au carré de plus de 2 moins n supérieur à 2. 158 00:08:14,220 --> 00:08:18,860 Quand on parle d'exécution asymptotique, ce terme n au carré 159 00:08:18,860 --> 00:08:22,070 va dominer ce terme n. 160 00:08:22,070 --> 00:08:27,850 Donc, tri par sélection est O n carré. 161 00:08:27,850 --> 00:08:31,460 Rappelons que dans notre exemple, tri par sélection encore nécessaires pour 162 00:08:31,460 --> 00:08:33,850 vérifier si un numéro a déjà été trié 163 00:08:33,850 --> 00:08:35,450 doit être déplacé. 164 00:08:35,450 --> 00:08:38,929 Cela signifie donc que si nous avons couru tri par sélection sur une déjà 165 00:08:38,929 --> 00:08:43,070 liste triée, il faudra le même nombre de pas qu'il 166 00:08:43,070 --> 00:08:46,340 serait lors de l'exécution sur une liste complètement non triés. 167 00:08:46,340 --> 00:08:51,470 Donc, tri par sélection a un rendement meilleur des cas, de carré n, 168 00:08:51,470 --> 00:08:56,820 que nous représentons en oméga n carré. 169 00:08:56,820 --> 00:08:58,600 Et c'est tout pour le tri de sélection. 170 00:08:58,600 --> 00:09:00,630 Juste un des nombreux algorithmes que nous pouvons 171 00:09:00,630 --> 00:09:02,390 utiliser pour trier la liste. 172 00:09:02,390 --> 00:09:05,910 Mon nom est Tommy, et c'est CS50.