1
00:00:00,000 --> 00:00:02,290
[Powered by Google Translate] [Įterpiama Rūšiuoti]

2
00:00:02,290 --> 00:00:04,240
[Tommy MacWilliam] [Harvardo universiteto]

3
00:00:04,240 --> 00:00:07,290
[Tai CS50.TV]

4
00:00:07,290 --> 00:00:13,060
Paimkime atrodo, bent įterpimo Rūšiuoti algoritmas numerių sąrašą ir rūšiavimą.

5
00:00:13,060 --> 00:00:18,300
Algoritmas, atminkite, kad yra tiesiog žingsnis po žingsnio procedūrą įvykdyti užduotį.

6
00:00:18,300 --> 00:00:23,640
Pagrindinė idėja už įterpimo rūšiuoti, yra suskirstyti į mūsų sąrašą į dvi dalis,

7
00:00:23,640 --> 00:00:26,580
surūšiuoti dalis ir nerūšiuotų dalis.

8
00:00:26,580 --> 00:00:29,290
>> Kiekvieno algoritmo žingsnyje, numeris perkeltas

9
00:00:29,290 --> 00:00:32,439
nuo nerūšiuotų dalis išrūšiuotų dalis

10
00:00:32,439 --> 00:00:35,680
kol galiausiai Visas sąrašas surūšiuotas.

11
00:00:35,680 --> 00:00:43,340
Čia yra šešių nesurūšiuotų skaičių, sąrašas - 23, 42, 4, 16, 8, ir 15.

12
00:00:43,340 --> 00:00:47,680
Kadangi šie numeriai yra ne visi, didėjančia tvarka, jie nerūšiuotų.

13
00:00:47,680 --> 00:00:53,890
Kadangi mes pradėjo rūšiavimas dar, mes atsižvelgsime į visus šešių elementų mūsų nerūšiuotų dalį.

14
00:00:53,890 --> 00:00:59,270
>> Kai mes pradedame rūšiavimas, mes įdėti šias surūšiuotas numerius šių kairėje.

15
00:00:59,270 --> 00:01:03,600
Taigi, pradėkime 23, pirmasis elementas mūsų sąraše.

16
00:01:03,600 --> 00:01:06,930
Mes neturime dar jokių mūsų rūšiuotų dalis elementus,

17
00:01:06,930 --> 00:01:12,460
tad tiesiog apsvarstyti 23 veiklos pradžia ir pabaiga mūsų rūšiuotų dalį.

18
00:01:12,460 --> 00:01:16,510
Dabar mūsų surūšiuoti dalis turi vieną telefono numerį, 23,

19
00:01:16,510 --> 00:01:20,260
ir mūsų nerūšiuotų dalis turi šiuos penkis skaičius.

20
00:01:20,260 --> 00:01:27,320
Tegul dabar įterpti kitą skaičių mūsų nerūšiuotų dalį, 42, į išrūšiuotų dalis.

21
00:01:27,320 --> 00:01:35,930
>> Norėdami tai padaryti, mes reikia lyginti nuo 42 iki 23 d - vienintelis elementas mūsų rūšiuotų dalį iki šiol.

22
00:01:35,930 --> 00:01:41,980
Keturiasdešimt du yra didesnis nei 23, todėl mes galime pridėti 42 iki galo

23
00:01:41,980 --> 00:01:45,420
išrūšiuotų sąrašo dalį. Puiku!

24
00:01:45,420 --> 00:01:51,850
Dabar mūsų surūšiuoti dalis turi du elementus ir mūsų nerūšiuotų dalis turi keturis elementus.

25
00:01:51,850 --> 00:01:57,200
Taigi, tegul dabar pereiti į 4, Kitas elementas į nerūšiuotų dalis.

26
00:01:57,200 --> 00:02:00,230
Taigi, kur tai turėtų būti pateikiami išrūšiuotų dalis?

27
00:02:00,230 --> 00:02:04,220
>> Nepamirškite, kad mes norime šį skaičių rūšiuotų tvarka

