1
00:00:00,000 --> 00:00:03,360
>> [MUSIC CHƠI]

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

3
00:00:04,522 --> 00:00:06,730
DOUG LLOYD: Tất cả các bên phải, vì vậy
bubble sort là một thuật toán

4
00:00:06,730 --> 00:00:08,730
bạn có thể sử dụng để sắp xếp một tập các phần tử.

5
00:00:08,730 --> 00:00:10,850
Chúng ta hãy xem làm thế nào nó hoạt động.

6
00:00:10,850 --> 00:00:13,240
>> Vì vậy, ý tưởng cơ bản đằng sau
bubble sort này.

7
00:00:13,240 --> 00:00:17,340
Chúng ta thường muốn di chuyển cao hơn
yếu tố có giá trị thường sang bên phải,

8
00:00:17,340 --> 00:00:20,340
và giảm các yếu tố có giá trị chung
bên trái, như chúng ta mong đợi.

9
00:00:20,340 --> 00:00:23,256
Chúng tôi muốn những điều thấp hơn để được ở
đầu, và những điều cao hơn

10
00:00:23,256 --> 00:00:24,970
để được ở cuối.

11
00:00:24,970 --> 00:00:26,130
>> Làm thế nào để chúng tôi làm điều này?

12
00:00:26,130 --> 00:00:28,040
Vâng trong mã giả,
chúng ta có thể nói, chúng ta hãy

13
00:00:28,040 --> 00:00:30,320
thiết lập một vùng trao đổi truy cập đến một giá trị khác không.

14
00:00:30,320 --> 00:00:32,570
Chúng ta sẽ thấy lý do tại sao chúng tôi làm điều đó trong một giây.

15
00:00:32,570 --> 00:00:36,090
Và sau đó chúng ta lập lại sau
quá trình cho đến quầy trao đổi là 0,

16
00:00:36,090 --> 00:00:39,910
hoặc cho đến khi chúng tôi thực hiện giao dịch hoán đổi không có ở tất cả.

17
00:00:39,910 --> 00:00:43,170
>> Thiết lập lại các truy cập để hoán đổi
0 nếu nó chưa được 0.

18
00:00:43,170 --> 00:00:46,420
Sau đó nhìn vào mỗi
cặp liền kề của các yếu tố.

19
00:00:46,420 --> 00:00:49,550
Nếu hai yếu tố này là
không theo thứ tự, trao đổi chúng,

20
00:00:49,550 --> 00:00:51,620
và thêm 1 đến quầy trao đổi.

21
00:00:51,620 --> 00:00:53,870
Nếu bạn đang suy nghĩ về
này trước khi bạn hình dung nó,

22
00:00:53,870 --> 00:00:57,471
nhận thấy rằng điều này sẽ di chuyển thấp hơn
yếu tố có giá trị bên trái

23
00:00:57,471 --> 00:01:00,720
và các yếu tố bên phải cao hơn giá trị,
làm hiệu quả những gì chúng tôi muốn làm,

24
00:01:00,720 --> 00:01:03,940
đó là di chuyển những nhóm
các yếu tố theo cách đó.

25
00:01:03,940 --> 00:01:07,035
Chúng ta hãy hình dung như thế nào đây
có thể nhìn bằng cách sử dụng mảng của chúng tôi

26
00:01:07,035 --> 00:01:10,504
mà chúng tôi sử dụng để kiểm tra
ra các thuật toán.

27
00:01:10,504 --> 00:01:13,420
Chúng tôi có một mảng không được phân loại ở đây một lần nữa,
chỉ ra bởi tất cả các yếu tố

28
00:01:13,420 --> 00:01:14,840
là màu đỏ.

29
00:01:14,840 --> 00:01:17,970
Và tôi đặt swap truy cập của tôi
đến một giá trị khác.

30
00:01:17,970 --> 00:01:20,610
Tôi tùy tiện chọn
tiêu cực 1-- nó không phải là 0.

31
00:01:20,610 --> 00:01:23,840
Chúng tôi muốn lặp lại quá trình này
cho đến quầy trao đổi là 0.

32
00:01:23,840 --> 00:01:26,540
Đây là lý do tại sao tôi đặt trao đổi của tôi
truy cập vào một số giá trị khác không,

33
00:01:26,540 --> 00:01:29,400
bởi vì nếu không
trao đổi truy cập sẽ là 0.

34
00:01:29,400 --> 00:01:31,610
Chúng tôi thậm chí sẽ không bắt đầu
quá trình của thuật toán.

