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 ĐẠI HỌC HARVARD]

3
00:00:04,560 --> 00:00:07,500
[Đây là CS50. CS50TV]

4
00:00:08,000 --> 00:00:11,730
Sắp xếp bong bóng là một ví dụ về một thuật toán phân loại -

5
00:00:11,730 --> 00:00:14,460
có nghĩa là, một thủ tục để sắp xếp một tập hợp các yếu tố trong

6
00:00:14,460 --> 00:00:15,840
tăng dần hoặc giảm dần.

7
00:00:15,840 --> 00:00:18,710
Ví dụ, nếu bạn muốn sắp xếp một mảng bao gồm các con số

8
00:00:18,710 --> 00:00:23,060
[3, 5, 2, 9], thực hiện đúng loại Bubble sẽ trả lại

9
00:00:23,060 --> 00:00:26,260
sắp xếp mảng [2, 3, 5, 9] theo thứ tự tăng dần.

10
00:00:26,260 --> 00:00:28,850
Bây giờ, tôi sẽ giải thích trong giả thuật toán làm việc như thế nào.

11
00:00:28,850 --> 00:00:34,000
>> Hãy nói rằng chúng tôi đang phân loại một danh sách gồm 5 số nguyên - 3, 2, 9, 6, và 5.

12
00:00:34,000 --> 00:00:37,650
Thuật toán bắt đầu bằng cách nhìn vào hai yếu tố đầu tiên, 3 và 2,

13
00:00:37,650 --> 00:00:40,850
và kiểm tra nếu họ đang ra khỏi thứ tự tương đối với nhau.

14
00:00:40,850 --> 00:00:43,150
Họ là 3 là lớn hơn 2.

15
00:00:43,150 --> 00:00:45,190
Để có thứ tự tăng dần, họ sẽ có cách khác xung quanh.

16
00:00:45,190 --> 00:00:46,610
Vì vậy, chúng tôi trao đổi chúng.

17
00:00:46,610 --> 00:00:49,760
Bây giờ danh sách trông như thế này: [2, 3, 9, 6, 5].

18
00:00:49,760 --> 00:00:52,450
>> Tiếp theo, chúng ta nhìn vào các yếu tố thứ hai và thứ ba, 3 và 9.

19
00:00:52,450 --> 00:00:55,770
Họ đang ở trong thứ tự chính xác tương đối với nhau.

20
00:00:55,770 --> 00:00:58,800
Đó là, 3 là ít hơn 9 do đó, các thuật toán không trao đổi chúng.

21
00:00:58,800 --> 00:01:01,900
Tiếp theo, chúng ta nhìn vào 9 và 6. Họ đang ra khỏi trật tự.

22
00:01:01,900 --> 00:01:04,260
>> Vì vậy, chúng ta cần trao đổi chúng vì 9 là lớn hơn 6.

23
00:01:04,260 --> 00:01:08,840
Cuối cùng, chúng ta nhìn vào hai số nguyên, 9 và 5.

24
00:01:08,840 --> 00:01:10,850
Họ đang ra khỏi trật tự, vì vậy họ phải được trao đổi.

25
00:01:10,850 --> 00:01:13,360
Sau khi vượt qua hoàn chỉnh đầu tiên thông qua danh sách,

26
00:01:13,360 --> 00:01:17,140
nó trông như thế này: [2, 3, 6, 5, 9].

27
00:01:17,140 --> 00:01:19,690
Không phải là xấu. Nó gần như được sắp xếp.

28
00:01:19,690 --> 00:01:22,450
Nhưng chúng ta cần phải chạy qua danh sách một lần nữa để có được nó hoàn toàn được sắp xếp.

29
00:01:22,450 --> 00:01:29,250
Hai là ít hơn 3, nên chúng tôi không trao đổi chúng.

30
00:01:29,250 --> 00:01:31,700
>> Ba là ít hơn 6, vì vậy chúng tôi không trao đổi chúng.

