1
00:00:00,000 --> 00:00:03,360
>> [მუსიკის დაკვრა]

2
00:00:03,360 --> 00:00:04,522

3
00:00:04,522 --> 00:00:06,730
DOUG LLOYD: ყველა უფლება,
bubble sort არის ალგორითმი

4
00:00:06,730 --> 00:00:08,730
თქვენ შეგიძლიათ გამოიყენოთ დასალაგებლად კომპლექტი ელემენტები.

5
00:00:08,730 --> 00:00:10,850
მოდით შევხედოთ, თუ როგორ მუშაობს.

6
00:00:10,850 --> 00:00:13,240
>> ასე რომ, ძირითადი იდეა უკან
bubble sort არის ეს.

7
00:00:13,240 --> 00:00:17,340
ჩვენ ზოგადად მინდა გადატანა უმაღლესი
ღირებული ელემენტები ზოგადად უფლება,

8
00:00:17,340 --> 00:00:20,340
და ქვედა ღირებული ელემენტები ზოგადად
მარცხნივ, როგორც ჩვენ მოელოდა.

9
00:00:20,340 --> 00:00:23,256
ჩვენ გვინდა, რომ ქვედა რამ უნდა იყოს
დასაწყისში და უმაღლესი რამ

10
00:00:23,256 --> 00:00:24,970
უნდა იყოს ბოლოს.

11
00:00:24,970 --> 00:00:26,130
>> როგორ გავაკეთოთ ეს?

12
00:00:26,130 --> 00:00:28,040
კარგად pseudocode კოდი,
შეიძლება ითქვას, რომ, მოდით,

13
00:00:28,040 --> 00:00:30,320
მითითებული swap counter არასამთავრობო ნულოვანი ღირებულება.

14
00:00:30,320 --> 00:00:32,570
ჩვენ დავინახავთ, რატომ ვაკეთებთ, რომ მეორე.

15
00:00:32,570 --> 00:00:36,090
და შემდეგ ჩვენ ვიმეორებ შემდეგი
პროცესი სანამ swap counter არის 0,

16
00:00:36,090 --> 00:00:39,910
ან სანამ ჩვენ არ გაცვლებს ყველა.

17
00:00:39,910 --> 00:00:43,170
>> რესეტი swap წინააღმდეგობაში
0 თუ ეს არ არის უკვე 0.

18
00:00:43,170 --> 00:00:46,420
შემდეგ შეხედეთ ყველა
მიმდებარე წყვილი ელემენტებს.

19
00:00:46,420 --> 00:00:49,550
თუ ამ ორი ელემენტები
არ არის იმისათვის, რომ სვოპ მათ,

20
00:00:49,550 --> 00:00:51,620
და დაამატოთ 1 სვოპ counter.

21
00:00:51,620 --> 00:00:53,870
თუ თქვენ ფიქრი
ეს სანამ ვიზუალურად იგი,

22
00:00:53,870 --> 00:00:57,471
შეამჩნია, რომ ეს გადავა ქვედა
ღირებული ელემენტები მარცხენა

23
00:00:57,471 --> 00:01:00,720
და უმაღლესი ღირებული ელემენტები მარჯვნივ,
ეფექტურად აკეთებს იმას, რაც ჩვენ გვინდა, რომ,

24
00:01:00,720 --> 00:01:03,940
რომელიც გადავა იმ ჯგუფების
ელემენტების, რომ გზა.

25
00:01:03,940 --> 00:01:07,035
მოდით ვიზუალურად როგორ ეს
შეიძლება გამოიყურებოდეს გამოყენებით ჩვენი მასივი

26
00:01:07,035 --> 00:01:10,504
რომ ჩვენ შეამოწმოთ
აღნიშნული ალგორითმები.

27
00:01:10,504 --> 00:01:13,420
ჩვენ გვაქვს დაუხარისხებელი მასივი აქ კიდევ ერთხელ,
მიერ მითითებულ ყველა ელემენტები

28
00:01:13,420 --> 00:01:14,840
მიმდინარეობს წითელი.

29
00:01:14,840 --> 00:01:17,970
და მე ჩემს swap counter
რომ არ უდრის ნულს ღირებულება.

30
00:01:17,970 --> 00:01:20,610
თვითნებურად აირჩია
უარყოფითი 1-- ეს არ არის 0.

31
00:01:20,610 --> 00:01:23,840
შეგახსენებთ, რომ ეს პროცესი
სანამ swap counter არის 0.

32
00:01:23,840 --> 00:01:26,540
ამიტომ, მე ჩემს swap
counter ზოგიერთი არასამთავრობო ნულოვანი ღირებულება,

33
00:01:26,540 --> 00:01:29,400
რადგან, წინააღმდეგ შემთხვევაში
swap counter იქნება 0.

