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 HARVARD UNIVERSITY]

3
00:00:04,560 --> 00:00:07,500
[INI ADALAH CS50. CS50TV]

4
00:00:08,000 --> 00:00:11,730
Susun gelembung satu contoh algoritma sorting -

5
00:00:11,730 --> 00:00:14,460
iaitu, satu prosedur untuk menyusun satu set unsur-unsur dalam

6
00:00:14,460 --> 00:00:15,840
urutan naik atau turun.

7
00:00:15,840 --> 00:00:18,710
Sebagai contoh, jika anda mahu untuk menyelesaikan array yang terdiri daripada nombor

8
00:00:18,710 --> 00:00:23,060
[3, 5, 2, 9], pelaksanaan yang betul Susun Bubble akan memulangkan

9
00:00:23,060 --> 00:00:26,260
pelbagai disusun [2, 3, 5, 9] dalam tertib menaik.

10
00:00:26,260 --> 00:00:28,850
Sekarang, saya akan terangkan dalam pseudokod bagaimana algoritma berfungsi.

11
00:00:28,850 --> 00:00:34,000
>> Mari kita mengatakan bahawa kita sedang menyusun senarai sebanyak 5 integer - 3, 2, 9, 6, dan 5.

12
00:00:34,000 --> 00:00:37,650
Algoritma bermula dengan melihat dua unsur pertama, 3 dan 2,

13
00:00:37,650 --> 00:00:40,850
dan memeriksa jika mereka berada di luar perintah relatif kepada satu sama lain.

14
00:00:40,850 --> 00:00:43,150
Mereka adalah - 3 adalah lebih daripada 2.

15
00:00:43,150 --> 00:00:45,190
Untuk menjadi dalam usaha menaik, mereka harus menjadi cara lain di sekeliling.

16
00:00:45,190 --> 00:00:46,610
Jadi, kita menukar mereka.

17
00:00:46,610 --> 00:00:49,760
Sekarang senarai kelihatan seperti ini: [2, 3, 9, 6, 5].

18
00:00:49,760 --> 00:00:52,450
>> Seterusnya, kita melihat unsur-unsur yang kedua dan ketiga, 3 dan 9.

19
00:00:52,450 --> 00:00:55,770
Mereka berada dalam susunan yang betul relatif kepada satu sama lain.

20
00:00:55,770 --> 00:00:58,800
Iaitu, 3 adalah kurang daripada 9 jadi algoritma tidak menukar mereka.

21
00:00:58,800 --> 00:01:01,900
Seterusnya, kita melihat pada 9 dan 6. Mereka keluar perintah.

22
00:01:01,900 --> 00:01:04,260
>> Jadi, kita perlu untuk menukar mereka kerana 9 adalah lebih besar daripada 6.

23
00:01:04,260 --> 00:01:08,840
Akhir sekali, kita melihat dua integer lepas, 9 dan 5.

24
00:01:08,840 --> 00:01:10,850
Mereka berada di luar perintah, jadi mereka mesti ditukar.

25
00:01:10,850 --> 00:01:13,360
Selepas pas pertama yang lengkap melalui senarai,

26
00:01:13,360 --> 00:01:17,140
ia kelihatan seperti ini: [2, 3, 6, 5, 9].

27
00:01:17,140 --> 00:01:19,690
Not bad. Ia hampir diselesaikan.

28
00:01:19,690 --> 00:01:22,450
Tetapi kita perlu untuk menjalankan melalui senarai sekali lagi untuk mendapatkan ia benar-benar disusun.

29
00:01:22,450 --> 00:01:29,250
Dua adalah kurang daripada 3, jadi kita tidak menukar mereka.

30
00:01:29,250 --> 00:01:31,700
>> Tiga adalah kurang daripada 6, jadi kami tidak menukar mereka.

31
00:01:31,700 --> 00:01:35,500
Enam adalah lebih besar daripada 5. Kami bertukar.

32
00:01:35,500 --> 00:01:38,460
Enam adalah kurang daripada 9. Kami tidak menukar.

33
00:01:38,460 --> 00:01:42,170
Selepas lulus kedua melalui, ia kelihatan seperti ini: [2, 3, 5, 6, 9]. Sempurna.

34
00:01:42,170 --> 00:01:44,680
Sekarang, mari kita menulis dalam pseudokod.

35
00:01:44,680 --> 00:01:48,450
Pada asasnya, untuk setiap elemen dalam senarai, kita perlu melihat ia

36
00:01:48,450 --> 00:01:50,060
dan unsur terus ke kanan.

37
00:01:50,060 --> 00:01:53,420
Jika mereka berada di luar perintah relatif kepada satu sama lain - iaitu, jika unsur di sebelah kiri

38
00:01:53,420 --> 00:01:56,810
adalah lebih besar daripada satu di sebelah kanan - kita harus menukar dua elemen.

