1
00:00:00,000 --> 00:00:02,290
[Powered by Google Translate] [Iekļaut Sakārtot]

2
00:00:02,290 --> 00:00:04,240
[Tomijs MacWilliam] [Hārvarda]

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

4
00:00:07,290 --> 00:00:13,060
Pieņemsim to apskatīt ievietošanas veida, algoritms ņemot sarakstu numurus un šķirošanu.

5
00:00:13,060 --> 00:00:18,300
Algoritms, atcerieties, ir vienkārši soli pa solim procedūru pabeigšanai uzdevumu.

6
00:00:18,300 --> 00:00:23,640
Pamatideja ievietošanas veida, ir sadalīt savu sarakstu divās daļās,

7
00:00:23,640 --> 00:00:26,580
sakārtoti daļu un nešķirotiem porciju.

8
00:00:26,580 --> 00:00:29,290
>> Katrā posmā no algoritma, numurs tiek pārvietots

9
00:00:29,290 --> 00:00:32,439
no šķirotus daļas uz sakārtotās daļu

10
00:00:32,439 --> 00:00:35,680
līdz beidzot viss saraksts ir sakārtots.

11
00:00:35,680 --> 00:00:43,340
Šeit ir seši nešķirotu numuru saraksts - 23, 42, 4, 16, 8, 15 un.

12
00:00:43,340 --> 00:00:47,680
Tā kā šie skaitļi ir ne visi augošā secībā, viņi nešķirotu.

13
00:00:47,680 --> 00:00:53,890
Kopš mēs neesam sākuši šķirošana vēl, mēs ņemsim vērā visas sešiem elementiem mūsu nešķirotu porciju.

14
00:00:53,890 --> 00:00:59,270
>> Kad mēs sākam šķirošana, mēs nodot šos sakārtoti skaitļus pa kreisi no tiem.

15
00:00:59,270 --> 00:01:03,600
Tātad, sāksim ar 23, pirmais elements mūsu sarakstā.

16
00:01:03,600 --> 00:01:06,930
Mums nav nekādas elementi mūsu sakārtotās daļu vēl,

17
00:01:06,930 --> 00:01:12,460
tāpēc pieņemsim vienkārši uzskatu 23 kā sākums un beigas mūsu šķiroto porciju.

18
00:01:12,460 --> 00:01:16,510
Tagad mūsu sakārtoti daļa ir viens numurs, 23,

19
00:01:16,510 --> 00:01:20,260
un mūsu nešķiroti daļa ir šīs pieci numuri.

20
00:01:20,260 --> 00:01:27,320
Pieņemsim tagad ievietot nākamo numuru mūsu nešķirotu daļu, 42, uz sakārtotās daļu.

21
00:01:27,320 --> 00:01:35,930
>> Lai to izdarītu, mums ir nepieciešams, lai salīdzinātu 42-23 The - vienīgais elements mūsu šķiroto daļā līdz šim.

22
00:01:35,930 --> 00:01:41,980
Četrdesmit divi ir lielāks par 23, lai mēs varētu vienkārši pievienot 42 līdz gada beigām

23
00:01:41,980 --> 00:01:45,420
no sakārtoti daļas sarakstā. Lieliski!

24
00:01:45,420 --> 00:01:51,850
Tagad mūsu sakārtoti daļa ir divas elementi, un mūsu nešķiroti daļa ir četri elementi.

25
00:01:51,850 --> 00:01:57,200
Tātad, pieņemsim tagad pāriet uz 4, nākamais elements nešķirotiem daļu.

26
00:01:57,200 --> 00:02:00,230
Tātad, ja tas būtu ievietots sakārtotās daļu?

27
00:02:00,230 --> 00:02:04,220
>> Atcerieties, mēs vēlamies ievietot šo numuru sakārtoti secībā

28
00:02:04,220 --> 00:02:08,680
tāpēc mūsu sakārtoti daļa paliek pareizi šķirot to visu laiku.

