1
00:00:00,000 --> 00:00:05,726
>> [MUSIC SPILLE]

2
00:00:05,726 --> 00:00:08,600
DOUG LLOYD: Utvalg sort er en
algoritme som, som du kanskje forventer,

3
00:00:08,600 --> 00:00:10,470
sorterer et sett av elementer.

4
00:00:10,470 --> 00:00:12,470
Og algoritme tilbakekalling
er en steg-for-steg sett

5
00:00:12,470 --> 00:00:15,260
instruks for å fullføre en oppgave.

6
00:00:15,260 --> 00:00:17,580
>> I utvalget sortere
grunnleggende ideen er dette,

7
00:00:17,580 --> 00:00:22,080
finne den minste usortert element og
legge den til slutten av den sorterte listen.

8
00:00:22,080 --> 00:00:26,970
Effektivt hva dette gjør er build
en sortert liste, ett element om gangen.

9
00:00:26,970 --> 00:00:29,800
Bryte det ned til pseudo
vi kunne oppgi denne algoritmen

10
00:00:29,800 --> 00:00:34,490
som følger, gjenta dette til
ingen usorterte elementer forbli.

11
00:00:34,490 --> 00:00:38,660
Gjennom usortert søke
data for å finne den minste verdien,

12
00:00:38,660 --> 00:00:44,130
deretter bytte den minste verdien med
første element i usortert del.

13
00:00:44,130 --> 00:00:47,130
>> Det kan bidra til å visualisere dette,
så la oss ta en titt på dette.

14
00:00:47,130 --> 00:00:49,710
Så dette, jeg hevder, er en
usortert array og jeg har

15
00:00:49,710 --> 00:00:53,040
indikeres det ved å indikerer at all
av elementene er farget rød,

16
00:00:53,040 --> 00:00:54,420
de er ennå ikke sortert.

17
00:00:54,420 --> 00:00:57,670
Dette er hele
usortert del av tabellen.

18
00:00:57,670 --> 00:01:02,020
>> Så la oss gå gjennom trinnene
utvalg sorter å sortere array.

19
00:01:02,020 --> 00:01:05,296
Så igjen, vi skal gjenta
til det gjenstår noen usorterte elementer.

20
00:01:05,296 --> 00:01:07,920
Vi skal søke gjennom
data for å finne den minste verdien,

21
00:01:07,920 --> 00:01:11,990
og deretter bytte denne verdien med
første element i usortert del.

22
00:01:11,990 --> 00:01:14,380
>> Akkurat nå, igjen, hele
matrise er usortert del.

23
00:01:14,380 --> 00:01:16,534
Alle de røde elementene er usortert.

24
00:01:16,534 --> 00:01:18,700
Så vi søke gjennom og
vi finner den minste verdien.

25
00:01:18,700 --> 00:01:20,533
Vi starter i begynnelsen,
vi går til enden,

26
00:01:20,533 --> 00:01:23,630
vi finne den minste verdien er, en.

27
00:01:23,630 --> 00:01:24,860
Så det er en del en.

28
00:01:24,860 --> 00:01:29,440
Og så del to, bytte denne verdien med
det første element av usortert del,

29
00:01:29,440 --> 00:01:31,340
eller den første røde element.

30
00:01:31,340 --> 00:01:34,980
>> I dette tilfellet ville det være
fem, så vi bytte en og fem.

31
00:01:34,980 --> 00:01:37,320
Når vi gjør dette, kan vi
visuelt se at vi har

32
00:01:37,320 --> 00:01:41,260
flyttet den minste verdsatt element
av tabellen, til begynnelsen.

33
00:01:41,260 --> 00:01:43,920
Effektivt sortering som element.

34
00:01:43,920 --> 00:01:47,520
>> Og så kan vi faktisk bekrefte
og stat at man blir sortert.

35
00:01:47,520 --> 00:01:52,080
Og så får vi indikere sortert delen
av vår rekke, ved å farge det blå.

36
00:01:52,080 --> 00:01:53,860
>> Nå er vi bare gjenta prosessen på nytt.

37
00:01:53,860 --> 00:01:57,430
Vi søker gjennom usortert del av
array for å finne den minste element.

38
00:01:57,430 --> 00:01:59,000
I dette tilfellet er det to.

