1
00:00:00,000 --> 00:00:03,360
 [SKAN MŪZIKA]

2
00:00:04,522 --> 00:00:06,626
DAGS LOIDS: Tātad burbuļa kārtošana
ir algoritms, ko varat izmantot 

3
00:00:06,626 --> 00:00:08,730
elementu kopas kārtošanai. 

4
00:00:08,730 --> 00:00:10,850
Apskatīsim, kā tas darbojas.

5
00:00:10,850 --> 00:00:13,240
 Tātad burbuļa kārtošanas
pamatideja ir šāda.

6
00:00:13,240 --> 00:00:16,790
Augstākās vērtības elementus mēs
parasti vēlamies pārvietot pa labi, 

7
00:00:16,790 --> 00:00:20,340
zemākās vērtības elementus – pa
kreisi, kas būtu sagaidāms. 

8
00:00:20,340 --> 00:00:24,970
Mēs vēlamies, lai zemākās lietas
būtu sākumā, bet augstākās - beigās.

9
00:00:24,970 --> 00:00:26,130
 Kā mēs to darām?

10
00:00:26,130 --> 00:00:28,225
Pseidokoda kodā, mēs varētu teikt,
iestatīsim mijmaiņas skaitītāju uz 

11
00:00:28,225 --> 00:00:30,320
vērtību, kas nav nulle. 

12
00:00:30,320 --> 00:00:32,570
Pēc brīža mēs redzēsim, kāpēc mēs
to darām.

13
00:00:32,570 --> 00:00:36,240
Un tad mēs atkārtojam šo procesu,
līdz mijmaiņas skaitītājs ir 0 vai 

14
00:00:36,240 --> 00:00:39,910
līdz mēs vispār neveicam mijmaiņas
darbības. 

15
00:00:39,910 --> 00:00:43,170
 Atiestatiet mijmaiņas skaitītāju
uz 0, ja tas vēl nav 0.

16
00:00:43,170 --> 00:00:46,420
Pēc tam apskatiet katru blakus
esošo elementu pāri.

17
00:00:46,420 --> 00:00:49,020
Ja šie divi elementi nav kārtībā,
samainiet tos vietām un 

18
00:00:49,020 --> 00:00:51,620
pievienojiet 1 mijmaiņas
skaitītājam. 

19
00:00:51,620 --> 00:00:54,700
Ja domājat par to, pirms to
vizualizējat, ievērojiet, ka tas 

20
00:00:54,700 --> 00:00:57,780
pārvietos zemākās vērtības
elementus pa kreisi un augstākās vērtības 

21
00:00:57,780 --> 00:01:00,860
elementus pa labi, efektīvi darot
to, ko mēs vēlamies, proti, 

22
00:01:00,860 --> 00:01:03,940
pārvietot šīs elementu grupas šādā
veidā. 

23
00:01:03,940 --> 00:01:07,222
Vizualizēsim, kā tas varētu
izskatīties, izmantojot to masīvu, kurus 

24
00:01:07,222 --> 00:01:10,504
izmantojām, lai pārbaudītu šos
algoritmus. 

25
00:01:10,504 --> 00:01:12,672
Šeit atkal ir nesakārtots masīvs,
uz ko norāda visi elementi sarkanā 

26
00:01:12,672 --> 00:01:14,840
krāsā. 

27
00:01:14,840 --> 00:01:17,970
Un es iestatīju savu mijmaiņas
skaitītāju uz vērtību, kas nav nulle.

28
00:01:17,970 --> 00:01:20,610
Es patvaļīgi izvēlējos negatīvo 1 —
tā nav 0.

29
00:01:20,610 --> 00:01:23,840
Mēs vēlamies atkārtot šo procesu,
līdz mijmaiņas skaitītājs ir 0.

30
00:01:23,840 --> 00:01:26,620
Tāpēc es iestatīju mijmaiņas
skaitītāju uz kādu vērtību, kas nav 

31
00:01:26,620 --> 00:01:29,400
nulle, jo pretējā gadījumā
mijmaiņas skaitītājs būtu 0. 

32
00:01:29,400 --> 00:01:31,610
Mēs pat nesāktu algoritma procesu.