29
00:02:08,680 --> 00:02:14,380
Ja mēs vieta 4 uz tiesībām uz 42, tad mūsu saraksts būs bojātas.

30
00:02:14,380 --> 00:02:18,380
Tātad, pieņemsim turpināt pārvietojas no labās uz kreiso mūsu kārtošanas daļu.

31
00:02:18,380 --> 00:02:23,260
Kā mēs virzāmies, pieņemsim pāriet katru numuru uz leju vietā, lai atbrīvotu vietu jaunajai numuru.

32
00:02:25,440 --> 00:02:31,740
Labi, 4 ir arī mazāk nekā 23, tāpēc mēs nevaram ievietot to šeit, vai nu.

33
00:02:31,740 --> 00:02:34,480
Pāriesim no 23 pareizo vienu vietu.

34
00:02:36,500 --> 00:02:43,120
>> Tas nozīmē, ka mēs gribētu, lai novietotu 4 par pirmo spraugā sakārtotās daļu.

35
00:02:43,120 --> 00:02:46,300
Paziņojums, kā tas sarakstā telpa bija jau tukša,

36
00:02:46,300 --> 00:02:51,120
jo mēs esam pārvietojas sakārtotās elementi noteikti kā mēs esam saskārušās tos.

37
00:02:51,120 --> 00:02:52,740
Labi. Tātad, mēs esam pusceļā tur.

38
00:02:52,740 --> 00:02:57,990
Turpināsim mūsu algoritmu, ievietojot 16 uz sakārtotās daļu.

39
00:02:59,260 --> 00:03:03,820
Sešpadsmit ir mazāks par 42, tāpēc pieņemsim pāriet, 42 pa labi.

40
00:03:05,700 --> 00:03:10,190
Sešpadsmit ir mazāk nekā 23, tāpēc pieņemsim arī novirzīt šo elementu.

41
00:03:11,790 --> 00:03:20,820
>> Tagad, 16 ir lielāks par 4. Tātad, izskatās, ka mēs gribētu, lai ievietotu 16 starp 4 un 23.

42
00:03:20,820 --> 00:03:24,620
Pārvietojoties pa sakārtoti daļu saraksts, no labās uz kreiso,

43
00:03:24,620 --> 00:03:29,160
4 ir pirmais numurs, mēs esam redzējuši, ka ir mazāks nekā skaits

44
00:03:29,160 --> 00:03:31,540
Mēs cenšamies, lai ievietotu.

45
00:03:31,540 --> 00:03:35,820
Tātad, tagad mēs varam ievietot 16 šajā slotā,

46
00:03:35,820 --> 00:03:40,520
kas, atcerieties, mēs esam izveidojuši ar kustīgiem elementiem kārtošanas daļu virs

47
00:03:40,520 --> 00:03:43,340
kā mēs esam konstatējuši tos.

48
00:03:43,340 --> 00:03:47,900
>> Labi. Tagad mums ir četras sakārtotās elementi un divas nešķirotas elementus.

49
00:03:47,900 --> 00:03:51,600
Tātad, pieņemsim pārvietojiet 8 uz sakārtotās daļu.

50
00:03:51,600 --> 00:03:55,010
Astoņi ir mazāk kā 42.

51
00:03:55,010 --> 00:03:56,940
Astoņi ir mazāk nekā 23.

52
00:03:56,940 --> 00:04:00,230
Un 8 ir mazāk nekā 16.

53
00:04:00,230 --> 00:04:03,110
Bet 8 ir lielāks par 4.

54
00:04:03,110 --> 00:04:07,280
Tātad, mēs gribētu, lai ievietotu 8 starp 4 un 16.

55
00:04:09,070 --> 00:04:13,650
Un tagad mums vienkārši ir vēl viens palicis elementu, lai kārtotu - 15.

56
00:04:13,950 --> 00:04:16,589
Piecpadsmit ir mazāk nekā 42,

57
00:04:16,589 --> 00:04:19,130
Piecpadsmit ir mazāk nekā 23.

58
00:04:19,130 --> 00:04:21,750
Un 15 ir mazāk nekā 16.