31
00:01:31,700 --> 00:01:35,500
Sáu là lớn hơn 5. Chúng tôi đổi chỗ.

32
00:01:35,500 --> 00:01:38,460
Sáu là ít hơn 9. Chúng tôi không trao đổi.

33
00:01:38,460 --> 00:01:42,170
Sau khi vượt qua thứ hai thông qua, nó trông như thế này: [2, 3, 5, 6, 9]. Hoàn hảo.

34
00:01:42,170 --> 00:01:44,680
Bây giờ, hãy viết nó trong giả.

35
00:01:44,680 --> 00:01:48,450
Về cơ bản, cho mỗi phần tử trong danh sách, chúng ta cần phải nhìn vào nó

36
00:01:48,450 --> 00:01:50,060
và yếu tố trực tiếp bên phải của nó.

37
00:01:50,060 --> 00:01:53,420
Nếu họ ra khỏi trật tự tương đối với nhau - đó là, nếu các yếu tố trên bên trái

38
00:01:53,420 --> 00:01:56,810
là lớn hơn so với cái bên phải - chúng ta nên trao đổi hai yếu tố.

39
00:01:56,810 --> 00:02:01,270
>> Chúng tôi làm điều này cho tất cả các phần tử của danh sách, và chúng tôi đã thực hiện một đi qua.

40
00:02:01,270 --> 00:02:05,160
Bây giờ chúng ta chỉ cần có để làm pass-through đủ thời gian để đảm bảo danh sách

41
00:02:05,160 --> 00:02:06,480
đầy đủ, đúng cách sắp xếp.

42
00:02:06,480 --> 00:02:08,889
Nhưng bao nhiêu lần chúng ta phải vượt qua thông qua danh sách để

43
00:02:08,889 --> 00:02:10,400
đảm bảo rằng chúng tôi đang thực hiện?

44
00:02:10,400 --> 00:02:14,730
Vâng, trường hợp xấu nhất là nếu chúng ta có một danh sách hoàn toàn ngược.

45
00:02:14,730 --> 00:02:17,840
Sau đó, nó có một số vượt qua-throughs bằng số

46
00:02:17,840 --> 00:02:19,730
các yếu tố n-1.

47
00:02:19,730 --> 00:02:24,720
Nếu điều này không có ý nghĩa trực giác, suy nghĩ của một trường hợp đơn giản - danh sách [2, 1].

48
00:02:24,720 --> 00:02:28,430
>> Điều này sẽ mất một pass-thông qua để sắp xếp một cách chính xác.

49
00:02:28,430 --> 00:02:33,060
[3, 2, 1] - Trường hợp xấu nhất là với 3 yếu tố được sắp xếp ngược,

50
00:02:33,060 --> 00:02:34,830
nó sẽ mất 2 lặp đi lặp lại để sắp xếp.

51
00:02:34,830 --> 00:02:37,980
Sau một lặp đi lặp lại, đó là [2, 1, 3].

52
00:02:37,980 --> 00:02:39,550
Thứ hai sản lượng mảng được sắp xếp [1, 2, 3].

53
00:02:39,550 --> 00:02:43,350
Vì vậy, bạn biết bạn không bao giờ phải đi qua mảng, nói chung,

54
00:02:43,350 --> 00:02:46,790
hơn n-1 lần, trong đó n là số phần tử trong mảng.

55
00:02:47,090 --> 00:02:50,470
Nó được gọi là bong bóng sắp xếp bởi vì các yếu tố lớn nhất có xu hướng 'bong bóng'

56
00:02:50,470 --> 00:02:51,950
bên phải khá nhanh chóng.

57
00:02:51,950 --> 00:02:53,980
Trong thực tế, thuật toán này có hành vi rất thú vị.

58
00:02:53,980 --> 00:02:57,410
>> Sau khi lặp đi lặp lại m thông qua toàn bộ mảng,

59
00:02:57,410 --> 00:02:59,000
được đảm bảo các yếu tố ngoài cùng bên phải m

