1
00:00:00,000 --> 00:00:05,726
>> [Jouer de la musique]

2
00:00:05,726 --> 00:00:08,600
DOUG LLOYD: Sélection sorte est un
algorithme qui, comme vous vous en doutez,

3
00:00:08,600 --> 00:00:10,470
trie un ensemble d'éléments.

4
00:00:10,470 --> 00:00:12,470
Et algorithme rappel
est un ensemble étape par étape

5
00:00:12,470 --> 00:00:15,260
des instructions pour remplir une tâche.

6
00:00:15,260 --> 00:00:17,580
>> Dans la sélection trier la
idée de base est présent,

7
00:00:17,580 --> 00:00:22,080
trouver l'élément le plus petit et non triés
ajouter à la fin de la liste triée.

8
00:00:22,080 --> 00:00:26,970
Effectivement ce qu'il fait est build
une liste triée, un élément à la fois.

9
00:00:26,970 --> 00:00:29,800
Décomposant au pseudo-
nous pourrions affirmer cet algorithme

10
00:00:29,800 --> 00:00:34,490
comme suit, Répétez jusqu'à ce que
pas d'éléments non triés demeurent.

11
00:00:34,490 --> 00:00:38,660
Recherchez dans les non triés
données pour trouver la plus petite valeur,

12
00:00:38,660 --> 00:00:44,130
puis échanger la plus petite valeur à la
premier élément de la partie non triés.

13
00:00:44,130 --> 00:00:47,130
>> Il peut aider à visualiser ce,
nous allons donc jeter un oeil à ce.

14
00:00:47,130 --> 00:00:49,710
Donc, je soutiens, est un
tableau non trié et je l'ai

15
00:00:49,710 --> 00:00:53,040
indiqué qu'il en indiquant que tous les
des éléments sont colorés en rouge,

16
00:00:53,040 --> 00:00:54,420
ils ne sont pas encore triées.

17
00:00:54,420 --> 00:00:57,670
Ceci constitue la totalité
partie non triés du tableau.

18
00:00:57,670 --> 00:01:02,020
>> Donc, nous allons passer par les étapes de
sélection Trier pour trier ce tableau.

19
00:01:02,020 --> 00:01:05,296
Encore une fois, nous allons répétition
jusqu'à ce qu'aucun des éléments non triés demeurent.

20
00:01:05,296 --> 00:01:07,920
Nous allons à travers la recherche
données pour trouver la plus petite valeur,

21
00:01:07,920 --> 00:01:11,990
puis échanger cette valeur avec le
premier élément de la partie non triés.

22
00:01:11,990 --> 00:01:14,380
>> À l'heure actuelle, encore une fois, l'ensemble
tableau est la partie non triés.

23
00:01:14,380 --> 00:01:16,534
Tous les éléments rouges sont triés.

24
00:01:16,534 --> 00:01:18,700
Donc, nous cherchons à travers et
nous trouvons la plus petite valeur.

25
00:01:18,700 --> 00:01:20,533
Nous commençons par le début,
nous allons à la fin,

26
00:01:20,533 --> 00:01:23,630
nous trouvons la plus petite valeur est, un.

27
00:01:23,630 --> 00:01:24,860
Voilà donc la première partie.

28
00:01:24,860 --> 00:01:29,440
Et puis la deuxième partie, de swap avec cette valeur
le premier élément de la partie non triés,

29
00:01:29,440 --> 00:01:31,340
ou le premier élément rouge.

30
00:01:31,340 --> 00:01:34,980
>> Dans ce cas, ce serait
cinq ans, de sorte que nous permuter un et cinq.

31
00:01:34,980 --> 00:01:37,320
Lorsque nous faisons cela, nous pouvons
voyons visuellement que nous avons

32
00:01:37,320 --> 00:01:41,260
déplacé l'élément valeur plus petite
de la matrice, au début.

33
00:01:41,260 --> 00:01:43,920
Trier efficacement cet élément.

34
00:01:43,920 --> 00:01:47,520
>> Et si nous pouvons en effet confirmer
et de l'état que l'on est trié.

35
00:01:47,520 --> 00:01:52,080
Et donc nous allons indiquer la partie trié
de notre gamme, en le colorant bleu.

36
00:01:52,080 --> 00:01:53,860
>> Maintenant, nous avons juste répéter le processus.

37
00:01:53,860 --> 00:01:57,430
Nous recherchons à travers la partie non triés du
le tableau pour trouver le plus petit élément.

38
00:01:57,430 --> 00:01:59,000
Dans ce cas, il est deux.

39
00:01:59,000 --> 00:02:02,100
>> Nous swap avec la première
élément de la partie non triés.