59
00:04:21,750 --> 00:04:24,810
Bet 15 ir lielāks par 8.

60
00:04:24,810 --> 00:04:27,440
>> Tātad, šeit ir tas, kur mēs vēlamies, lai mūsu gala ievietošanu.

61
00:04:28,770 --> 00:04:30,330
Un mēs esam darīts.

62
00:04:30,330 --> 00:04:33,540
Mums nav vairāk elementus nešķirotu daļu,

63
00:04:33,540 --> 00:04:36,670
un mūsu sakārtoti daļa ir pareizā secībā.

64
00:04:36,670 --> 00:04:40,270
Skaitļi ir pasūtīts no vismazākās līdz lielākajam.

65
00:04:40,270 --> 00:04:44,330
Tātad, pieņemsim apskatīt dažas pseudocode kas apraksta soļus mēs vienkārši veikti.

66
00:04:46,760 --> 00:04:51,740
>> Gada 1 līniju, mēs varam redzēt, ka mums būs nepieciešams atkārtot pār katru elementu sarakstā

67
00:04:51,740 --> 00:04:57,060
izņemot pirmo, jo pirmais elements nešķirotu daļa būs vienkārši kļūs

68
00:04:57,060 --> 00:05:00,220
pirmais elements sakārtotās daļu.

69
00:05:00,220 --> 00:05:06,320
Līnijās 2 un 3, mēs sekotu mūsu pašreizējo vietu nešķirotiem daļu.

70
00:05:06,320 --> 00:05:10,450
Elements atbilst skaitlim mēs šobrīd virzās uz sakārtotās daļu,

71
00:05:10,450 --> 00:05:15,600
un j pārstāv mūsu rādītāju uz nešķirotu daļu.

72
00:05:15,600 --> 00:05:20,980
>> Gada 4 līnijas, mēs atkārtojot caur sakārtotās daļu no labās uz kreiso.

73
00:05:20,980 --> 00:05:26,010
Mēs vēlamies, lai apturētu atkārtojot reizi elementam kreisi no mūsu pašreizējās pozīcijas

74
00:05:26,010 --> 00:05:30,050
ir mazāks nekā elements mēs cenšamies ievietot.

75
00:05:30,050 --> 00:05:35,600
Gada 5 līnijas, mēs novirzot katru elementu mēs saskaramies vienu vietu pa labi.

76
00:05:35,600 --> 00:05:40,950
Tādā veidā, mums būs skaidrs telpu ievietot, kad mēs atrast pirmo elementu

77
00:05:40,950 --> 00:05:44,080
mazāk nekā elements mēs pārvietojas.

78
00:05:44,080 --> 00:05:50,800
Gada 6 līniju, mēs atjaunināt mūsu skaitītāju turpināt virzīties uz kreisi pa sakārtotās daļu.

79
00:05:50,800 --> 00:05:56,860
Visbeidzot, attiecībā uz 7 līnijā, mēs esam ievietojot elementu vērā sakārtoti daļu sarakstu.

80
00:05:56,860 --> 00:06:00,020
>> Mēs zinām, ka tas ir labi, lai ievietotu stāvoklī J,

81
00:06:00,020 --> 00:06:05,360
jo mēs esam jau pārvietots uz elementu, kas izmanto, lai būtu tur viena telpa pa labi.

82
00:06:05,360 --> 00:06:09,460
Atcerieties, mēs esam pārvietojas pa sakārtotās daļu no labās uz kreiso,

83
00:06:09,460 --> 00:06:13,960
bet mēs esam pārvietojas pa nešķirotu daļu no kreisās uz labo pusi.

84
00:06:13,960 --> 00:06:19,090
Labi. Pieņemsim tagad to apskatīt, cik ilgi darbojas, ka algoritms ņēma.

85
00:06:19,090 --> 00:06:25,300
Mēs vispirms uzdot jautājumu, cik ilgi tas veic, lai šis algoritms palaist sliktākajā gadījumā.

