1
00:00:00,000 --> 00:00:03,360
>> [MUSIC PLAYING]

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

3
00:00:04,522 --> 00:00:06,730
Doug LLOYD: Baiklah, jadi
bubble sort adalah sebuah algoritma

4
00:00:06,730 --> 00:00:08,730
Anda dapat menggunakan untuk mengurutkan satu set elemen.

5
00:00:08,730 --> 00:00:10,850
Mari kita lihat cara kerjanya.

6
00:00:10,850 --> 00:00:13,240
>> Jadi ide dasar di balik
bubble sort adalah ini.

7
00:00:13,240 --> 00:00:17,340
Kita umumnya ingin bergerak lebih tinggi
elemen dihargai umumnya ke kanan,

8
00:00:17,340 --> 00:00:20,340
dan menurunkan elemen dihargai umumnya
ke kiri, seperti yang kita harapkan.

9
00:00:20,340 --> 00:00:23,256
Kami menginginkan hal yang lebih rendah berada di
awal, dan hal-hal yang lebih tinggi

10
00:00:23,256 --> 00:00:24,970
berada di akhir.

11
00:00:24,970 --> 00:00:26,130
>> Bagaimana kita melakukan ini?

12
00:00:26,130 --> 00:00:28,040
Nah dalam kode pseudo,
kita bisa mengatakan, mari kita

13
00:00:28,040 --> 00:00:30,320
mengatur counter swap nilai non-nol.

14
00:00:30,320 --> 00:00:32,570
Kami akan melihat mengapa kita melakukan itu dalam satu detik.

15
00:00:32,570 --> 00:00:36,090
Dan kemudian kita mengulang berikut
proses sampai counter swap adalah 0,

16
00:00:36,090 --> 00:00:39,910
atau sampai kami tidak membuat swap sama sekali.

17
00:00:39,910 --> 00:00:43,170
>> Atur ulang swap counter untuk
0 jika tidak sudah 0.

18
00:00:43,170 --> 00:00:46,420
Kemudian melihat setiap
berdekatan sepasang elemen.

19
00:00:46,420 --> 00:00:49,550
Jika kedua unsur adalah
tidak dalam urutan, swap mereka,

20
00:00:49,550 --> 00:00:51,620
dan tambahkan 1 ke counter swap.

21
00:00:51,620 --> 00:00:53,870
Jika Anda berpikir tentang
ini sebelum Anda memvisualisasikan itu,

22
00:00:53,870 --> 00:00:57,471
melihat bahwa ini akan bergerak lebih rendah
elemen dihargai ke kiri

23
00:00:57,471 --> 00:01:00,720
dan lebih tinggi dihargai elemen ke kanan,
efektif melakukan apa yang ingin kita lakukan,

24
00:01:00,720 --> 00:01:03,940
yang bergerak kelompok-kelompok
elemen dengan cara itu.

25
00:01:03,940 --> 00:01:07,035
Mari kita memvisualisasikan bagaimana ini
mungkin terlihat menggunakan array kita

26
00:01:07,035 --> 00:01:10,504
bahwa kita digunakan untuk menguji
out algoritma ini.

27
00:01:10,504 --> 00:01:13,420
Kami memiliki sebuah array disortir di sini lagi,
ditunjukkan oleh semua elemen

28
00:01:13,420 --> 00:01:14,840
menjadi merah.

29
00:01:14,840 --> 00:01:17,970
Dan saya mengatur pertukaran kontra saya
ke nilai nol.

30
00:01:17,970 --> 00:01:20,610
Aku sewenang-wenang memilih
negatif 1-- itu tidak 0.

31
00:01:20,610 --> 00:01:23,840
Kami ingin mengulang proses ini
sampai counter swap adalah 0.

32
00:01:23,840 --> 00:01:26,540
Ini adalah mengapa saya mengatur swap
counter untuk beberapa nilai bukan nol,

33
00:01:26,540 --> 00:01:29,400
karena jika tidak
Swap kontra akan 0.

