1
00:00:00,000 --> 00:00:05,726
>> [Speel van musiek]

2
00:00:05,726 --> 00:00:08,600
DOUG LLOYD: Seleksie soort is 'n
algoritme wat, soos jy kan verwag,

3
00:00:08,600 --> 00:00:10,470
sorteer 'n stel van elemente.

4
00:00:10,470 --> 00:00:12,470
En algoritme herroep
is 'n stel stap-vir-stap

5
00:00:12,470 --> 00:00:15,260
instruksies vir die voltooiing van 'n taak.

6
00:00:15,260 --> 00:00:17,580
>> In seleksie sorteer die
basiese idee is dit,

7
00:00:17,580 --> 00:00:22,080
vind die kleinste ongesorteerde element en
voeg dit by die einde van die gesorteerde lys.

8
00:00:22,080 --> 00:00:26,970
Effektief wat dit doen, is die bou
'n gesorteerde lys, een element op 'n slag.

9
00:00:26,970 --> 00:00:29,800
Breek dit af na pseudokode
ons kon hierdie algoritme meld

10
00:00:29,800 --> 00:00:34,490
soos volg, herhaal totdat
geen ongesorteerde elemente bly.

11
00:00:34,490 --> 00:00:38,660
Soek deur die ongesorteerde
data na die kleinste waarde vind,

12
00:00:38,660 --> 00:00:44,130
dan ruil die kleinste waarde van die
eerste element van die ongesorteerde deel.

13
00:00:44,130 --> 00:00:47,130
>> Dit kan help om hierdie visualiseer,
so laat ons neem 'n blik op hierdie.

14
00:00:47,130 --> 00:00:49,710
So hierdie, ek stry, is 'n
ongesorteerde verskeidenheid en ek het

15
00:00:49,710 --> 00:00:53,040
aangedui dat hy deur aan te dui dat alle
van die elemente is rooi gekleur,

16
00:00:53,040 --> 00:00:54,420
hulle nog nie gesorteer.

17
00:00:54,420 --> 00:00:57,670
Dit is die hele
ongesorteerde deel van die skikking.

18
00:00:57,670 --> 00:01:02,020
>> So laat ons gaan deur die stappe van
seleksie soort om hierdie verskeidenheid te sorteer.

19
00:01:02,020 --> 00:01:05,296
So weer, ons gaan herhaal
totdat daar geen ongesorteerde elemente bly.

20
00:01:05,296 --> 00:01:07,920
Ons gaan soek deur die
data na die kleinste waarde vind,

21
00:01:07,920 --> 00:01:11,990
en dan ruil wat waarde by die
eerste element van die ongesorteerde deel.

22
00:01:11,990 --> 00:01:14,380
>> Nou, weer, die hele
skikking is die ongesorteerde deel.

23
00:01:14,380 --> 00:01:16,534
Al die elemente is rooi ongesorteerde.

24
00:01:16,534 --> 00:01:18,700
So soek ons ​​deur en
vind ons die kleinste waarde.

25
00:01:18,700 --> 00:01:20,533
Ons begin by die begin,
ons gaan na die einde,

26
00:01:20,533 --> 00:01:23,630
vind ons die kleinste waarde is, een.

27
00:01:23,630 --> 00:01:24,860
So dit is deel een.

28
00:01:24,860 --> 00:01:29,440
En dan deel twee, ruil wat waarde met
die eerste element van die ongesorteerde deel,

29
00:01:29,440 --> 00:01:31,340
of die eerste rooi element.

30
00:01:31,340 --> 00:01:34,980
>> In hierdie geval sal dit nie wees
vyf, so ons ruil een en vyf.

31
00:01:34,980 --> 00:01:37,320
Wanneer ons dit doen, kan ons
visueel sien dat ons het

32
00:01:37,320 --> 00:01:41,260
verskuif die kleinste waarde element
van die skikking, na die begin.

33
00:01:41,260 --> 00:01:43,920
Effektief te sorteer daardie element.

34
00:01:43,920 --> 00:01:47,520
>> En so kan ons inderdaad bevestig
en staat wat een word gesorteer.

35
00:01:47,520 --> 00:01:52,080
En so sal ons die gedeelte dui gesorteer
van ons skikking, deur kleur dit blou.

36
00:01:52,080 --> 00:01:53,860
>> Nou het ons net weer herhaal die proses.

37
00:01:53,860 --> 00:01:57,430
Ons soek deur die ongesorteerde deel van
die skikking na die kleinste element te vind.

38
00:01:57,430 --> 00:01:59,000
In hierdie geval, dit is twee.