33
00:01:31,610 --> 00:01:34,578
Tātad atkal ir šādas darbības:
atiestatiet mijmaiņas skaitītāju uz 0, 

34
00:01:34,578 --> 00:01:37,546
pēc tam apskatiet katru blakus
esošo pāri un, ja tie nav kārtībā, 

35
00:01:37,546 --> 00:01:40,514
samainiet tos vietām un
pievienojiet mijmaiņas skaitītājam 1. 

36
00:01:40,514 --> 00:01:41,680
Tātad, sāksim šo procesu.

37
00:01:41,680 --> 00:01:44,170
Tāpēc vispirms mēs iestatām
mijmaiņas skaitītāju uz 0 un pēc tam 

38
00:01:44,170 --> 00:01:46,660
sākam aplūkot katru blakus esošo
pāri. 

39
00:01:46,660 --> 00:01:49,140
 Tā mēs vispirms sākam aplūkot 5 un
2.

40
00:01:49,140 --> 00:01:52,410
Mēs redzam, ka tie nav kārtībā,
tāpēc mēs tos samainām vietām.

41
00:01:52,410 --> 00:01:53,830
Un mēs pievienojam 1 mijmaiņas
skaitītājam.

42
00:01:53,830 --> 00:01:57,860
Tātad tagad mūsu mijmaiņas
skaitītājs ir 1, bet 2 un 5 ir pārslēgti.

43
00:01:57,860 --> 00:01:59,370
Tagad mēs atkārtojam procesu
vēlreiz.

44
00:01:59,370 --> 00:02:03,165
Mēs skatāmies uz nākamo pāri
blakus — 5 un 1 — tie arī nav kārtībā, 

45
00:02:03,165 --> 00:02:06,960
tāpēc mēs tos samainām vietām un
pievienojam 1 mijmaiņas skaitītājam. 

46
00:02:06,960 --> 00:02:08,900
Tad mēs skatāmies uz 5 un 3.

47
00:02:08,900 --> 00:02:11,365
Tie nav kārtībā, tāpēc mēs tos
samainām vietām un pievienojam 1 

48
00:02:11,365 --> 00:02:13,830
maiņas skaitītājam. 

49
00:02:13,830 --> 00:02:15,550
Tad mēs skatāmies uz 5 un 6.

50
00:02:15,550 --> 00:02:18,630
Tie ir kārtībā, tāpēc mums šoreiz
nekas nav jāmaina.

51
00:02:18,630 --> 00:02:20,250
Tad mēs skatāmies uz 6 un 4.

52
00:02:20,250 --> 00:02:22,585
Tie arī nav kārtībā, tāpēc mēs tos
samainām un pievienojam 1 maiņas 

53
00:02:22,585 --> 00:02:24,920
skaitītājam. 

54
00:02:24,920 --> 00:02:26,230
 Tagad ievērojiet, kas ir noticis.

55
00:02:26,230 --> 00:02:29,514
Mēs esam pārvietojuši 6 līdz
beigām.

56
00:02:29,514 --> 00:02:32,889
Tātad atlases kārtošanā, ja esat
redzējuši to videoklipu, mēs 

57
00:02:32,889 --> 00:02:36,264
pārvietojām mazākos elementus,
veidojot sakārtoto masīvu precīzi no 

58
00:02:36,264 --> 00:02:39,640
kreisās puses uz labo, no mazākā uz
lielāko. 

59
00:02:39,640 --> 00:02:42,793
Burbuļa kārtošanas gadījumā, ja mēs
sekojam šim konkrētajam 

60
00:02:42,793 --> 00:02:45,946
algoritmam, mēs faktiski veidojam
sakārtoto masīvu no labās puses uz 

61
00:02:45,946 --> 00:02:49,100
kreiso, no lielākā uz mazāko. 

62
00:02:49,100 --> 00:02:53,840
Mēs esam faktiski uzburbulējuši 6,
lielāko vērtību, līdz pat beigām.

63
00:02:53,840 --> 00:02:56,320
Un tāpēc mēs tagad varam paziņot,
ka tas ir sakārtots, un turpmākajās 

64
00:02:56,320 --> 00:02:58,800
iterācijās — vēlreiz izejot cauri
masīvam — mums vairs nav jāņem 