34
00:01:29,400 --> 00:01:31,610
ჩვენ კი არ დაიწყოს
პროცესი ალგორითმი.

35
00:01:31,610 --> 00:01:33,610
ასე რომ კიდევ ერთხელ, ნაბიჯები are--
აღადგინოთ swap counter

36
00:01:33,610 --> 00:01:37,900
0, მაშინ შევხედოთ ყველა მიმდებარე
წყვილი, და თუ ისინი მწყობრიდან გამოვიდა,

37
00:01:37,900 --> 00:01:40,514
სვოპ მათ, და დაამატოთ 1
რომ swap counter.

38
00:01:40,514 --> 00:01:41,680
ასე რომ დავიწყოთ ამ პროცესში.

39
00:01:41,680 --> 00:01:44,430
ასე რომ, პირველი, რასაც ვაკეთებთ არის
ჩვენ მითითებული swap counter 0,

40
00:01:44,430 --> 00:01:46,660
და შემდეგ დავიწყებთ
ყოველ მიმდებარე წყვილი.

41
00:01:46,660 --> 00:01:49,140
>> ასე რომ, ჩვენ დავიწყოთ ეძებს 5 და 2.

42
00:01:49,140 --> 00:01:52,410
ჩვენ ვხედავთ, რომ ისინი გარეთ
შეკვეთა და ამიტომ ჩვენ სვოპ მათ.

43
00:01:52,410 --> 00:01:53,830
და დავუმატებთ 1 სვოპ counter.

44
00:01:53,830 --> 00:01:57,860
ასე რომ, ახლა ჩვენი swap counter 1,
და 2 და 5 უკვე შეცვალა.

45
00:01:57,860 --> 00:01:59,370
ახლა ჩვენ ვიმეორებთ პროცესს კიდევ ერთხელ.

46
00:01:59,370 --> 00:02:03,540
>> ჩვენ შევხედოთ შემდეგი მიმდებარე წყვილი,
5 და 1 ისინი ასევე მწყობრიდან,

47
00:02:03,540 --> 00:02:06,960
ასე რომ, ჩვენ სვოპ მათ და დაამატოთ
1-swap counter.

48
00:02:06,960 --> 00:02:08,900
მაშინ შევხედავთ 5 და 3.

49
00:02:08,900 --> 00:02:13,830
ისინი მწყობრიდან, ამიტომ ჩვენ სვოპ
მათ და დავუმატებთ 1 სვოპ counter.

50
00:02:13,830 --> 00:02:15,550
მაშინ შევხედავთ 5 და 6.

51
00:02:15,550 --> 00:02:18,630
ისინი, რათა, ამიტომ ჩვენ არ რეალურად
უნდა სვოპ არაფერი ამ დროს.

52
00:02:18,630 --> 00:02:20,250
მაშინ შევხედავთ 6 და 4.

53
00:02:20,250 --> 00:02:24,920
ისინი ასევე მწყობრიდან, ამიტომ ჩვენ სვოპ
მათ და დავუმატებთ 1 სვოპ counter.

54
00:02:24,920 --> 00:02:26,230
>> ახლა შეამჩნია, რა მოხდა.

55
00:02:26,230 --> 00:02:29,514
ჩვენ გადავიდა 6 ყველა გზა ბოლომდე.

56
00:02:29,514 --> 00:02:32,180
ასე რომ, შერჩევის დალაგების, თუ თქვენ
ჩანს, რომ ვიდეო, რა გავაკეთეთ,

57
00:02:32,180 --> 00:02:35,290
ჩვენ დასრულდა მოძრავი
პატარა ელემენტები შენობა

58
00:02:35,290 --> 00:02:39,640
დახარისხებული მასივი, არსებითად,
მარცხნიდან მარჯვნივ, პატარა რომ უდიდესი.

59
00:02:39,640 --> 00:02:43,200
იმ შემთხვევაში, თუ bubble sort, თუ ჩვენ
შემდეგ ამ კონკრეტულ ალგორითმი,

60
00:02:43,200 --> 00:02:46,720
ჩვენ რეალურად აპირებს უნდა მშენებლობის
დახარისხებული array მარჯვნიდან

61
00:02:46,720 --> 00:02:49,100
მარცხნივ, უმსხვილესი to ყველაზე პატარა.

62
00:02:49,100 --> 00:02:53,840
ჩვენ ეფექტურად bubbled 6
უდიდესი მნიშვნელობა, ყველა გზა ბოლომდე.

63
00:02:53,840 --> 00:02:56,165
>> ასე რომ, ახლა ჩვენ შეგვიძლია განვაცხადოთ,
რომ ეს არის დახარისხებული,

64
00:02:56,165 --> 00:02:59,130
და მომავალში iterations--
გადის მასივი ერთხელ

65
00:02:59,130 --> 00:03:01,280
ჩვენ არ უნდა განიხილოს 6 უქმნით.