39
00:01:56,810 --> 00:02:01,270
>> Kami lakukan ini untuk setiap elemen senarai, dan kita telah membuat satu pas melalui.

40
00:02:01,270 --> 00:02:05,160
Sekarang kita hanya perlu untuk melakukan kali pass-through cukup untuk memastikan senarai

41
00:02:05,160 --> 00:02:06,480
sepenuhnya, disusun dengan betul.

42
00:02:06,480 --> 00:02:08,889
Tetapi berapa kali kita perlu melalui senarai

43
00:02:08,889 --> 00:02:10,400
menjamin bahawa kita sedang dilakukan?

44
00:02:10,400 --> 00:02:14,730
Nah, senario kes terburuk adalah jika kita mempunyai senarai yang sepenuhnya ke belakang.

45
00:02:14,730 --> 00:02:17,840
Kemudian ia mengambil beberapa lulus-lewat sama dengan bilangan

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

47
00:02:19,730 --> 00:02:24,720
Jika ini tidak masuk akal intuitif, berfikir kes mudah - senarai [2, 1].

48
00:02:24,720 --> 00:02:28,430
>> Ini akan mengambil satu pas-melalui untuk menyusun dengan betul.

49
00:02:28,430 --> 00:02:33,060
[3, 2, 1] - kes terburuk adalah bahawa dengan 3 unsur disusun ke belakang,

50
00:02:33,060 --> 00:02:34,830
ia akan mengambil 2 lelaran untuk apapun.

51
00:02:34,830 --> 00:02:37,980
Selepas satu lelaran, [2, 1, 3].

52
00:02:37,980 --> 00:02:39,550
Hasil kedua array disusun [1, 2, 3].

53
00:02:39,550 --> 00:02:43,350
Jadi anda tahu anda tidak perlu pergi melalui pelbagai, secara umum,

54
00:02:43,350 --> 00:02:46,790
lebih daripada n-1 kali, di mana n adalah bilangan elemen dalam array.

55
00:02:47,090 --> 00:02:50,470
Ia dipanggil Disusun sad kerana unsur-unsur terbesar cenderung untuk 'gelembung'

56
00:02:50,470 --> 00:02:51,950
kepada hak yang cantik dengan cepat.

57
00:02:51,950 --> 00:02:53,980
Malah, algoritma ini mempunyai tingkah laku yang sangat menarik.

58
00:02:53,980 --> 00:02:57,410
>> Selepas lelaran m melalui pelbagai keseluruhan,

59
00:02:57,410 --> 00:02:59,000
m paling kanan elemen yang dijamin

60
00:02:59,000 --> 00:03:01,000
akan disusun ke tempat yang betul.

61
00:03:01,000 --> 00:03:02,280
Jika anda mahu melihat ini untuk diri sendiri,

62
00:03:02,280 --> 00:03:05,500
kita boleh cuba ia pada senarai sepenuhnya ke belakang [9, 6, 5, 3, 2].

63
00:03:05,500 --> 00:03:08,220
Selepas satu pas melalui senarai keseluruhan,

64
00:03:08,220 --> 00:03:09,220
[Bunyi bertulis]

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
elemen paling kanan 9 adalah di tempat yang betul.

67
00:03:21,250 --> 00:03:24,760
Selepas kedua pass-through, 6 akan mempunyai 'dipam-up' kepada

68
00:03:24,760 --> 00:03:26,220
tempat kedua paling kanan.

69
00:03:26,220 --> 00:03:28,840
Dua elemen di sebelah kanan - 6 dan 9 - akan berada di tempat yang betul mereka

70
00:03:28,840 --> 00:03:30,580
selepas yang pertama dua pas-lewat.

71
00:03:30,580 --> 00:03:32,590
>> Jadi, bagaimana kita boleh menggunakan ini untuk mengoptimumkan algoritma?

72
00:03:32,590 --> 00:03:34,850
Nah, selepas satu lelaran melalui array

73
00:03:34,850 --> 00:03:37,690
kita sebenarnya tidak perlu untuk memeriksa elemen paling kanan

74
00:03:37,690 --> 00:03:39,200
kerana kita tahu ia diselesaikan.

75
00:03:39,200 --> 00:03:43,050
Selepas dua lelaran, kita tahu pasti dua elemen paling kanan adalah di tempat.

76
00:03:43,050 --> 00:03:48,260
Jadi, secara umum, selepas lelaran k melalui pelbagai penuh,

77
00:03:48,260 --> 00:03:51,550
memeriksa elemen k terakhir adalah berlebihan kerana kita tahu

78
00:03:51,550 --> 00:03:52,360
mereka berada di lokasi yang betul sudah.

79
00:03:52,360 --> 00:03:54,870
>> Jadi, jika anda menyusun pelbagai unsur-unsur n,

