[Jouer de la musique] DOUG LLOYD: Sélection sorte est un algorithme qui, comme vous vous en doutez, trie un ensemble d'éléments. Et algorithme rappel est un ensemble étape par étape des instructions pour remplir une tâche. 

Dans la sélection trier la idée de base est présent, trouver l'élément le plus petit et non triés ajouter à la fin de la liste triée. Effectivement ce qu'il fait est build une liste triée, un élément à la fois. Décomposant au pseudo- nous pourrions affirmer cet algorithme comme suit, Répétez jusqu'à ce que pas d'éléments non triés demeurent. Recherchez dans les non triés données pour trouver la plus petite valeur, puis échanger la plus petite valeur à la premier élément de la partie non triés. 

Il peut aider à visualiser ce, nous allons donc jeter un oeil à ce. Donc, je soutiens, est un tableau non trié et je l'ai indiqué qu'il en indiquant que tous les des éléments sont colorés en rouge, ils ne sont pas encore triées. Ceci constitue la totalité partie non triés du tableau. 

Donc, nous allons passer par les étapes de sélection Trier pour trier ce tableau. Encore une fois, nous allons répétition jusqu'à ce qu'aucun des éléments non triés demeurent. Nous allons à travers la recherche données pour trouver la plus petite valeur, puis échanger cette valeur avec le premier élément de la partie non triés. 

À l'heure actuelle, encore une fois, l'ensemble tableau est la partie non triés. Tous les éléments rouges sont triés. Donc, nous cherchons à travers et nous trouvons la plus petite valeur. Nous commençons par le début, nous allons à la fin, nous trouvons la plus petite valeur est, un. Voilà donc la première partie. Et puis la deuxième partie, de swap avec cette valeur le premier élément de la partie non triés, ou le premier élément rouge. 

Dans ce cas, ce serait cinq ans, de sorte que nous permuter un et cinq. Lorsque nous faisons cela, nous pouvons voyons visuellement que nous avons déplacé l'élément valeur plus petite de la matrice, au début. Trier efficacement cet élément. 

Et si nous pouvons en effet confirmer et de l'état que l'on est trié. Et donc nous allons indiquer la partie trié de notre gamme, en le colorant bleu. 

Maintenant, nous avons juste répéter le processus. Nous recherchons à travers la partie non triés du le tableau pour trouver le plus petit élément. Dans ce cas, il est deux. 

Nous swap avec la première élément de la partie non triés. Dans ce cas, les deux se trouve être également le premier élément de la partie non triés. Donc, nous échangeons deux avec lui-même, ce qui laisse vraiment que deux où il est, et il est triée. En continuant, nous cherchons à travers pour trouver le plus petit élément. Il est trois. Nous échangeons avec le premier élément, qui est de cinq. Et maintenant trois est trié. 

Nous recherchons à travers encore une fois, et nous trouver le plus petit élément est de quatre. Nous échanger avec le premier élément de la partie non triés, et maintenant quatre sont triés. 

Nous constatons que cinq est le plus petit élément. Nous échangeons avec le premier élément de la partie non triés. Et maintenant, cinq sont triés. 

Et puis enfin, notre partie non triés consiste de juste un seul élément, de sorte que nous recherchons à travers et nous constatons que six est le plus petite, et en fait, seul élément. Et puis, nous pouvons affirmer qu'il est triée. Et maintenant, nous avons changé notre gamme d'être complètement non triés en rouge, complètement trié en bleu, en utilisant la sélection sorte. 

Alors, quel est le pire des cas ici? Eh bien, dans le pire absolue cas, nous devons regarder au-dessus tous les éléments de la matrice à trouver l'élément non triés plus petit, et nous devons répéter ce processus n fois. Une fois pour chaque élément de la matrice parce que nous ne, dans cet algorithme, sorte un élément à la fois. 

Quel est le meilleur scénario? Eh bien, il est exactement la même, non? Nous avons fait à l'étape encore à travers chaque élément du tableau afin de confirmer que ce soit, en effet, le plus petit élément. 

Donc le pire des cas d'exécution, nous avoir à répéter un processus n fois, une fois pour chacun des n éléments. Et dans le meilleur des cas, nous devons faire la même chose. 

Donc, en repensant à notre boîte à outils de calcul de la complexité, que pensez-vous est le pire cas d'exécution pour la sélection sorte? Que pensez-vous est le meilleur cas d'exécution pour la sélection sorte? 

Avez-vous deviné de Big O n carré, et Big Omega carré de n? Vous avez raison. Ce sont, en fait, la pire et le meilleur run de cas fois, pour la sélection sorte. 

Je suis Doug Lloyd. Ceci est CS50.