65
00:02:58,800 --> 00:03:01,280
vērā 6. 

66
00:03:01,280 --> 00:03:03,789
Mums ir jāņem vērā tikai
nesakārtoti elementi, kad skatāmies uz 

67
00:03:03,789 --> 00:03:06,299
blakus esošajiem pāriem. 

68
00:03:06,299 --> 00:03:08,340
Tātad mēs esam pabeiguši vienu
piegājienu ar burbuļa kārtošanu.

69
00:03:08,340 --> 00:03:10,140
Tagad mēs atgriežamies pie
jautājuma - atkārtojiet, līdz mijmaiņas 

70
00:03:10,140 --> 00:03:11,941
skaitītājs ir 0. 

71
00:03:11,941 --> 00:03:13,675
Nu, mijmaiņas skaitītājs ir 4,
tāpēc mēs turpināsim atkārtot šo 

72
00:03:13,675 --> 00:03:15,410
procesu vēlreiz. 

73
00:03:15,410 --> 00:03:17,295
Mēs atiestatīsim mijmaiņas
skaitītāju uz 0 un apskatīsim katru blakus 

74
00:03:17,295 --> 00:03:19,180
esošo pāri. 

75
00:03:19,180 --> 00:03:21,400
Tāpēc mēs sākam ar 2 un 1 — tie nav
kārtībā, tāpēc mēs tos samainām 

76
00:03:21,400 --> 00:03:23,620
vietām un pievienojam mijmaiņas
skaitītājam 1. 

77
00:03:23,620 --> 00:03:25,490
2 un 3, tie ir kārtībā.

78
00:03:25,490 --> 00:03:27,060
Mums nekas nav jādara.

79
00:03:27,060 --> 00:03:28,420
3 un 5 ir kārtībā.

80
00:03:28,420 --> 00:03:30,150
Mums tur nekas nav jādara.

81
00:03:30,150 --> 00:03:32,640
5 un 4, tie nav kārtībā, tāpēc mums
tie ir jāsamaina vietām un 

82
00:03:32,640 --> 00:03:35,130
jāpievieno 1 mijmaiņas skaitītājam.


83
00:03:35,130 --> 00:03:38,025
Un tagad mēs esam pārvietojuši 5,
nākamo lielāko elementu, uz 

84
00:03:38,025 --> 00:03:40,920
nesakārtotas daļas beigām. 

85
00:03:40,920 --> 00:03:44,360
Tātad tagad varam saukt šo
sakārtotu daļu.

86
00:03:44,360 --> 00:03:47,245
Tagad jūs skatāties uz ekrānu un,
iespējams, tāpat kā es varu teikt, 

87
00:03:47,245 --> 00:03:50,130
sakāt, ka masīvs šobrīd ir
sakārtots. 

88
00:03:50,130 --> 00:03:51,820
Bet mēs to vēl nevaram pierādīt.

89
00:03:51,820 --> 00:03:54,359
Mums nav garantijas, ka tas ir
sakārtots.

90
00:03:54,359 --> 00:03:56,900
Un te spēlē ienāk mijmaiņas
skaitītājs.

91
00:03:56,900 --> 00:03:59,060
 Tātad mēs esam pabeiguši
piegājienu.

92
00:03:59,060 --> 00:04:00,357
Mijmaiņas skaitītājs ir 2.

93
00:04:00,357 --> 00:04:02,323
Tāpēc mēs atkārtosim šo procesu
vēlreiz. Atkārtojiet, līdz mijmaiņas 

94
00:04:02,323 --> 00:04:04,290
skaitītājs ir 0. 

95
00:04:04,290 --> 00:04:05,550
Atiestatiet mijmaiņas skaitītāju uz
0.

96
00:04:05,550 --> 00:04:06,820
Tā mēs to atiestatām.

97
00:04:06,820 --> 00:04:09,810
 Tagad apskatiet katru blakus esošo
pāri.

98
00:04:09,810 --> 00:04:11,880
Tas ir kārtībā, 1 un 2.

99
00:04:11,880 --> 00:04:13,590
2 un 3 ir kārtībā.

100
00:04:13,590 --> 00:04:15,010
3 un 4 ir kārtībā.