35
00:01:31,610 --> 00:01:33,610
Vì vậy, một lần nữa, các bước are--
thiết lập lại các truy cập swap

36
00:01:33,610 --> 00:01:37,900
0, sau đó nhìn vào mỗi liền kề
cặp, và nếu họ đang trong trật tự,

37
00:01:37,900 --> 00:01:40,514
trao đổi chúng, và thêm 1
đến quầy trao đổi.

38
00:01:40,514 --> 00:01:41,680
Vì vậy, chúng ta hãy bắt đầu quá trình này.

39
00:01:41,680 --> 00:01:44,430
Vì vậy, điều đầu tiên chúng tôi làm là
chúng tôi thiết lập các quầy trao đổi để 0,

40
00:01:44,430 --> 00:01:46,660
và sau đó chúng tôi bắt đầu tìm kiếm
ở mỗi cặp liền kề.

41
00:01:46,660 --> 00:01:49,140
>> Vì vậy, đầu tiên chúng ta bắt đầu nhìn vào 5 và 2.

42
00:01:49,140 --> 00:01:52,410
Chúng tôi thấy rằng họ đang ra khỏi
đặt hàng và vì vậy chúng tôi trao đổi chúng.

43
00:01:52,410 --> 00:01:53,830
Và chúng ta thêm 1 đến quầy trao đổi.

44
00:01:53,830 --> 00:01:57,860
Vì vậy bây giờ truy cập trao đổi của chúng tôi là 1,
và 2 và 5 đã được chuyển sang.

45
00:01:57,860 --> 00:01:59,370
Bây giờ chúng ta lặp lại quá trình này một lần nữa.

46
00:01:59,370 --> 00:02:03,540
>> Chúng tôi nhìn vào cặp liền kề,
5 và 1-- họ cũng ra khỏi trật tự,

47
00:02:03,540 --> 00:02:06,960
vì vậy chúng tôi trao đổi chúng và thêm
1 đến quầy trao đổi.

48
00:02:06,960 --> 00:02:08,900
Sau đó, chúng ta nhìn vào 5 và 3.

49
00:02:08,900 --> 00:02:13,830
Họ là trong trật tự, vì vậy chúng tôi trao đổi
họ và chúng tôi thêm 1 đến quầy trao đổi.

50
00:02:13,830 --> 00:02:15,550
Sau đó, chúng ta nhìn vào 5 và 6.

51
00:02:15,550 --> 00:02:18,630
Họ đang ở trong trật tự, vì vậy chúng tôi không thực sự
cần phải trao đổi bất cứ điều gì lúc này.

52
00:02:18,630 --> 00:02:20,250
Sau đó, chúng ta nhìn vào 6 và 4.

53
00:02:20,250 --> 00:02:24,920
Họ cũng đang trong trật tự, vì vậy chúng tôi trao đổi
họ và chúng tôi thêm 1 đến quầy trao đổi.

54
00:02:24,920 --> 00:02:26,230
>> Bây giờ chú ý những gì đã xảy ra.

55
00:02:26,230 --> 00:02:29,514
Chúng tôi đã chuyển 6 tất cả các cách để kết thúc.

56
00:02:29,514 --> 00:02:32,180
Vì vậy, trong việc lựa chọn loại, nếu bạn đã
xem video đó, những gì chúng tôi làm là

57
00:02:32,180 --> 00:02:35,290
chúng tôi đã kết thúc di chuyển
yếu tố nhỏ nhất trong xây dựng

58
00:02:35,290 --> 00:02:39,640
các mảng được sắp xếp cơ bản từ
trái sang phải, nhỏ nhất đến lớn nhất.

59
00:02:39,640 --> 00:02:43,200
Trong trường hợp của bong bóng sắp xếp, nếu chúng tôi
sau thuật toán cụ thể này,

60
00:02:43,200 --> 00:02:46,720
chúng tôi đang thực sự sẽ được xây dựng
các mảng được sắp xếp từ bên phải

61
00:02:46,720 --> 00:02:49,100
sang trái, lớn nhất đến nhỏ nhất.

62
00:02:49,100 --> 00:02:53,840
Chúng tôi đã có hiệu quả các bọt khí 6,
giá trị lớn nhất, tất cả các cách để kết thúc.

63
00:02:53,840 --> 00:02:56,165
>> Và như vậy chúng ta có thể khai báo
rằng đó là sắp xếp,

64
00:02:56,165 --> 00:02:59,130
và trong tương lai iterations--
đi qua mảng again--