34
00:01:29,400 --> 00:01:31,610
Kita bahkan tidak akan memulai
proses algoritma.

35
00:01:31,610 --> 00:01:33,610
Jadi sekali lagi, langkah-langkah are--
reset counter Swap

36
00:01:33,610 --> 00:01:37,900
ke 0, kemudian melihat setiap berdekatan
Pasangan, dan jika mereka rusak,

37
00:01:37,900 --> 00:01:40,514
swap mereka, dan menambahkan 1
ke counter swap.

38
00:01:40,514 --> 00:01:41,680
Jadi mari kita mulai proses ini.

39
00:01:41,680 --> 00:01:44,430
Jadi hal pertama yang kita lakukan adalah
kita mengatur meja swap 0,

40
00:01:44,430 --> 00:01:46,660
dan kemudian kami mulai mencari
di setiap pasangan yang berdekatan.

41
00:01:46,660 --> 00:01:49,140
>> Jadi pertama-tama kita mulai melihat 5 dan 2.

42
00:01:49,140 --> 00:01:52,410
Kami melihat bahwa mereka berada di luar
memesan dan jadi kami swap mereka.

43
00:01:52,410 --> 00:01:53,830
Dan kita menambahkan 1 ke counter swap.

44
00:01:53,830 --> 00:01:57,860
Jadi sekarang Swap counter kami adalah 1,
dan 2 dan 5 telah beralih.

45
00:01:57,860 --> 00:01:59,370
Sekarang kita ulangi proses lagi.

46
00:01:59,370 --> 00:02:03,540
>> Kami melihat pasangan yang berdekatan berikutnya,
5 dan 1-- mereka juga rusak,

47
00:02:03,540 --> 00:02:06,960
jadi kami swap mereka dan menambahkan
1 ke counter swap.

48
00:02:06,960 --> 00:02:08,900
Kemudian kita melihat 5 dan 3.

49
00:02:08,900 --> 00:02:13,830
Mereka rusak, jadi kami bertukar
mereka dan kita tambahkan 1 ke counter swap.

50
00:02:13,830 --> 00:02:15,550
Kemudian kita melihat 5 dan 6.

51
00:02:15,550 --> 00:02:18,630
Mereka berada di urutan, jadi kita tidak benar-benar
perlu menukar apapun saat ini.

52
00:02:18,630 --> 00:02:20,250
Kemudian kita melihat 6 dan 4.

53
00:02:20,250 --> 00:02:24,920
Mereka juga sudah rusak, jadi kami bertukar
mereka dan kita tambahkan 1 ke counter swap.

54
00:02:24,920 --> 00:02:26,230
>> Sekarang perhatikan apa yang terjadi.

55
00:02:26,230 --> 00:02:29,514
Kami sudah pindah 6 sampai ke akhir.

56
00:02:29,514 --> 00:02:32,180
Jadi dalam pemilihan semacam, jika Anda sudah
melihat video itu, apa yang kita lakukan adalah

57
00:02:32,180 --> 00:02:35,290
kami akhirnya memindahkan
elemen terkecil di gedung

58
00:02:35,290 --> 00:02:39,640
array diurutkan dasarnya dari
kiri ke kanan, terkecil hingga terbesar.

59
00:02:39,640 --> 00:02:43,200
Dalam kasus semacam gelembung, jika kita
Berikut algoritma tertentu,

60
00:02:43,200 --> 00:02:46,720
kita benar-benar akan membangun
array diurutkan dari kanan

61
00:02:46,720 --> 00:02:49,100
ke kiri, terbesar ke terkecil.

62
00:02:49,100 --> 00:02:53,840
Kami telah efektif menggelegak 6, yang
nilai terbesar, semua jalan sampai akhir.

63
00:02:53,840 --> 00:02:56,165
>> Dan kita sekarang dapat mendeklarasikan
bahwa yang diurutkan,