28
00:02:04,220 --> 00:02:08,680
todėl mūsų surūšiuoti dalis išlieka teisingai surūšiuoti visais laikais.

29
00:02:08,680 --> 00:02:14,380
Jei mes 4 į dešinę iš 42, tada mūsų sąraše bus ne iš eilės.

30
00:02:14,380 --> 00:02:18,380
Taigi, tegul toliau juda iš dešinės į kairę, į mūsų rūšiavimo dalį.

31
00:02:18,380 --> 00:02:23,260
Kaip mes judėti, galime perkelti kiekvieno numerio žemyn vieta padaryti vietos naujam numeriui.

32
00:02:25,440 --> 00:02:31,740
Gerai, 4, taip pat mažiau nei 23, todėl mes negalime įdėti jį čia arba.

33
00:02:31,740 --> 00:02:34,480
Pereikime 23 tinkamą vieną vietą.

34
00:02:36,500 --> 00:02:43,120
>> Tai reiškia, kad mes norėtume, kad į pirmą lizdą išrūšiuotų dalis 4.

35
00:02:43,120 --> 00:02:46,300
Atkreipkite dėmesį, kaip tai erdvė sąraše jau buvo tušti,

36
00:02:46,300 --> 00:02:51,120
nes mes jau juda surūšiuoti elementus, kaip mes susidūrėme.

37
00:02:51,120 --> 00:02:52,740
Gerai. Taigi, mes pusiaukelėje.

38
00:02:52,740 --> 00:02:57,990
Tegul toliau mūsų algoritmas įrašant 16 į išrūšiuotų dalis.

39
00:02:59,260 --> 00:03:03,820
Šešiolika yra mažiau nei 42, todėl galime perkelti 42 į dešinę.

40
00:03:05,700 --> 00:03:10,190
Šešiolika taip pat yra mažiau nei 23, tad taip pat pasikeis, kad elementas.

41
00:03:11,790 --> 00:03:20,820
>> Dabar 16 yra didesnis kaip 4. Taigi, atrodo, kad mes norite įterpti tarp 4 ir 23 16.

42
00:03:20,820 --> 00:03:24,620
O juda per išrūšiuotų sąrašo dalį iš dešinės į kairę,

43
00:03:24,620 --> 00:03:29,160
4 yra pirmasis skaičius, mes matėme, kuris yra mažesnis, nei iš

44
00:03:29,160 --> 00:03:31,540
mes bandome įterpti.

45
00:03:31,540 --> 00:03:35,820
Taigi, dabar mes galime įterpti 16 į šį tuščią lizdą,

46
00:03:35,820 --> 00:03:40,520
, atminkite, kad mes sukūrė judančių elementų rūšiavimo dalis virš

47
00:03:40,520 --> 00:03:43,340
kaip mes susidūrėme.

48
00:03:43,340 --> 00:03:47,900
>> Gerai. Dabar, mes turime keturis surūšiuoti elementus ir du nerūšiuotos elementus.

49
00:03:47,900 --> 00:03:51,600
Taigi, galime judėti į išrūšiuotų dalis 8.

50
00:03:51,600 --> 00:03:55,010
Aštuoni yra mažiau nei 42.

51
00:03:55,010 --> 00:03:56,940
Aštuoni yra mažiau nei 23.

52
00:03:56,940 --> 00:04:00,230
Ir 8 yra mažiau nei 16.

53
00:04:00,230 --> 00:04:03,110
Bet 8 yra didesnis kaip 4.

54
00:04:03,110 --> 00:04:07,280
Taigi, mes norėtume įterpti 8 tarp 4 ir 16.

55
00:04:09,070 --> 00:04:13,650
Ir dabar mes tiesiog dar vieną elementą į kairę rūšiuoti - 15.

56
00:04:13,950 --> 00:04:16,589
Penkiolika yra mažesnis kaip 42,

57
00:04:16,589 --> 00:04:19,130
Penkiolika yra mažiau nei 23.

