[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.