1
00:00:00,500 --> 00:00:02,840
[Powered by Google Translate] [BUBBLE SORT]

2
00:00:02,840 --> 00:00:04,560
[JACKSON STEINKAMP Hārvarda universitāte]

3
00:00:04,560 --> 00:00:07,500
[Tas ir CS50. CS50TV]

4
00:00:08,000 --> 00:00:11,730
Burbulis Šķirot ir piemērs šķirošanas algoritmu -

5
00:00:11,730 --> 00:00:14,460
tas ir, procedūra šķirošanas kompleksu elementu pastāvēšanu

6
00:00:14,460 --> 00:00:15,840
augošā vai dilstošā secībā.

7
00:00:15,840 --> 00:00:18,710
Piemēram, ja jūs vēlaties, lai sakārtotu masīvu, kas sastāv no numuriem

8
00:00:18,710 --> 00:00:23,060
[3, 5, 2, 9], pareiza īstenošana Bubble Kārtot varētu atgriezties

9
00:00:23,060 --> 00:00:26,260
sakārtoti masīvs [2, 3, 5, 9] augošā secībā.

10
00:00:26,260 --> 00:00:28,850
Tagad es esmu gatavojas izskaidrot pseudocode kā algoritms darbojas.

11
00:00:28,850 --> 00:00:34,000
>> Pieņemsim, ka mēs esam šķirošanas sarakstu no 5 integers - 3, 2, 9, 6, 5 un.

12
00:00:34,000 --> 00:00:37,650
Algoritms sākas, aplūkojot pirmajiem diviem elementiem, 3 un 2,

13
00:00:37,650 --> 00:00:40,850
un pārbaudīt, ja viņi no rīkojuma attiecībā pret otru.

14
00:00:40,850 --> 00:00:43,150
Tie ir - 3 ir lielāks par 2.

15
00:00:43,150 --> 00:00:45,190
Lai būtu augošā secībā, tiem vajadzētu būt otrādi.

16
00:00:45,190 --> 00:00:46,610
Tātad, mēs mijmaiņas tiem.

17
00:00:46,610 --> 00:00:49,760
Tagad saraksts izskatās šādi: [2, 3, 9, 6, 5].

18
00:00:49,760 --> 00:00:52,450
>> Tālāk, mēs skatāmies uz otro un trešo elementu, 3 un 9.

19
00:00:52,450 --> 00:00:55,770
Viņi pareizā secībā attiecībā pret otru.

20
00:00:55,770 --> 00:00:58,800
Tas ir, 3 ir mazāks par 9 tāpēc algoritms nav mijmaiņas tiem.

21
00:00:58,800 --> 00:01:01,900
Tālāk, mēs skatāmies pēc 9 un 6. Viņi no pasūtījuma.

22
00:01:01,900 --> 00:01:04,260
>> Tātad, mums ir nepieciešams, lai mijmaiņas tiem, jo ​​9 ir lielāks par 6.

23
00:01:04,260 --> 00:01:08,840
Visbeidzot, mēs skatāmies pēdējos divos integers, 9 un 5.

24
00:01:08,840 --> 00:01:10,850
Viņi iziet no ierindas, tāpēc tie ir samainīti.

25
00:01:10,850 --> 00:01:13,360
Pēc pirmās pilnās iziet cauri sarakstam,

26
00:01:13,360 --> 00:01:17,140
tas izskatās šādi: [2, 3, 6, 5, 9].

27
00:01:17,140 --> 00:01:19,690
Nav slikti. Tas ir gandrīz sakārtoti.

28
00:01:19,690 --> 00:01:22,450
Bet mums ir nepieciešams, lai palaistu cauri sarakstam vēlreiz, lai saņemtu to pilnībā sakārtots.

29
00:01:22,450 --> 00:01:29,250
Divi ir mazāks par 3, tāpēc mums nav mijmaiņas tiem.

30
00:01:29,250 --> 00:01:31,700
>> Trīs ir mazāks par 6, tāpēc mums nav mijmaiņas tiem.

31
00:01:31,700 --> 00:01:35,500
Seši ir lielāks par 5. Mēs nomainīju.

32
00:01:35,500 --> 00:01:38,460
Seši ir mazāks par 9. Mums nav swap.

33
00:01:38,460 --> 00:01:42,170
Pēc otrā iziet cauri, tas izskatās šādi: [2, 3, 5, 6, 9]. Perfekta.

34
00:01:42,170 --> 00:01:44,680
Tagad, pieņemsim uzrakstiet to pseudocode.

35
00:01:44,680 --> 00:01:48,450
Būtībā, katram elementam sarakstā, mums ir jāskatās uz to

36
00:01:48,450 --> 00:01:50,060
un elementa tieši tās tiesībām.

37
00:01:50,060 --> 00:01:53,420
Ja tie nav pareizā secībā attiecībā pret otru - tas ir, ja elements pa kreisi

38
00:01:53,420 --> 00:01:56,810
ir lielāks nekā tas, pa labi - mums vajadzētu mijmaiņas diviem elementiem.