40
00:02:02,100 --> 00:02:05,540
Dans ce cas, les deux se trouve être également
le premier élément de la partie non triés.

41
00:02:05,540 --> 00:02:08,650
Donc, nous échangeons deux avec lui-même,
ce qui laisse vraiment que deux

42
00:02:08,650 --> 00:02:11,257
où il est, et il est triée.

43
00:02:11,257 --> 00:02:13,840
En continuant, nous cherchons à travers
pour trouver le plus petit élément.

44
00:02:13,840 --> 00:02:15,030
Il est trois.

45
00:02:15,030 --> 00:02:17,650
Nous échangeons avec le premier
élément, qui est de cinq.

46
00:02:17,650 --> 00:02:19,450
Et maintenant trois est trié.

47
00:02:19,450 --> 00:02:22,440
>> Nous recherchons à travers encore une fois, et nous
trouver le plus petit élément est de quatre.

48
00:02:22,440 --> 00:02:28,070
Nous échanger avec le premier élément de la
partie non triés, et maintenant quatre sont triés.

49
00:02:28,070 --> 00:02:29,910
>> Nous constatons que cinq est
le plus petit élément.

50
00:02:29,910 --> 00:02:32,900
Nous échangeons avec le premier
élément de la partie non triés.

51
00:02:32,900 --> 00:02:34,740
Et maintenant, cinq sont triés.

52
00:02:34,740 --> 00:02:36,660
>> Et puis enfin, notre
partie non triés consiste

53
00:02:36,660 --> 00:02:38,576
de juste un seul élément,
de sorte que nous recherchons à travers

54
00:02:38,576 --> 00:02:41,740
et nous constatons que six est le
plus petite, et en fait, seul élément.

55
00:02:41,740 --> 00:02:44,906
Et puis, nous pouvons affirmer qu'il est triée.

56
00:02:44,906 --> 00:02:47,530
Et maintenant, nous avons changé notre gamme
d'être complètement non triés

57
00:02:47,530 --> 00:02:52,660
en rouge, complètement trié
en bleu, en utilisant la sélection sorte.

58
00:02:52,660 --> 00:02:54,920
>> Alors, quel est le pire des cas ici?

59
00:02:54,920 --> 00:02:57,830
Eh bien, dans le pire absolue
cas, nous devons regarder au-dessus

60
00:02:57,830 --> 00:03:02,170
tous les éléments de la matrice à
trouver l'élément non triés plus petit,

61
00:03:02,170 --> 00:03:04,750
et nous devons répéter
ce processus n fois.

62
00:03:04,750 --> 00:03:09,090
Une fois pour chaque élément de la matrice
parce que nous ne, dans cet algorithme,

63
00:03:09,090 --> 00:03:12,180
sorte un élément à la fois.

64
00:03:12,180 --> 00:03:13,595
>> Quel est le meilleur scénario?

65
00:03:13,595 --> 00:03:15,040
Eh bien, il est exactement la même, non?

66
00:03:15,040 --> 00:03:18,440
Nous avons fait à l'étape encore à travers
chaque élément du tableau

67
00:03:18,440 --> 00:03:22,040
afin de confirmer que ce soit,
en effet, le plus petit élément.

68
00:03:22,040 --> 00:03:26,760
>> Donc le pire des cas d'exécution, nous
avoir à répéter un processus n fois,

69
00:03:26,760 --> 00:03:28,960
une fois pour chacun des n éléments.

70
00:03:28,960 --> 00:03:31,940
Et dans le meilleur des cas,
nous devons faire la même chose.

71
00:03:31,940 --> 00:03:35,340
>> Donc, en repensant à notre
boîte à outils de calcul de la complexité,

72
00:03:35,340 --> 00:03:39,250
que pensez-vous est le pire
cas d'exécution pour la sélection sorte?

73
00:03:39,250 --> 00:03:41,840
Que pensez-vous est le meilleur
cas d'exécution pour la sélection sorte?

74
00:03:41,840 --> 00:03:44,760

75
00:03:44,760 --> 00:03:49,325
>> Avez-vous deviné de Big O n carré,
et Big Omega carré de n?

76
00:03:49,325 --> 00:03:49,950
Vous avez raison.

77
00:03:49,950 --> 00:03:52,490
Ce sont, en fait, la
pire et le meilleur run de cas

78
00:03:52,490 --> 00:03:55,100
fois, pour la sélection sorte.

79
00:03:55,100 --> 00:03:56,260
>> Je suis Doug Lloyd.

80
00:03:56,260 --> 00:03:58,600
Ceci est CS50.

81
00:03:58,600 --> 00:04:00,279