58
00:04:19,130 --> 00:04:21,750
Ir 15 yra mažiau nei 16.

59
00:04:21,750 --> 00:04:24,810
Bet 15 yra didesnis nei 8.

60
00:04:24,810 --> 00:04:27,440
>> Taigi, čia yra, kur mes norime, kad mūsų galutinis įterpti.

61
00:04:28,770 --> 00:04:30,330
Ir baigsime.

62
00:04:30,330 --> 00:04:33,540
Mes neturime daugiau elementų į nerūšiuotų dalis,

63
00:04:33,540 --> 00:04:36,670
ir mūsų surūšiuoti dalis yra teisinga tvarka.

64
00:04:36,670 --> 00:04:40,270
Skaičiai yra rūšiuojami nuo mažiausio iki didžiausio.

65
00:04:40,270 --> 00:04:44,330
Taigi, galime imtis tam tikru pseudocode, kurios apibūdina veiksmus, mes tiesiog atliekamų išvaizdą.

66
00:04:46,760 --> 00:04:51,740
>> 1 eilutėje, mes galime pamatyti, kad mes jums reikia kartoti per kiekvieną elementą sąraše

67
00:04:51,740 --> 00:04:57,060
į nerūšiuotų dalis pirmojo elemento, išskyrus pirmąjį, nes tiesiog tapti

68
00:04:57,060 --> 00:05:00,220
pirmasis elementas išrūšiuotų dalis.

69
00:05:00,220 --> 00:05:06,320
2 ir 3 linijų, mes sekti mūsų dabartinę vietą į nerūšiuotų dalis.

70
00:05:06,320 --> 00:05:10,450
Elementas yra skaičių, šiuo metu juda į išrūšiuotų dalis,

71
00:05:10,450 --> 00:05:15,600
ir j simbolizuoja mūsų indeksą į nerūšiuotų dalis.

72
00:05:15,600 --> 00:05:20,980
>> 4 on-line, mes iteravimu per išrūšiuotų dalį iš dešinės į kairę.

73
00:05:20,980 --> 00:05:26,010
Mes norime sustabdyti iteravimu kartą elemento mūsų dabartinės padėties kairėje

74
00:05:26,010 --> 00:05:30,050
yra mažiau nei elemento mes bandote įterpti.

75
00:05:30,050 --> 00:05:35,600
5 on-line, mes perkelti kiekvieną elementą, mes susiduriame vieną erdvę į dešinę.

76
00:05:35,600 --> 00:05:40,950
Tokiu būdu, mes turime aiškią vietos įterpti į kai randame pirmasis elementas

77
00:05:40,950 --> 00:05:44,080
mažiau nei elemento Mes perkelti.

78
00:05:44,080 --> 00:05:50,800
6 on-line, mes atnaujiname mūsų skaitiklis toliau judėti į kairę per išrūšiuotų dalis.

79
00:05:50,800 --> 00:05:56,860
Galiausiai, 7 on-line, mes įterpiant elementą į išrūšiuotų sąrašo dalį.

80
00:05:56,860 --> 00:06:00,020
>> Mes žinome, kad tai gerai, kad įterpti į poziciją j,

81
00:06:00,020 --> 00:06:05,360
, nes mes jau persikėlė elementas, kuris naudojamas ten būti viena erdvė į dešinę.

82
00:06:05,360 --> 00:06:09,460
Nepamirškite, kad mes žengiame per išrūšiuotų dalį iš dešinės į kairę,

83
00:06:09,460 --> 00:06:13,960
bet mes per nerūšiuotų dalį iš kairės į dešinę.

84
00:06:13,960 --> 00:06:19,090
Gerai. Tegul dabar imtis, kaip ilgai veikia, kad algoritmas paėmė išvaizdą.

85
00:06:19,090 --> 00:06:25,300
Mes pirmą kartą užduoti klausimą, kiek laiko užtruks šis algoritmas paleisti blogiausiu atveju.

86
00:06:25,300 --> 00:06:29,040
Prisiminkite, kad mes atstovaujame šį veikimo laiką su Big O notacijos.