80
00:03:54,870 --> 00:03:57,870
pada lelaran pertama - karena perlu menyelesaikan semua elemen - pertama n-0.

81
00:03:57,870 --> 00:04:04,170
Pada lelaran kedua, anda akan perlu melihat semua elemen tetapi lepas -

82
00:04:04,170 --> 00:04:07,090
pertama n-1.

83
00:04:07,090 --> 00:04:10,520
Pengoptimuman lain mungkin untuk memeriksa jika senarai sudah disusun

84
00:04:10,520 --> 00:04:11,710
selepas setiap lelaran.

85
00:04:11,710 --> 00:04:13,900
Jika ia sudah disusun, kita tidak perlu membuat apa-apa lagi lelaran

86
00:04:13,900 --> 00:04:15,310
melalui senarai.

87
00:04:15,310 --> 00:04:16,220
Bagaimana kita boleh melakukan ini?

88
00:04:16,220 --> 00:04:19,360
Nah, jika kita tidak membuat apa-apa pertukaran pada pas-melalui senarai,

89
00:04:19,360 --> 00:04:22,350
ia adalah jelas bahawa senarai itu sudah diselesaikan kerana kami tidak menukar apa-apa.

90
00:04:22,350 --> 00:04:24,160
Jadi, kita pasti tidak perlu untuk menyusun semula.

91
00:04:24,160 --> 00:04:27,960
>> Mungkin anda boleh memulakan pembolehubah bendera dipanggil 'tidak disusun'

92
00:04:27,960 --> 00:04:30,990
palsu dan menukar ia kepada true jika anda mempunyai untuk menukar mana-mana elemen

93
00:04:30,990 --> 00:04:32,290
satu lelaran melalui array.

94
00:04:32,290 --> 00:04:35,350
Atau sama, membuat kaunter untuk mengira berapa banyak swap anda membuat

95
00:04:35,350 --> 00:04:37,040
pada lelaran yang diberikan.

96
00:04:37,040 --> 00:04:40,040
Pada akhir lelaran, jika anda tidak menukar mana-mana elemen,

97
00:04:40,040 --> 00:04:41,780
anda tahu senarai sudah disusun dan anda selesai.

98
00:04:41,780 --> 00:04:44,090
Susun gelembung, seperti algoritma sorting lain, boleh

99
00:04:44,090 --> 00:04:46,960
mengagak untuk bekerja bagi mana-mana elemen yang mempunyai satu kaedah pesanan.

100
00:04:46,960 --> 00:04:50,610
>> Iaitu, diberi dua elemen anda mempunyai cara untuk mengatakan jika yang pertama

101
00:04:50,610 --> 00:04:53,770
adalah lebih besar daripada, sama dengan atau kurang daripada yang kedua.

102
00:04:53,770 --> 00:04:56,870
Sebagai contoh, anda boleh menyusun huruf abjad dengan mengatakan

103
00:04:56,870 --> 00:05:00,520
bahawa <b, b <c, dan lain-lain

104
00:05:00,520 --> 00:05:03,830
Atau anda boleh menyusun hari dalam seminggu di mana hari Ahad adalah kurang daripada Isnin

105
00:05:03,830 --> 00:05:05,110
yang kurang daripada Selasa.

106
00:05:05,110 --> 00:05:09,630
>> Susun Bubble adalah tidak bermakna sorting algoritma yang sangat cekap atau cepat.

107
00:05:09,630 --> 00:05:12,370
Runtime kes terburuk adalah Big O n ²

108
00:05:12,370 --> 00:05:14,810
kerana anda perlu membuat lelaran n melalui senarai

109
00:05:14,810 --> 00:05:18,430
memeriksa semua elemen n setiap pas-melalui, nxn = n ².

110
00:05:18,430 --> 00:05:22,730
Kali ini dijalankan bermakna bahawa sebagai bilangan unsur anda sorting kenaikan,

111
00:05:22,730 --> 00:05:24,330
masa run meningkatkan quadratically.

112
00:05:24,330 --> 00:05:27,330
>> Tetapi jika kecekapan tidak adalah satu kebimbangan utama program anda

113
00:05:27,330 --> 00:05:29,550
atau jika anda hanya sorting sebilangan kecil unsur,

114
00:05:29,550 --> 00:05:31,660
anda mungkin mencari Susun sad berguna kerana

115
00:05:31,660 --> 00:05:33,360
ia adalah salah satu algoritma sorting mudah untuk memahami

116
00:05:33,360 --> 00:05:34,250
dan kod.

117
00:05:34,250 --> 00:05:37,270
Ia juga merupakan cara terbaik untuk mendapatkan pengalaman dengan menterjemahkan teori

118
00:05:37,270 --> 00:05:40,220
algoritma ke dalam kod fungsi sebenar.

119
00:05:40,220 --> 00:05:43,000
Nah, itulah Disusun Bubble untuk anda. Terima kasih kerana menonton.

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