64
00:02:56,165 --> 00:02:59,130
dan di masa depan iterations--
melalui array again--

65
00:02:59,130 --> 00:03:01,280
kita tidak harus mempertimbangkan 6 lagi.

66
00:03:01,280 --> 00:03:03,850
Kami hanya harus mempertimbangkan
elemen disortir

67
00:03:03,850 --> 00:03:06,299
ketika kita sedang melihat pasangan yang berdekatan.

68
00:03:06,299 --> 00:03:08,340
Jadi kita telah selesai satu
melewati bubble sort.

69
00:03:08,340 --> 00:03:11,941
Jadi sekarang kita kembali ke pertanyaan,
ulangi sampai counter swap adalah 0.

70
00:03:11,941 --> 00:03:13,690
Nah counter Swap
adalah 4, jadi kita akan

71
00:03:13,690 --> 00:03:15,410
terus mengulangi proses ini lagi.

72
00:03:15,410 --> 00:03:19,180
>> Kita akan me-reset counter Swap
dengan 0, dan melihat setiap pasangan yang berdekatan.

73
00:03:19,180 --> 00:03:21,890
Jadi kita mulai dengan 2 dan 1-- mereka
rusak, jadi kami swap mereka

74
00:03:21,890 --> 00:03:23,620
dan kita tambahkan 1 ke counter swap.

75
00:03:23,620 --> 00:03:25,490
2 dan 3, mereka dalam rangka.

76
00:03:25,490 --> 00:03:27,060
Kita tidak perlu melakukan apa-apa.

77
00:03:27,060 --> 00:03:28,420
3 dan 5 adalah dalam rangka.

78
00:03:28,420 --> 00:03:30,150
Kita tidak perlu melakukan apa-apa di sana.

79
00:03:30,150 --> 00:03:32,515
>> 5 dan 4, mereka berada di luar
ketertiban, dan jadi kami

80
00:03:32,515 --> 00:03:35,130
perlu swap mereka dan menambahkan
1 ke counter swap.

81
00:03:35,130 --> 00:03:38,880
Dan sekarang kita sudah pindah 5,
elemen terbesar berikutnya,

82
00:03:38,880 --> 00:03:40,920
ke ujung bagian yang tidak dipisahkan.

83
00:03:40,920 --> 00:03:44,360
Jadi sekarang kita bisa menyebutnya
bagian dari bagian diurutkan.

84
00:03:44,360 --> 00:03:47,180
>> Sekarang Anda melihat
layar dan mungkin bisa mengatakan,

85
00:03:47,180 --> 00:03:50,130
seperti dapat saya, bahwa array
diurutkan sekarang.

86
00:03:50,130 --> 00:03:51,820
Tapi kita tidak bisa membuktikan bahwa belum.

87
00:03:51,820 --> 00:03:54,359
Kami tidak memiliki jaminan
bahwa itu diurutkan.

88
00:03:54,359 --> 00:03:56,900
Tapi ini adalah di mana swap
kontra akan ikut bermain.

89
00:03:56,900 --> 00:03:59,060
>> Jadi kami telah menyelesaikan lulus.

90
00:03:59,060 --> 00:04:00,357
Swap counter 2.

91
00:04:00,357 --> 00:04:02,190
Jadi kita akan mengulangi
Proses ini lagi,

92
00:04:02,190 --> 00:04:04,290
ulangi sampai counter swap adalah 0.

93
00:04:04,290 --> 00:04:05,550
Reset counter swap 0.

94
00:04:05,550 --> 00:04:06,820
Jadi kita akan me-reset.

95
00:04:06,820 --> 00:04:09,810
>> Sekarang lihat setiap pasangan yang berdekatan.

96
00:04:09,810 --> 00:04:11,880
Itu dalam rangka, 1 dan 2.

97
00:04:11,880 --> 00:04:13,590
2 dan 3 adalah dalam rangka.

98
00:04:13,590 --> 00:04:15,010
3 dan 4 adalah dalam rangka.