60
00:02:59,000 --> 00:03:01,000
được sắp xếp vào vị trí chính xác của họ.

61
00:03:01,000 --> 00:03:02,280
Nếu bạn muốn xem này cho chính mình,

62
00:03:02,280 --> 00:03:05,500
chúng ta có thể thử nó trên một danh sách hoàn toàn ngược [9, 6, 5, 3, 2].

63
00:03:05,500 --> 00:03:08,220
Sau khi đi qua toàn bộ danh sách,

64
00:03:08,220 --> 00:03:09,220
[Âm thanh của văn bản]

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
các yếu tố ngoài cùng bên phải 9 là ở vị trí thích hợp của nó.

67
00:03:21,250 --> 00:03:24,760
Sau khi pass-through, 6 sẽ có bọt khí-up '.

68
00:03:24,760 --> 00:03:26,220
2 vị trí ngoài cùng bên phải.

69
00:03:26,220 --> 00:03:28,840
Hai yếu tố trên quyền - 6 và 9 - sẽ được địa điểm chính xác của họ

70
00:03:28,840 --> 00:03:30,580
sau khi hai pass-throughs.

71
00:03:30,580 --> 00:03:32,590
>> Vì vậy, làm thế nào chúng ta có thể sử dụng điều này để tối ưu hóa các thuật toán?

72
00:03:32,590 --> 00:03:34,850
Vâng, sau khi một lặp đi lặp lại thông qua các mảng

73
00:03:34,850 --> 00:03:37,690
chúng tôi không thực sự cần phải kiểm tra các yếu tố ngoài cùng bên phải

74
00:03:37,690 --> 00:03:39,200
bởi vì chúng ta biết nó được sắp xếp.

75
00:03:39,200 --> 00:03:43,050
Sau hai lặp đi lặp lại, chúng ta biết chắc chắn rằng hai yếu tố cuối cùng bên phải được đưa ra.

76
00:03:43,050 --> 00:03:48,260
Vì vậy, nói chung, sau khi lặp đi lặp lại k qua mảng đầy đủ,

77
00:03:48,260 --> 00:03:51,550
kiểm tra các yếu tố k cuối cùng là không cần thiết vì chúng ta biết

78
00:03:51,550 --> 00:03:52,360
họ đang ở trong vị trí chính xác rồi.

79
00:03:52,360 --> 00:03:54,870
>> Vì vậy, nếu bạn đang phân loại một mảng n phần tử,

80
00:03:54,870 --> 00:03:57,870
phiên đầu tiên - bạn sẽ phải sắp xếp tất cả các yếu tố đầu tiên n-0.

81
00:03:57,870 --> 00:04:04,170
Trên lặp thứ hai, bạn sẽ phải xem xét tất cả các yếu tố, nhưng cuối cùng -

82
00:04:04,170 --> 00:04:07,090
n-1 đầu tiên.

83
00:04:07,090 --> 00:04:10,520
Một tối ưu hóa có thể là để kiểm tra xem danh sách đã được sắp xếp

84
00:04:10,520 --> 00:04:11,710
sau mỗi lần lặp.

85
00:04:11,710 --> 00:04:13,900
Nếu nó đã được sắp xếp, chúng ta không cần phải thực hiện lặp đi lặp lại nữa

86
00:04:13,900 --> 00:04:15,310
thông qua danh sách.

87
00:04:15,310 --> 00:04:16,220
Làm thế nào chúng ta có thể làm điều này?

88
00:04:16,220 --> 00:04:19,360
Vâng, nếu chúng ta không thực hiện bất kỳ giao dịch hoán đổi trên một pass-thông qua danh sách,

89
00:04:19,360 --> 00:04:22,350
thì rõ ràng rằng danh sách đã được sắp xếp bởi vì chúng tôi đã không trao đổi bất cứ điều gì.

90
00:04:22,350 --> 00:04:24,160
Vì vậy, chúng tôi chắc chắn không phải sắp xếp lại.