39
00:01:59,000 --> 00:02:02,100
>> Vi bytter at med det første
element i usortert del.

40
00:02:02,100 --> 00:02:05,540
I dette tilfellet to også tilfeldigvis
det første elementet i usortert del.

41
00:02:05,540 --> 00:02:08,650
Så vi bytte to med seg selv,
som egentlig bare etterlater to

42
00:02:08,650 --> 00:02:11,257
hvor det er, og det er sortert.

43
00:02:11,257 --> 00:02:13,840
Fortsetter på, søke vi gjennom
for å finne den minste element.

44
00:02:13,840 --> 00:02:15,030
Det er tre.

45
00:02:15,030 --> 00:02:17,650
Vi bytte den med det første
element, som er fem.

46
00:02:17,650 --> 00:02:19,450
Og nå tre er sortert.

47
00:02:19,450 --> 00:02:22,440
>> Vi søker gjennom igjen, og vi
finner det minste elementet er fire.

48
00:02:22,440 --> 00:02:28,070
Vi bytte den med det første elementet av
usortert del, og nå er det fire er sortert.

49
00:02:28,070 --> 00:02:29,910
>> Vi finner at fem er
det minste elementet.

50
00:02:29,910 --> 00:02:32,900
Vi bytte den med det første
element i usortert del.

51
00:02:32,900 --> 00:02:34,740
Og nå har fem er sortert.

52
00:02:34,740 --> 00:02:36,660
>> Og så til slutt, vår
usortert delen består

53
00:02:36,660 --> 00:02:38,576
av bare et enkelt element,
så vi søker gjennom

54
00:02:38,576 --> 00:02:41,740
og vi finner at seks er
minste, og faktisk bare element.

55
00:02:41,740 --> 00:02:44,906
Og så kan vi si at det er sortert.

56
00:02:44,906 --> 00:02:47,530
Og nå har vi slått våre utvalg
fra å være helt usortert

57
00:02:47,530 --> 00:02:52,660
rødt, å fullstendig, sortert
i blått, ved hjelp av valg liksom.

58
00:02:52,660 --> 00:02:54,920
>> Så hva er worst case scenario her?

59
00:02:54,920 --> 00:02:57,830
Vel i den absolutt verste
tilfelle, må vi se over

60
00:02:57,830 --> 00:03:02,170
alle elementene i matrisen til
finne den minste usortert element,

61
00:03:02,170 --> 00:03:04,750
og vi må gjenta
denne prosessen n ganger.

62
00:03:04,750 --> 00:03:09,090
En gang for hvert element i matrisen
fordi bare vi, i denne algoritmen,

63
00:03:09,090 --> 00:03:12,180
sort element på en gang.

64
00:03:12,180 --> 00:03:13,595
>> Hva er den best case scenario?

65
00:03:13,595 --> 00:03:15,040
Vel det er akkurat det samme, ikke sant?

66
00:03:15,040 --> 00:03:18,440
Vi har faktisk å fortsatt gå gjennom
hvert enkelt element i matrisen

67
00:03:18,440 --> 00:03:22,040
for å bekrefte at det er,
faktisk det minste elementet.

68
00:03:22,040 --> 00:03:26,760
>> Så verste fall runtime, vi
må gjenta en prosess n ganger,

69
00:03:26,760 --> 00:03:28,960
en gang for hver av n elementer.

70
00:03:28,960 --> 00:03:31,940
Og i beste fall
vi må gjøre det samme.

71
00:03:31,940 --> 00:03:35,340
>> Så tenker tilbake til vår
beregningsorientert kompleksitet verktøykasse,

72
00:03:35,340 --> 00:03:39,250
hva tror du er den verste
case runtime for valg slag?

73
00:03:39,250 --> 00:03:41,840
Hva tror du er den beste
case runtime for valg slag?

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

75
00:03:44,760 --> 00:03:49,325
>> Visste du gjette Big O n squared,
og Big Omega n squared?

76
00:03:49,325 --> 00:03:49,950
Du ville være riktig.

77
00:03:49,950 --> 00:03:52,490
De er, faktisk,
worst case og best case run

78
00:03:52,490 --> 00:03:55,100
ganger, for valg liksom.

79
00:03:55,100 --> 00:03:56,260
>> Jeg er Doug Lloyd.

80
00:03:56,260 --> 00:03:58,600
Dette er CS50.

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