39
00:01:56,810 --> 00:02:01,270
>> Mēs to darām, lai katru elementu sarakstu, un mēs esam padarījuši vienu iet cauri.

40
00:02:01,270 --> 00:02:05,160
Tagad mums vienkārši ir jādara transmisija pietiekami laikus, lai nodrošinātu sarakstu

41
00:02:05,160 --> 00:02:06,480
ir pilnībā, pareizi sakārtots.

42
00:02:06,480 --> 00:02:08,889
Bet cik reizes mums ir iziet cauri sarakstam, lai

43
00:02:08,889 --> 00:02:10,400
garantēt, ka mēs esam darījuši?

44
00:02:10,400 --> 00:02:14,730
Nu, sliktākajā gadījumā ir, ja mums ir pilnīgi atpakaļsaderību sarakstu.

45
00:02:14,730 --> 00:02:17,840
Tad tas aizņem vairākus iet pievadiem vienāds skaits

46
00:02:17,840 --> 00:02:19,730
elementu n-1.

47
00:02:19,730 --> 00:02:24,720
Ja tas nav jēgas intuitīvi, domā par vienkāršu lietu - sarakstu [2, 1].

48
00:02:24,720 --> 00:02:28,430
>> Tas ir gatavojas veikt vienu transmisija sakārtot pareizi.

49
00:02:28,430 --> 00:02:33,060
[3, 2, 1] - Sliktākajā gadījumā ir tas, ka ar 3 elementiem sakārtoti atpakaļ,

50
00:02:33,060 --> 00:02:34,830
tas gatavojas veikt 2 atkārtojumiem kārtošanai.

51
00:02:34,830 --> 00:02:37,980
Pēc viena atkārtojuma, tā [2, 1, 3].

52
00:02:37,980 --> 00:02:39,550
Otrais ražas sakārtoti masīvs [1, 2, 3].

53
00:02:39,550 --> 00:02:43,350
Tātad, jūs zināt, jums nekad nav iet caur masīvs, kopumā

54
00:02:43,350 --> 00:02:46,790
vairāk nekā n-1 reizes, kur n ir elementu skaits masīvā.

55
00:02:47,090 --> 00:02:50,470
To sauc burbulis Sakārtot jo lielākie elementi mēdz "burbulis-up"

56
00:02:50,470 --> 00:02:51,950
uz labo diezgan ātri.

57
00:02:51,950 --> 00:02:53,980
Patiesībā, šis algoritms ir ļoti interesants uzvedību.

58
00:02:53,980 --> 00:02:57,410
>> Pēc m atkārtojumiem cauri visai masīvs,

59
00:02:57,410 --> 00:02:59,000
rightmost m elementi ir garantēta

60
00:02:59,000 --> 00:03:01,000
sakārtoti savā pareizajā vietā.

61
00:03:01,000 --> 00:03:02,280
Ja jūs vēlaties redzēt šo par sevi,

62
00:03:02,280 --> 00:03:05,500
mēs varam mēģināt to par pilnīgi atpakaļsaderību sarakstā [9, 6, 5, 3, 2].

63
00:03:05,500 --> 00:03:08,220
Pēc viena iet caur visam sarakstam,

64
00:03:08,220 --> 00:03:09,220
[Skaņu rakstīšanas]

65
00:03:09,220 --> 00:03:18,790
[6, 9, 5, 3, 2], [6, 5, 9, 3, 2], [6, 5, 3, 9, 2], [6, 5, 3, 2, 9]

66
00:03:18,790 --> 00:03:21,250
rightmost elements 9 ir tās pienācīgu vietu.

67
00:03:21,250 --> 00:03:24,760
Pēc otrā transmisija, 6 būs "burbuļo-up" uz

68
00:03:24,760 --> 00:03:26,220
2. rightmost vieta.

69
00:03:26,220 --> 00:03:28,840
Divi elementi pa labi - 6 un 9 - būs savās pareizajās vietās

70
00:03:28,840 --> 00:03:30,580
Pēc pirmo divu pass pievadiem.

71
00:03:30,580 --> 00:03:32,590
>> Tātad, kā mēs varam izmantot, lai optimizētu šo algoritmu?

72
00:03:32,590 --> 00:03:34,850
Nu, pēc viena atkārtojuma caur masīvs

73
00:03:34,850 --> 00:03:37,690
mums nav tiešām ir nepieciešams, lai pārbaudītu rightmost elements

74
00:03:37,690 --> 00:03:39,200
jo mēs zinām, tas ir sakārtoti.

75
00:03:39,200 --> 00:03:43,050
Pēc diviem atkārtojumiem, mēs zinām droši rightmost divi elementi ir savā vietā.

76
00:03:43,050 --> 00:03:48,260
Tātad, kopumā, pēc k iterācijām caur pilnu klāstu,

77
00:03:48,260 --> 00:03:51,550
Pārbaudot pēdējo k elementiem ir lieks, jo mēs zinām,

78
00:03:51,550 --> 00:03:52,360
viņi ir pareizajā vietā jau.

79
00:03:52,360 --> 00:03:54,870
>> Tātad, ja jūs esat šķirošanu masīvs n elementiem,

