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：すべての権利なので、
バブルソートアルゴリズムであります

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
>> だから、基本的な考え方の背後にあります
バブルソートはこれです。

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
まあ擬似コードコードで、
我々はしてみましょう、と言うことができます

13
00:00:28,040 --> 00:00:30,320
ゼロ以外の値にスワップカウンターを設定します。

14
00:00:30,320 --> 00:00:32,570
私たちは第二にそれを行う理由当社は、表示されます。

15
00:00:32,570 --> 00:00:36,090
そして、我々は、以下を繰り返します
スワップカウンタが0になるまでのプロセス、

16
00:00:36,090 --> 00:00:39,910
または私達はまったくスワップを行うことなくなるまで。

17
00:00:39,910 --> 00:00:43,170
>> へのスワップカウンターをリセット
0それはまだ0ではない場合。

18
00:00:43,170 --> 00:00:46,420
そして、すべてのを見て
隣接する要素のペア。

19
00:00:46,420 --> 00:00:49,550
これらの2つの要素がある場合
ないために、それらを交換し、

20
00:00:49,550 --> 00:00:51,620
スワップカウンターに1を加えます。

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
そして、私はスワップカウンターを設定
ゼロ以外の値に設定します。

30
00:01:17,970 --> 00:01:20,610
私は任意に選びました
負1--それは0ではありません。

31
00:01:20,610 --> 00:01:23,840
我々は、このプロセスを繰り返したいです
スワップカウンターまで0です。

32
00:01:23,840 --> 00:01:26,540
私はスワップを設定する理由はここにあります
いくつかの非ゼロ値にカウンタ、

33
00:01:26,540 --> 00:01:29,400
なぜならそうでなければ
スワップカウンターは0になります。

34
00:01:29,400 --> 00:01:31,610
私たちも開始しません
アルゴリズムのプロセス。

35
00:01:31,610 --> 00:01:33,610
だから、再び、ステップはare--
スワップカウンターをリセット

36
00:01:33,610 --> 00:01:37,900
0にし、すべての隣接を見て
ペア、および彼らが故障している場合は、

37
00:01:37,900 --> 00:01:40,514
それらを交換し、1を追加
スワップカウンターへ。

38
00:01:40,514 --> 00:01:41,680
それでは、このプロセスを開始しましょう​​。

39
00:01:41,680 --> 00:01:44,430
だから、まず最初にすることです
私たちは、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を加えます。

44
00:01:53,830 --> 00:01:57,860
だから今、私たちのスワップカウンターが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。

48
00:02:06,960 --> 00:02:08,900
その後、我々は5と3を見てください。

49
00:02:08,900 --> 00:02:13,830
彼らは順不同であるので、交換します
彼らと私たちは、スワップカウンターに1を加えます。

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を加えます。

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
バブルソートの場合は、私たちがしている場合
この特定のアルゴリズムに従って、

60
00:02:43,200 --> 00:02:46,720
私たちは実際に構築することになるだろう
右からソートされた配列

61
00:02:46,720 --> 00:02:49,100
左に、最大最小に。

62
00:02:49,100 --> 00:02:53,840
我々は、6を効果的にバブリングしています
最大値、最後にすべての方法。

63
00:02:53,840 --> 00:02:56,165
>> そして、私たちは今宣言することができます
それは、ソートされていること、

64
00:02:56,165 --> 00:02:59,130
将来的にiterations--
配列を通過again--

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
だから我々は1を終えました
バブルソートを通過します。

69
00:03:08,340 --> 00:03:11,941
だから今、私たちが質問に戻って、
スワップカウンタが0になるまで繰り返します。

70
00:03:11,941 --> 00:03:13,690
まあスワップカウンター
4であるので、我々はつもりです

71
00:03:13,690 --> 00:03:15,410
再度このプロセスを繰り返し続けることができます。

72
00:03:15,410 --> 00:03:19,180
>> 私たちは、スワップカウンターをリセットしようとしています
0にし、各隣接ペアを見てください。

73
00:03:19,180 --> 00:03:21,890
だから我々は、彼らがしている1-- 2で始まり、
順不同で、私たちはそれらを交換

74
00:03:21,890 --> 00:03:23,620
私たちは、スワップカウンターに1を加えます。

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。

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
しかし、これはどこにスワップです
カウンタは、遊びに来て起こっています。

89
00:03:56,900 --> 00:03:59,060
>> だから我々は、パスを完了しました。

90
00:03:59,060 --> 00:04:00,357
スワップカウンターは2です。

91
00:04:00,357 --> 00:04:02,190
だから我々は、繰り返しになるだろう
このプロセスを再度、

92
00:04:02,190 --> 00:04:04,290
スワップカウンタが0になるまで繰り返します。

93
00:04:04,290 --> 00:04:05,550
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
しかし、スワップカウンターはまだ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
そして、我々は効果的にも持っています
バブル小さな要素のすべてのバック

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
だから、最悪のシナリオは何ですか
バブルソート、何のために

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
最悪のケースでは、反復処理する必要があります
すべての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
スワップカウンターがまだ0である場合、
あなたは、この配列がソートされていると言うことができます。

130
00:05:42,670 --> 00:05:45,780
だから最良の場合には、これは
選択よりも、実際に良いです

131
00:05:45,780 --> 00:05:49,230
それは、nのオメガのsort--。

132
00:05:49,230 --> 00:05:50,270
>> 私はダグロイドです。

133
00:05:50,270 --> 00:05:52,140
これはCS50です。

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