39
00:01:59,000 --> 00:02:02,100
>> Ons ruil dat met die eerste
element van die ongesorteerde deel.

40
00:02:02,100 --> 00:02:05,540
In hierdie geval twee gebeur ook te wees
die eerste element van die ongesorteerde deel.

41
00:02:05,540 --> 00:02:08,650
So ruil ons twee met homself,
wat eintlik net laat twee

42
00:02:08,650 --> 00:02:11,257
waar dit is, en dit is gesorteer.

43
00:02:11,257 --> 00:02:13,840
Voortgesette op, soek ons ​​deur
die kleinste element te vind.

44
00:02:13,840 --> 00:02:15,030
Dit is drie.

45
00:02:15,030 --> 00:02:17,650
Ons ruil dit met die eerste
element, wat vyf.

46
00:02:17,650 --> 00:02:19,450
En nou drie gesorteer.

47
00:02:19,450 --> 00:02:22,440
>> Ons soek weer deur, en ons
vind die kleinste element is vier.

48
00:02:22,440 --> 00:02:28,070
Ons ruil dit met die eerste element van die
ongesorteerde deel, en nou vier gesorteer.

49
00:02:28,070 --> 00:02:29,910
>> Ons vind dat vyf is
die kleinste element.

50
00:02:29,910 --> 00:02:32,900
Ons ruil dit met die eerste
element van die ongesorteerde deel.

51
00:02:32,900 --> 00:02:34,740
En nou vyf gesorteer.

52
00:02:34,740 --> 00:02:36,660
>> En dan laastens, ons
ongesorteerde gedeelte bestaan

53
00:02:36,660 --> 00:02:38,576
van net 'n enkele element,
sodat ons soek deur

54
00:02:38,576 --> 00:02:41,740
en ons vind dat ses is die
kleinste, en in werklikheid, net element.

55
00:02:41,740 --> 00:02:44,906
En dan kan ons sê dat dit gesorteer.

56
00:02:44,906 --> 00:02:47,530
En nou het ons ons verskeidenheid aangeskakel
uit om heeltemal Unsorted

57
00:02:47,530 --> 00:02:52,660
in rooi, heeltemal gesorteer
in blou, met behulp van seleksie soort.

58
00:02:52,660 --> 00:02:54,920
>> So, wat is die ergste geval scenario hier?

59
00:02:54,920 --> 00:02:57,830
Wel, in die absolute ergste
geval, ons het om te kyk oor

60
00:02:57,830 --> 00:03:02,170
al die elemente van die skikking te
vind die kleinste ongesorteerde element,

61
00:03:02,170 --> 00:03:04,750
en ons moet herhaal
hierdie proses n keer.

62
00:03:04,750 --> 00:03:09,090
Een keer vir elke element van die skikking
want net wat ons in hierdie algoritme

63
00:03:09,090 --> 00:03:12,180
sorteer een element op die tyd.

64
00:03:12,180 --> 00:03:13,595
>> Wat is die beste scenario?

65
00:03:13,595 --> 00:03:15,040
Wel dit is presies dieselfde, reg?

66
00:03:15,040 --> 00:03:18,440
Ons het eintlik nog stap vir stap deur
elke enkele element van die skikking

67
00:03:18,440 --> 00:03:22,040
om te bevestig dat dit is,
in werklikheid, die kleinste element.

68
00:03:22,040 --> 00:03:26,760
>> So het die ergste geval runtime, ons
moet 'n proses n keer herhaal,

69
00:03:26,760 --> 00:03:28,960
eens en vir elkeen van n elemente.

70
00:03:28,960 --> 00:03:31,940
En in die beste geval,
ons het om dieselfde te doen.

71
00:03:31,940 --> 00:03:35,340
>> So dink terug aan ons
rekenkundige kompleksiteit toolbox,

72
00:03:35,340 --> 00:03:39,250
wat dink jy is die ergste
geval runtime vir keuring soort?

73
00:03:39,250 --> 00:03:41,840
Wat dink jy is die beste
geval runtime vir keuring soort?

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

75
00:03:44,760 --> 00:03:49,325
>> Het jy raai Big O van n vierkant,
en Big Omega van N kwadraat?

76
00:03:49,325 --> 00:03:49,950
Jy wil reg wees.

77
00:03:49,950 --> 00:03:52,490
Dit is, in werklikheid, die
ergste geval en die beste geval run

78
00:03:52,490 --> 00:03:55,100
tye, vir keuring soort.

79
00:03:55,100 --> 00:03:56,260
>> Ek is Doug Lloyd.

80
00:03:56,260 --> 00:03:58,600
Dit is CS50.

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