80
00:03:54,870 --> 00:03:57,870
gada pirmā atkārtojuma - you'll ir kārtot visus elementus - pirmā N-0.

81
00:03:57,870 --> 00:04:04,170
Gada otrajam atkārtojumam, jums ir apskatīt visus elementus, bet pēdējo -

82
00:04:04,170 --> 00:04:07,090
pirmais N-1.

83
00:04:07,090 --> 00:04:10,520
Vēl optimizācija varētu pārbaudīt, ja saraksts jau ir sakārtots

84
00:04:10,520 --> 00:04:11,710
Pēc katras iterācijas.

85
00:04:11,710 --> 00:04:13,900
Ja tas jau ir sakārtoti, mums nav nepieciešams veikt vairāk iterācijas

86
00:04:13,900 --> 00:04:15,310
pa sarakstu.

87
00:04:15,310 --> 00:04:16,220
Kā mēs varam darīt?

88
00:04:16,220 --> 00:04:19,360
Nu, ja mums nav nekādas mijmaiņa uz transmisija saraksta,

89
00:04:19,360 --> 00:04:22,350
tas ir skaidrs, ka saraksts jau tika sakārtots, jo mums nav mijmaiņas neko.

90
00:04:22,350 --> 00:04:24,160
Tāpēc mēs noteikti nav šķirot vēlreiz.

91
00:04:24,160 --> 00:04:27,960
>> Varbūt jūs varētu inicializēt karoga mainīgo sauc "nav sakārtoti", lai

92
00:04:27,960 --> 00:04:30,990
nepatiess un mainīt to, ja jums ir, lai mijmaiņas kādi elementus

93
00:04:30,990 --> 00:04:32,290
viena atkārtojuma caur masīvs.

94
00:04:32,290 --> 00:04:35,350
Vai līdzīgi, lai skaitītājs cik mijmaiņas jūs veicat

95
00:04:35,350 --> 00:04:37,040
jebkurā konkrētā atkārtojuma.

96
00:04:37,040 --> 00:04:40,040
Pēc atkārtošanu, ja Jums nav mijmaiņas jebkuru no elementiem,

97
00:04:40,040 --> 00:04:41,780
Jūs zināt saraksts jau ir sakārtots, un jūs darīts.

98
00:04:41,780 --> 00:04:44,090
Burbulis Kārtot, tāpat kā citi kārtošanas algoritmi, var būt

99
00:04:44,090 --> 00:04:46,960
tweaked strādāt visiem elementiem, kuriem ir pasūtīšanas metodi.

100
00:04:46,960 --> 00:04:50,610
>> Tas ir, ņemot vērā divi elementi jums ir veids, kā pateikt, ja pirmais

101
00:04:50,610 --> 00:04:53,770
ir lielāks nekā, vienāda vai mazāka nekā otrajā.

102
00:04:53,770 --> 00:04:56,870
Piemēram, jūs varētu kārtot alfabēta burti, sakot

103
00:04:56,870 --> 00:05:00,520
ka <b, b <c, utt

104
00:05:00,520 --> 00:05:03,830
Vai jūs varētu sakārtot nedēļas dienas, kurās ir svētdiena mazāk nekā pirmdiena

105
00:05:03,830 --> 00:05:05,110
kas ir mazāk nekā otrdien.

106
00:05:05,110 --> 00:05:09,630
>> Burbulis Šķirot nekādā ziņā ļoti efektīvu vai ātri šķirošanas algoritmu.

107
00:05:09,630 --> 00:05:12,370
Vissliktākajā gadījumā izpildlaika ir Big O n ²

108
00:05:12,370 --> 00:05:14,810
jo jums ir, lai n iterācijas izmantojot sarakstu

109
00:05:14,810 --> 00:05:18,430
pārbaudot visus n elementus katru transmisija, nxn = n ².

110
00:05:18,430 --> 00:05:22,730
Tas palaist laiks nozīmē, ka par vairākiem elementiem jūs šķirošana pieaugumu,

111
00:05:22,730 --> 00:05:24,330
darbības laiks palielinās quadratically.

112
00:05:24,330 --> 00:05:27,330
>> Bet, ja efektivitāte nav lielas bažas par savu programmu

113
00:05:27,330 --> 00:05:29,550
vai, ja jūs tikai šķirošanas nelielu skaitu elementu,

114
00:05:29,550 --> 00:05:31,660
Jūs varētu atrast burbulis Sakārtot noderīgi, jo

115
00:05:31,660 --> 00:05:33,360
tas ir viens no vienkāršākajiem šķirošanas algoritmu, lai saprastu

116
00:05:33,360 --> 00:05:34,250
un kods.

117
00:05:34,250 --> 00:05:37,270
Tas ir arī lielisks veids, kā iegūt pieredzi ar tulkošanu teorētisks

118
00:05:37,270 --> 00:05:40,220
Algoritms vērā faktisko funkcionējošu kodu.

119
00:05:40,220 --> 00:05:43,000
Nu, tas ir burbulis Sakārtot jums. Paldies par skatoties.

120
00:05:43,000 --> 00:05:44,000
CS50.TV