91
00:04:24,160 --> 00:04:27,960
>> Có lẽ bạn có thể khởi tạo một biến cờ được gọi là 'không được sắp xếp'

92
00:04:27,960 --> 00:04:30,990
sai và thay đổi nó để thực sự nếu bạn phải trao đổi bất kỳ yếu tố trên

93
00:04:30,990 --> 00:04:32,290
một lặp đi lặp lại thông qua các mảng.

94
00:04:32,290 --> 00:04:35,350
Hoặc tương tự như vậy, làm cho một truy cập để đếm có bao nhiêu giao dịch hoán đổi bạn thực hiện

95
00:04:35,350 --> 00:04:37,040
trên bất kỳ lặp đi lặp lại nhất định.

96
00:04:37,040 --> 00:04:40,040
Vào cuối của sự lặp lại, nếu bạn không trao đổi bất kỳ của các yếu tố,

97
00:04:40,040 --> 00:04:41,780
bạn biết danh sách đã được sắp xếp và bạn đang làm.

98
00:04:41,780 --> 00:04:44,090
Bubble Phân loại, như các thuật toán phân loại khác, có thể là

99
00:04:44,090 --> 00:04:46,960
tinh chỉnh để làm việc cho bất kỳ yếu tố trong đó có một phương pháp đặt hàng.

100
00:04:46,960 --> 00:04:50,610
>> Tức là, với hai yếu tố bạn có một cách để nói nếu một trong những người đầu tiên

101
00:04:50,610 --> 00:04:53,770
lớn hơn, bằng hoặc nhỏ hơn lần thứ hai.

102
00:04:53,770 --> 00:04:56,870
Ví dụ, bạn có thể sắp xếp các chữ cái trong bảng chữ cái bằng cách nói

103
00:04:56,870 --> 00:05:00,520
a <b, b <c, vv

104
00:05:00,520 --> 00:05:03,830
Hoặc bạn có thể sắp xếp các ngày trong tuần chủ nhật là ít hơn so với thứ hai

105
00:05:03,830 --> 00:05:05,110
đó là ít hơn thứ ba.

106
00:05:05,110 --> 00:05:09,630
>> Sắp xếp bong bóng không có nghĩa là một thuật toán sắp xếp rất hiệu quả nhanh chóng.

107
00:05:09,630 --> 00:05:12,370
Trường hợp xấu nhất thời gian chạy là Big O n ²

108
00:05:12,370 --> 00:05:14,810
bởi vì bạn phải thực hiện lặp đi lặp lại n thông qua một danh sách

109
00:05:14,810 --> 00:05:18,430
kiểm tra tất cả các yếu tố n mỗi pass-through, nxn = n ².

110
00:05:18,430 --> 00:05:22,730
Thời gian chạy này có nghĩa rằng, cũng như số lượng của các yếu tố bạn đang phân loại tăng,

111
00:05:22,730 --> 00:05:24,330
tăng thời gian chạy bình phương.

112
00:05:24,330 --> 00:05:27,330
>> Nhưng nếu hiệu quả không phải là một mối quan tâm chính của chương trình của bạn

113
00:05:27,330 --> 00:05:29,550
hoặc nếu bạn chỉ sắp xếp một số lượng nhỏ các nguyên tố,

114
00:05:29,550 --> 00:05:31,660
bạn có thể tìm thấy Sắp xếp Bubble hữu ích bởi vì

115
00:05:31,660 --> 00:05:33,360
nó là một trong những thuật toán sắp xếp đơn giản để hiểu

116
00:05:33,360 --> 00:05:34,250
và mã.

117
00:05:34,250 --> 00:05:37,270
Nó cũng là một cách tuyệt vời để có được kinh nghiệm với dịch một lý thuyết

118
00:05:37,270 --> 00:05:40,220
thuật toán vào mã hoạt động thực tế.

119
00:05:40,220 --> 00:05:43,000
Vâng, đó là bong bóng sắp xếp cho bạn. Cảm ơn bạn đã cho xem.

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