99
00:04:15,010 --> 00:04:19,250
Jadi pada titik ini, melihat kami sudah selesai
melihat setiap pasangan yang berdekatan,

100
00:04:19,250 --> 00:04:22,530
tapi counter swap adalah masih 0.

101
00:04:22,530 --> 00:04:25,520
>> Jika kita tidak perlu beralih
setiap elemen, maka mereka

102
00:04:25,520 --> 00:04:28,340
harus dalam rangka, oleh
kebajikan dari proses ini.

103
00:04:28,340 --> 00:04:32,000
Dan efisiensi macam,
bahwa para ilmuwan kita cintai komputer,

104
00:04:32,000 --> 00:04:35,560
sekarang kita dapat mendeklarasikan
seluruh array harus

105
00:04:35,560 --> 00:04:38,160
diurutkan, karena kita tidak
harus menukar elemen.

106
00:04:38,160 --> 00:04:40,380
Itu cukup bagus.

107
00:04:40,380 --> 00:04:43,260
>> Jadi apa kasus terburuk
Skenario dengan bubble sort?

108
00:04:43,260 --> 00:04:46,240
Dalam kasus terburuk array adalah
dalam rangka benar-benar terbalik,

109
00:04:46,240 --> 00:04:49,870
dan jadi kita harus gelembung setiap
dari unsur-unsur besar semua

110
00:04:49,870 --> 00:04:51,780
jalan melintasi array.

111
00:04:51,780 --> 00:04:55,350
Dan kita juga harus efektif
gelembung semua elemen kecil kembali

112
00:04:55,350 --> 00:04:57,050
semua jalan melintasi array, juga.

113
00:04:57,050 --> 00:05:01,950
Jadi masing-masing elemen n harus bergerak
di semua elemen n lainnya.

114
00:05:01,950 --> 00:05:04,102
Jadi itulah skenario terburuk.

115
00:05:04,102 --> 00:05:05,810
Dalam kasus terbaik
skenario walaupun, ini adalah

116
00:05:05,810 --> 00:05:07,880
sedikit berbeda dari pemilihan semacam.

117
00:05:07,880 --> 00:05:10,040
Array sudah
diurutkan ketika kita masuk.

118
00:05:10,040 --> 00:05:12,550
Kami tidak perlu membuat
swap pada lulus pertama.

119
00:05:12,550 --> 00:05:14,940
Jadi kita mungkin harus melihat
di elemen yang lebih sedikit, kan?

120
00:05:14,940 --> 00:05:18,580
Kami tidak perlu mengulangi ini
memproses beberapa kali lebih.

121
00:05:18,580 --> 00:05:19,540
>> Jadi apa artinya?

122
00:05:19,540 --> 00:05:22,390
Jadi apa skenario terburuk
untuk bubble sort, dan apa

123
00:05:22,390 --> 00:05:25,330
skenario kasus terbaik untuk bubble sort?

124
00:05:25,330 --> 00:05:27,770
Apakah Anda kira ini?

125
00:05:27,770 --> 00:05:32,420
Dalam kasus terburuk Anda harus iterate
di semua elemen n n kali.

126
00:05:32,420 --> 00:05:34,220
Jadi kasus terburuk adalah n kuadrat.

127
00:05:34,220 --> 00:05:36,550
>> Jika array adalah sempurna
diurutkan meskipun, Anda hanya

128
00:05:36,550 --> 00:05:38,580
harus melihat setiap
elemen sekali.

129
00:05:38,580 --> 00:05:42,670
Dan jika counter swap adalah masih 0,
Anda bisa mengatakan array ini diurutkan.

130
00:05:42,670 --> 00:05:45,780
Dan dalam kasus terbaik, ini adalah
sebenarnya lebih baik dari pilihan

131
00:05:45,780 --> 00:05:49,230
sort-- itu omega dari n.

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

133
00:05:50,270 --> 00:05:52,140
Ini adalah CS50.

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