87
00:06:32,530 --> 00:06:38,500
Jei norite surūšiuoti mūsų sąraše, mes turėjome, kad keistumėte į nerūšiuotas dalis elementus,

88
00:06:38,500 --> 00:06:43,430
ir kiekvienas iš šių elementų, gali per visų išrūšiuotų dalis elementų.

89
00:06:43,430 --> 00:06:47,950
Intuityviai, tai skamba, kaip O (n ^ 2) operacijos.

90
00:06:47,950 --> 00:06:51,840
>> Žiūri mūsų pseudocode, mes turime viduje kitos linijos įdėtos kilpa,

91
00:06:51,840 --> 00:06:55,290
kuri iš tikrųjų skamba kaip O (n ^ 2) operacijos.

92
00:06:55,290 --> 00:07:01,590
Tačiau surūšiuoti sąrašo dalis nebuvo visą sąrašą iki pat pabaigos.

93
00:07:01,590 --> 00:07:06,920
Vis dėlto, mes potencialiai gali įterpti naują elementą pačioje pradžioje išrūšiuotų dalis

94
00:07:06,920 --> 00:07:09,320
ant kiekvieno algoritmo iteracija,

95
00:07:09,320 --> 00:07:14,500
o tai reiškia, kad mes turėsime pažvelgti į kiekvieno elemento, šiuo metu išrūšiuotų dalis.

96
00:07:14,500 --> 00:07:20,090
Taigi, tai reiškia, kad potencialiai galėtume padaryti vieną palyginimą antrą elementą,

97
00:07:20,090 --> 00:07:24,660
du trečiojo elemento palyginimų, ir taip toliau.

98
00:07:24,660 --> 00:07:32,480
Taigi, iš viso priemonių yra sveikųjų skaičių suma nuo 1 iki sąrašo ilgio minus 1.

99
00:07:32,480 --> 00:07:35,240
Mes galime atstovauti tai su sumavimo.

100
00:07:41,170 --> 00:07:47,270
>> Mes negalime eiti į summations čia, tačiau paaiškėja, kad tai apibendrinimo yra lygus

101
00:07:47,270 --> 00:07:57,900
n (n - 1) per 2, kuris yra lygiavertis n ^ 2/2 - n / 2.

102
00:07:57,900 --> 00:08:00,800
Kai kalbame apie asimptotinio runtime,

103
00:08:00,800 --> 00:08:05,170
tai n ^ 2 terminas vyksta dominuoti, n terminą.

104
00:08:05,170 --> 00:08:11,430
Taigi, įterpimas rūšiuoti Didelės O (n ^ 2).

105
00:08:11,430 --> 00:08:16,150
Ką daryti, jei nubėgome įterpimo rūšiuoti jau rūšiuotų sąrašą.

106
00:08:16,150 --> 00:08:20,960
Tokiu atveju, mes norime tiesiog sukurti surūšiuoti dalį iš kairės į dešinę.

107
00:08:20,960 --> 00:08:25,050
Taigi, mes tik reikia n žingsnių tvarka.

108
00:08:25,050 --> 00:08:29,740
>> Tai reiškia, kad,, kad įterpimo rūšiuoti geriausiu atveju našumą n,

109
00:08:29,740 --> 00:08:34,130
kurią mes atstovaujame Ω (n).

110
00:08:34,130 --> 00:08:36,190
Ir štai įterpimo rūšiuoti,

111
00:08:36,190 --> 00:08:40,429
tik vienas iš daugelio algoritmų, mes galime naudoti rūšiuoti sąrašą.

112
00:08:40,429 --> 00:08:43,210
My name is Tommy, ir tai yra CS50.

113
00:08:43,210 --> 00:08:44,880
[CS50.TV]

114
00:08:46,110 --> 00:08:49,230
Oh, tu tiesiog negali sustoti, kad kai jis pradeda.

115
00:09:01,620 --> 00:09:04,760
O, mes padarėme, kad - >> Boom!