66
00:03:01,280 --> 00:03:03,850
ჩვენ მხოლოდ უნდა განიხილოს
არასორტირებული ელემენტები

67
00:03:03,850 --> 00:03:06,299
როდესაც ჩვენ შევხედავთ მიმდებარე წყვილი.

68
00:03:06,299 --> 00:03:08,340
ასე რომ, ჩვენ დასრულდა ერთი
გაიაროს bubble sort.

69
00:03:08,340 --> 00:03:11,941
ასე რომ, ახლა ჩვენ დავუბრუნდეთ კითხვას,
ვიმეორებ, სანამ swap counter არის 0.

70
00:03:11,941 --> 00:03:13,690
ისე swap counter
4, ამიტომ ჩვენ ვაპირებთ

71
00:03:13,690 --> 00:03:15,410
შევინარჩუნოთ იმეორებს ამ პროცესში კიდევ ერთხელ.

72
00:03:15,410 --> 00:03:19,180
>> ჩვენ ვაპირებთ, რომ აღადგინოთ swap counter
0, და შევხედოთ თითოეული მიმდებარე წყვილი.

73
00:03:19,180 --> 00:03:21,890
ამიტომ, ჩვენ დავიწყებთ 2 და 1 ისინი
მწყობრიდან, ამიტომ ჩვენ სვოპ მათ

74
00:03:21,890 --> 00:03:23,620
და დავუმატებთ 1 სვოპ counter.

75
00:03:23,620 --> 00:03:25,490
2 და 3, ისინი მიზნით.

76
00:03:25,490 --> 00:03:27,060
ჩვენ არ გვჭირდება არაფრის.

77
00:03:27,060 --> 00:03:28,420
3 და 5 მიზნით.

78
00:03:28,420 --> 00:03:30,150
ჩვენ არ უნდა გავაკეთოთ არაფერი არსებობს.

79
00:03:30,150 --> 00:03:32,515
>> 5 და 4, ისინი გარეთ
იმისათვის, და ამიტომ ჩვენ

80
00:03:32,515 --> 00:03:35,130
უნდა სვოპ მათ და დაამატოთ
1-swap counter.

81
00:03:35,130 --> 00:03:38,880
და ახლა ჩვენ გადავიდა 5,
შემდეგი უდიდესი ელემენტი,

82
00:03:38,880 --> 00:03:40,920
ბოლოს არასორტირებული ნაწილი.

83
00:03:40,920 --> 00:03:44,360
ასე რომ, ახლა ჩვენ შეგვიძლია მოვუწოდებთ, რომ
ნაწილი დახარისხებული ნაწილი.

84
00:03:44,360 --> 00:03:47,180
>> ახლა თქვენ ეძებს
ეკრანზე და ალბათ შემიძლია გითხრათ,

85
00:03:47,180 --> 00:03:50,130
როგორც შემიძლია, რომ მასივი
დალაგებულია ახლავე.

86
00:03:50,130 --> 00:03:51,820
მაგრამ ჩვენ არ შეგვიძლია დავამტკიცოთ, რომ ამჟამად.

87
00:03:51,820 --> 00:03:54,359
ჩვენ არ გვაქვს გარანტია
რომ ეს დახარისხებული.

88
00:03:54,359 --> 00:03:56,900
მაგრამ ეს არის, სადაც swap
counter აპირებს მოვიდეს პიესა.

89
00:03:56,900 --> 00:03:59,060
>> ასე რომ, ჩვენ დასრულდა აკეთებს.

90
00:03:59,060 --> 00:04:00,357
სვოპ counter 2.

91
00:04:00,357 --> 00:04:02,190
ასე რომ, ჩვენ ვაპირებთ გავიმეორო
ეს პროცესი კიდევ ერთხელ,

92
00:04:02,190 --> 00:04:04,290
ვიმეორებ, სანამ swap counter არის 0.

93
00:04:04,290 --> 00:04:05,550
რესეტი swap counter 0.

94
00:04:05,550 --> 00:04:06,820
ასე რომ, ჩვენ აღადგინოთ იგი.

95
00:04:06,820 --> 00:04:09,810
>> ახლა შევხედოთ თითოეული მიმდებარე წყვილი.

96
00:04:09,810 --> 00:04:11,880
სწორედ იმისათვის, 1 და 2.

97
00:04:11,880 --> 00:04:13,590
2 და 3 მიზნით.

98
00:04:13,590 --> 00:04:15,010
3 და 4 მიზნით.

99
00:04:15,010 --> 00:04:19,250
ასე რომ, ამ ეტაპზე, შეამჩნია ჩვენ უკვე დასრულდა
ეძებს ყოველ მიმდებარე წყვილი,

100
00:04:19,250 --> 00:04:22,530
მაგრამ swap counter კვლავ 0.