101
00:04:15,010 --> 00:04:18,770
Tāpēc šajā brīdī ievērojiet, ka
esam pabeiguši visu blakus esošo pāru 

102
00:04:18,770 --> 00:04:22,530
apskati, taču mijmaiņas skaitītājs
joprojām ir 0. 

103
00:04:22,530 --> 00:04:25,435
Ja mums nav jāmaina nekādi
elementi, tad saskaņā ar šo procesu tiem 

104
00:04:25,435 --> 00:04:28,340
ir jābūt kārtībā. 

105
00:04:28,340 --> 00:04:31,613
Un tad kārtošanas efektivitāte ir
tas, kas mums, datorzinātniekiem, 

106
00:04:31,613 --> 00:04:34,886
tik patīk. Tas, ka tagad varam
paziņot, ka viss masīvs ir sakārtots, 

107
00:04:34,886 --> 00:04:38,160
jo mums nebija jāmaina vietām
elementi. 

108
00:04:38,160 --> 00:04:40,380
Tas ir diezgan jauki.

109
00:04:40,380 --> 00:04:43,260
 Tātad, kāds ir sliktākais
scenārijs ar burbuļa kārtošanu?

110
00:04:43,260 --> 00:04:47,520
Sliktākajā gadījumā masīvs ir
pilnīgi apgrieztā secībā, un tāpēc mums 

111
00:04:47,520 --> 00:04:51,780
ir jāburbulē katrs lielais elements
masīvā. 

112
00:04:51,780 --> 00:04:54,415
Un mums faktiski arī ir
jāaizburbulē atpakaļ visi mazie elementi 

113
00:04:54,415 --> 00:04:57,050
masīvā. 

114
00:04:57,050 --> 00:04:59,500
Tātad katram no n elementiem ir
jāpārvietojas pāri visiem pārējiem n 

115
00:04:59,500 --> 00:05:01,950
elementiem. 

116
00:05:01,950 --> 00:05:04,102
Tātad tas ir sliktākais scenārijs.

117
00:05:04,102 --> 00:05:05,991
Savukārt, labākajā gadījumā tas
nedaudz atšķiras no atlases 

118
00:05:05,991 --> 00:05:07,880
kārtošanas. 

119
00:05:07,880 --> 00:05:10,040
Masīvs jau ir sakārtots, kad mēs
ieejam.

120
00:05:10,040 --> 00:05:12,550
Mums nav jāveic nekādas mijmaiņas
pirmajā piegājienā.

121
00:05:12,550 --> 00:05:14,940
Tātad mums, iespējams, būs jāaplūko
mazāk elementu, vai ne?

122
00:05:14,940 --> 00:05:18,580
Mums šis process nav jāatkārto
vairākas reizes.

123
00:05:18,580 --> 00:05:19,540
 Tātad, ko tas nozīmē?

124
00:05:19,540 --> 00:05:22,435
Tad, kāds būtu sliktākais scenārijs
burbuļa kārtošanai un kāds būtu 

125
00:05:22,435 --> 00:05:25,330
labākais burbuļa kārtošanas
scenārijs? 

126
00:05:25,330 --> 00:05:27,770
Vai jūs to uzminējāt?

127
00:05:27,770 --> 00:05:32,420
Sliktākajā gadījumā jums ir
jāatkārto visi n elementi n reizes.

128
00:05:32,420 --> 00:05:34,220
Tātad, sliktākais gadījums ir n
kvadrātā.

129
00:05:34,220 --> 00:05:36,400
Ja masīvs ir sakārtots nevainojami,
katrs elements ir jāaplūko tikai 

130
00:05:36,400 --> 00:05:38,580
vienu reizi. 

131
00:05:38,580 --> 00:05:40,625
Un, ja mijmaiņas skaitītājs
joprojām ir 0, varat teikt, ka šis masīvs 

132
00:05:40,625 --> 00:05:42,670
ir sakārtots. 

133
00:05:42,670 --> 00:05:45,950
Tātad labākajā gadījumā tas
patiesībā ir labāks par atlases 

134
00:05:45,950 --> 00:05:49,230
kārtošanu — tas ir n omega. 

135
00:05:49,230 --> 00:05:50,270
 Es esmu Dags Loids.

136
00:05:50,270 --> 00:05:52,140
Šis ir CS50.