86
00:06:25,300 --> 00:06:29,040
Atgādināt, ka mēs pārstāvam šo darbības laiku ar Big O notācija.

87
00:06:32,530 --> 00:06:38,500
Lai sakārtotu mūsu sarakstu, mums bija atkārtot pāri elementus nešķirotu daļu,

88
00:06:38,500 --> 00:06:43,430
un katram no šiem elementiem, potenciāli vairāk nekā visiem šķiroto daļu elementiem.

89
00:06:43,430 --> 00:06:47,950
Intuitīvi, tas izklausās O (n ^ 2) darbību.

90
00:06:47,950 --> 00:06:51,840
>> Skatoties uz mūsu pseudocode, mums ir cilpa ligzdotas citam cilpas,

91
00:06:51,840 --> 00:06:55,290
kas, protams, izklausās O (n ^ 2) darbību.

92
00:06:55,290 --> 00:07:01,590
Tomēr sakārtoti daļa saraksta neietvēra visu sarakstu, līdz pašām beigām.

93
00:07:01,590 --> 00:07:06,920
Tomēr, mēs, iespējams, varētu ievietot jaunu elementu pašā sākumā sakārtotās daļu

94
00:07:06,920 --> 00:07:09,320
par katru atkārtojuma no algoritma,

95
00:07:09,320 --> 00:07:14,500
kas nozīmē, ka mēs ir jāskatās uz katru elementu pašlaik sakārtotās daļu.

96
00:07:14,500 --> 00:07:20,090
Tātad, tas nozīmē, ka mēs, iespējams, varētu iesniegt vienu salīdzinājumu par otro elementu,

97
00:07:20,090 --> 00:07:24,660
divi salīdzinājumi par trešo elementu, un tā tālāk.

98
00:07:24,660 --> 00:07:32,480
Tātad, kopējais skaits soļiem ir summa integers no 1 līdz garumu saraksta mīnus 1.

99
00:07:32,480 --> 00:07:35,240
Mēs varam pārstāvēt šo ar summēšanā.

100
00:07:41,170 --> 00:07:47,270
>> Mēs ne iedziļināties summations šeit, bet izrādās, ka tas sasummēt ir vienāds ar

101
00:07:47,270 --> 00:07:57,900
n (n - 1) vairāk nekā 2, kas ir līdzvērtīgs n ^ 2/2 - N / 2.

102
00:07:57,900 --> 00:08:00,800
Ja runājam par asimptotiskās runtime,

103
00:08:00,800 --> 00:08:05,170
Šī n ^ 2 termins gatavojas dominēt šo n terminu.

104
00:08:05,170 --> 00:08:11,430
Tātad, ievietošanas kārtošanas ir Big O (n ^ 2).

105
00:08:11,430 --> 00:08:16,150
Ko darīt, ja mums bija ievietošanas Šķirot jau šķiroto sarakstā.

106
00:08:16,150 --> 00:08:20,960
Šajā gadījumā mēs vienkārši veidot kārtotas daļu no kreisās uz labo pusi.

107
00:08:20,960 --> 00:08:25,050
Tātad, mēs tikai nepieciešams par kārtību n soļiem.

108
00:08:25,050 --> 00:08:29,740
>> Tas nozīmē, ka ievietošana šķirot ir labākajā gadījumā sniegumu n,

109
00:08:29,740 --> 00:08:34,130
kas mēs pārstāvam ar Ω (n).

110
00:08:34,130 --> 00:08:36,190
Un tas ir tas, lai ievietošanas šķirot,

111
00:08:36,190 --> 00:08:40,429
tikai viens no daudziem algoritmu, mēs varam izmantot, lai sakārtotu sarakstu.

112
00:08:40,429 --> 00:08:43,210
Mans vārds ir Tommy, un tas ir CS50.

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

114
00:08:46,110 --> 00:08:49,230
Ak, jūs vienkārši nevar pārtraukt ka reiz tas sākas.

115
00:09:01,620 --> 00:09:04,760
Ak, mēs to izdarījām, - >> Boom!