65
00:02:59,130 --> 00:03:01,280
chúng ta không cần phải xem xét 6 nữa.

66
00:03:01,280 --> 00:03:03,850
Chúng tôi chỉ phải xem xét
các yếu tố không được phân loại

67
00:03:03,850 --> 00:03:06,299
khi chúng ta nhìn vào cặp liền kề.

68
00:03:06,299 --> 00:03:08,340
Vì vậy, chúng tôi đã hoàn thành một
đi qua bong bóng sắp xếp.

69
00:03:08,340 --> 00:03:11,941
Vì vậy, bây giờ chúng ta quay trở lại với câu hỏi,
lặp lại cho đến quầy trao đổi là 0.

70
00:03:11,941 --> 00:03:13,690
Vâng quầy trao đổi
là 4, vì vậy chúng tôi đang đi

71
00:03:13,690 --> 00:03:15,410
để tiếp tục lặp lại quá trình này một lần nữa.

72
00:03:15,410 --> 00:03:19,180
>> Chúng tôi sẽ thiết lập lại các truy cập swap
đến 0, và nhìn vào từng cặp liền kề.

73
00:03:19,180 --> 00:03:21,890
Vì vậy, chúng ta bắt đầu với 2 và 1-- họ
trong trật tự, vì vậy chúng tôi trao đổi chúng

74
00:03:21,890 --> 00:03:23,620
và chúng tôi thêm 1 đến quầy trao đổi.

75
00:03:23,620 --> 00:03:25,490
2 và 3, họ đang ở trong trật tự.

76
00:03:25,490 --> 00:03:27,060
Chúng tôi không cần phải làm gì cả.

77
00:03:27,060 --> 00:03:28,420
3 và 5 là theo thứ tự.

78
00:03:28,420 --> 00:03:30,150
Chúng tôi không cần phải làm bất cứ điều gì ở đó.

79
00:03:30,150 --> 00:03:32,515
>> 5 và 4, họ đang ra
trật tự, và vì vậy chúng tôi

80
00:03:32,515 --> 00:03:35,130
cần trao đổi chúng và thêm
1 đến quầy trao đổi.

81
00:03:35,130 --> 00:03:38,880
Và bây giờ chúng tôi đã chuyển 5,
các phần tử lớn nhất tiếp theo,

82
00:03:38,880 --> 00:03:40,920
đến hết phần được phân loại.

83
00:03:40,920 --> 00:03:44,360
Vì vậy, bây giờ chúng ta có thể gọi đó
một phần của các phần được sắp xếp.

84
00:03:44,360 --> 00:03:47,180
>> Bây giờ bạn đang nhìn vào
màn hình và có lẽ có thể nói,

85
00:03:47,180 --> 00:03:50,130
như tôi có thể, rằng mảng
được sắp xếp ngay bây giờ.

86
00:03:50,130 --> 00:03:51,820
Nhưng chúng ta không thể chứng minh rằng chưa.

87
00:03:51,820 --> 00:03:54,359
Chúng tôi không có một đảm bảo
mà nó được sắp xếp.

88
00:03:54,359 --> 00:03:56,900
Nhưng đây là nơi trao đổi
truy cập sẽ đi vào chơi.

89
00:03:56,900 --> 00:03:59,060
>> Vì vậy, chúng tôi đã hoàn thành một đường chuyền.

90
00:03:59,060 --> 00:04:00,357
Các trao đổi truy cập là 2.

91
00:04:00,357 --> 00:04:02,190
Vì vậy, chúng ta sẽ lặp lại
quá trình này một lần nữa,

92
00:04:02,190 --> 00:04:04,290
lặp lại cho đến quầy trao đổi là 0.

93
00:04:04,290 --> 00:04:05,550
Thiết lập lại các truy cập swap 0.

94
00:04:05,550 --> 00:04:06,820
Vì vậy, chúng tôi sẽ thiết lập lại nó.

95
00:04:06,820 --> 00:04:09,810
>> Bây giờ nhìn vào mỗi cặp liền kề.

96
00:04:09,810 --> 00:04:11,880
Đó là theo thứ tự, 1 và 2.

97
00:04:11,880 --> 00:04:13,590
2 và 3 là theo thứ tự.

98
00:04:13,590 --> 00:04:15,010
3 và 4 theo thứ tự.

99
00:04:15,010 --> 00:04:19,250
Vì vậy, tại thời điểm này, nhận thấy chúng ta đã hoàn thành
nhìn vào từng cặp liền kề,