101
00:04:22,530 --> 00:04:25,520
>> თუ ჩვენ არ უნდა გადავიდეს
ნებისმიერი ელემენტები, მაშინ ისინი

102
00:04:25,520 --> 00:04:28,340
უნდა იყოს იმისათვის, მოძებნა
ძალით ამ პროცესში.

103
00:04:28,340 --> 00:04:32,000
ასე რომ, ეფექტურობის სახის,
რომ ჩვენ კომპიუტერის მეცნიერები მიყვარს,

104
00:04:32,000 --> 00:04:35,560
არის ახლა ჩვენ შეგვიძლია განვაცხადოთ,
მთელი რიგი უნდა

105
00:04:35,560 --> 00:04:38,160
იყოს დახარისხებული, იმიტომ, რომ ჩვენ არ
უნდა სვოპ ნებისმიერი ელემენტები.

106
00:04:38,160 --> 00:04:40,380
ეს არის საკმაოდ ლამაზი.

107
00:04:40,380 --> 00:04:43,260
>> ასე რომ, რა უარეს შემთხვევაში
სცენარი ბუშტი დალაგება?

108
00:04:43,260 --> 00:04:46,240
უარეს შემთხვევაში მასივი
სრულიად საპირისპირო მიზნით,

109
00:04:46,240 --> 00:04:49,870
და ამიტომ ჩვენ უნდა ბუშტი თითოეულ
ერთი დიდი ელემენტები ყველა

110
00:04:49,870 --> 00:04:51,780
გზა მასშტაბით მასივი.

111
00:04:51,780 --> 00:04:55,350
ჩვენ ეფექტურად ასევე უნდა
bubble ყველა პატარა ელემენტები უკან

112
00:04:55,350 --> 00:04:57,050
ყველა გზა მასშტაბით მასივი, ძალიან.

113
00:04:57,050 --> 00:05:01,950
ასე რომ, თითოეული N ელემენტები უნდა გადავიდეს
მთელი მეორე n ელემენტებს.

114
00:05:01,950 --> 00:05:04,102
ასე რომ, უარეს შემთხვევაში.

115
00:05:04,102 --> 00:05:05,810
საუკეთესო შემთხვევაში
სცენარი, თუმცა, ეს არის

116
00:05:05,810 --> 00:05:07,880
ოდნავ განსხვავებული შერჩევა ერთგვარი.

117
00:05:07,880 --> 00:05:10,040
მასივი უკვე
დალაგებულია, როდესაც ჩვენ წავიდეთ.

118
00:05:10,040 --> 00:05:12,550
ჩვენ არ გვაქვს რაიმე
სვოპების პირველ უღელტეხილზე.

119
00:05:12,550 --> 00:05:14,940
ასე რომ, ჩვენ შეიძლება უნდა გამოიყურებოდეს
განთავსებულია ნაკლები ელემენტები, არა?

120
00:05:14,940 --> 00:05:18,580
ჩვენ არ უნდა გავიმეოროთ ეს
დამუშავებას ნომერი ჯერ მეტი.

121
00:05:18,580 --> 00:05:19,540
>> ასე რომ, რას ნიშნავს ეს?

122
00:05:19,540 --> 00:05:22,390
ასე რომ, რა არის ყველაზე უარესი სცენარი
ამისთვის bubble sort, და რა არის

123
00:05:22,390 --> 00:05:25,330
საუკეთესო სცენარით ბუშტი დალაგება?

124
00:05:25,330 --> 00:05:27,770
ხომ იცი, ეს?

125
00:05:27,770 --> 00:05:32,420
უარეს შემთხვევაში თქვენ უნდა iterate
მთელი n ელემენტებს N ჯერ.

126
00:05:32,420 --> 00:05:34,220
ასე რომ, უარეს შემთხვევაში არის n კვადრატში.

127
00:05:34,220 --> 00:05:36,550
>> იმ შემთხვევაში, თუ მასივი მშვენივრად
დახარისხებული, თუმცა, თქვენ მხოლოდ

128
00:05:36,550 --> 00:05:38,580
უნდა შევხედოთ თითოეული
ელემენტები ერთხელ.

129
00:05:38,580 --> 00:05:42,670
და თუ swap counter კვლავ 0,
შეიძლება ითქვას, ამ მასივი დალაგებულია.

130
00:05:42,670 --> 00:05:45,780
ასე რომ, საუკეთესო შემთხვევაში, ეს არის
რეალურად უკეთესი არჩევანი

131
00:05:45,780 --> 00:05:49,230
დალაგება ის omega of ო.

132
00:05:49,230 --> 00:05:50,270
>> მე Doug Lloyd.

133
00:05:50,270 --> 00:05:52,140
ეს არის CS50.

134
00:05:52,140 --> 00:05:54,382