100
00:04:19,250 --> 00:04:22,530
nhưng quầy trao đổi vẫn là 0.

101
00:04:22,530 --> 00:04:25,520
>> Nếu chúng ta không cần phải chuyển đổi
bất kỳ yếu tố, sau đó họ

102
00:04:25,520 --> 00:04:28,340
phải theo thứ tự, bởi
đức của quá trình này.

103
00:04:28,340 --> 00:04:32,000
Và do đó, một hiệu quả của các loại,
các nhà khoa học máy tính của chúng ta yêu thương,

104
00:04:32,000 --> 00:04:35,560
bây giờ chúng ta có thể khai báo
toàn bộ mảng phải

105
00:04:35,560 --> 00:04:38,160
được sắp xếp, bởi vì chúng tôi đã không
phải trao đổi bất kỳ yếu tố.

106
00:04:38,160 --> 00:04:40,380
Đó là khá tốt đẹp.

107
00:04:40,380 --> 00:04:43,260
>> Vì vậy, trường hợp xấu nhất là gì
kịch bản với bong bóng sắp xếp?

108
00:04:43,260 --> 00:04:46,240
Trong trường hợp xấu nhất là mảng
theo thứ tự ngược lại hoàn toàn,

109
00:04:46,240 --> 00:04:49,870
và vì vậy chúng tôi phải bong bóng mỗi
trong những yếu tố lớn tất cả

110
00:04:49,870 --> 00:04:51,780
các cách trên mảng.

111
00:04:51,780 --> 00:04:55,350
Và chúng tôi có hiệu quả cũng phải
bong bóng tất cả các yếu tố nhỏ lại

112
00:04:55,350 --> 00:04:57,050
tất cả các cách trên mảng, quá.

113
00:04:57,050 --> 00:05:01,950
Vì vậy, mỗi nguyên tố n có để di chuyển
trên tất cả các yếu tố n khác.

114
00:05:01,950 --> 00:05:04,102
Vì vậy, đó là kịch bản trường hợp xấu nhất.

115
00:05:04,102 --> 00:05:05,810
Trong trường hợp tốt nhất
kịch bản mặc dù, đây là

116
00:05:05,810 --> 00:05:07,880
hơi khác nhau từ sắp xếp chọn.

117
00:05:07,880 --> 00:05:10,040
Các mảng là đã
được sắp xếp khi chúng ta đi vào.

118
00:05:10,040 --> 00:05:12,550
Chúng tôi không có thực hiện bất kỳ
giao dịch hoán đổi trên đèo đầu tiên.

119
00:05:12,550 --> 00:05:14,940
Vì vậy, chúng ta có thể phải xem xét
vào các yếu tố ít hơn, phải không?

120
00:05:14,940 --> 00:05:18,580
Chúng tôi không cần phải lặp lại điều này
xử lý một số lần.

121
00:05:18,580 --> 00:05:19,540
>> Vì vậy, có nghĩa là gì?

122
00:05:19,540 --> 00:05:22,390
Vì vậy, trường hợp xấu nhất là gì
cho bong bóng sắp xếp, và những gì

123
00:05:22,390 --> 00:05:25,330
trường hợp kịch bản tốt nhất cho bong bóng sắp xếp?

124
00:05:25,330 --> 00:05:27,770
Bạn đã đoán này?

125
00:05:27,770 --> 00:05:32,420
Trong trường hợp xấu nhất bạn phải lặp
trên tất cả các yếu tố n lần n.

126
00:05:32,420 --> 00:05:34,220
Vì vậy, trường hợp xấu nhất là n bình phương.

127
00:05:34,220 --> 00:05:36,550
>> Nếu mảng là hoàn hảo
sắp xếp, mặc dù bạn chỉ

128
00:05:36,550 --> 00:05:38,580
phải nhìn vào mỗi
của các yếu tố một lần.

129
00:05:38,580 --> 00:05:42,670
Và nếu quầy trao đổi vẫn là 0,
bạn có thể nói mảng này được sắp xếp.

130
00:05:42,670 --> 00:05:45,780
Và do đó, trong trường hợp tốt nhất, đây là
thực sự tốt hơn so với lựa chọn

131
00:05:45,780 --> 00:05:49,230
sort-- nó omega của n.

132
00:05:49,230 --> 00:05:50,270
>> Tôi Doug Lloyd.

133
00:05:50,270 --> 00:05:52,140
Đây là CS50.

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