1
00:00:00,500 --> 00:00:02,840
[Powered by Google Translate] [バブルソート]

2
00:00:02,840 --> 00:00:04,560
[ジャクソンSTEINKAMPハーバード大学]

3
00:00:04,560 --> 00:00:07,500
[これはCS50です。 CS50TV]

4
00:00:08,000 --> 00:00:11,730
バブルソートは、ソートアルゴリズムの一例である - 

5
00:00:11,730 --> 00:00:14,460
それは、内の要素のセットをソートするための手順です

6
00:00:14,460 --> 00:00:15,840
昇順または降順。

7
00:00:15,840 --> 00:00:18,710
例えば、あなたが数字から成る配列をソートしたい場合

8
00:00:18,710 --> 00:00:23,060
[3、5、2、9]、バブルソートの正しい実装では、戻ってくる

9
00:00:23,060 --> 00:00:26,260
ソートされた配列[2、3、5、9]を昇順インチ

10
00:00:26,260 --> 00:00:28,850
今、私は、このアルゴリズムがどのように動作するかを擬似コードで説明するつもりです。

11
00:00:28,850 --> 00:00:34,000
>> 3、2、9、6、5  - レッツは、我々は5つの整数のリストをソートしていると言う。

12
00:00:34,000 --> 00:00:37,650
アルゴリズムは、最初の二つの要素、3と2を見て、開始

13
00:00:37,650 --> 00:00:40,850
彼らは互いに相対的順序を外れているのであればチェックする。

14
00:00:40,850 --> 00:00:43,150
彼らは -  3は2より大きい。

15
00:00:43,150 --> 00:00:45,190
昇順になっているために、彼らは他の方法で回避する必要があります。

16
00:00:45,190 --> 00:00:46,610
そこで、我々はそれらを交換。

17
00:00:46,610 --> 00:00:49,760
[2、3、9、6、5]：今のリストは、このように見えます。

18
00:00:49,760 --> 00:00:52,450
>> 次に、我々は2番目と3番目の要素は、3と9を見てください。

19
00:00:52,450 --> 00:00:55,770
彼らは互いに相対的に正しい順番にしている。

20
00:00:55,770 --> 00:00:58,800
アルゴリズムでは、それらを交換していません9未満でそうなっていることを、3である。

21
00:00:58,800 --> 00:01:01,900
次に、我々は9と6を見てください。彼らは順不同だ。

22
00:01:01,900 --> 00:01:04,260
>> だから、私たちは9が6よりも大きいので、それらを交換する必要があります。

23
00:01:04,260 --> 00:01:08,840
最後に、我々は最後の2つの整数、9と5を見てください。

24
00:01:08,840 --> 00:01:10,850
彼らは、順不同でいるので、彼らはスワップする必要があります。

25
00:01:10,850 --> 00:01:13,360
リストを通して最初の完全なパスの後、

26
00:01:13,360 --> 00:01:17,140
それはこのようになります：[2、3、6、5、9]。

27
00:01:17,140 --> 00:01:19,690
悪くない。これは、ほぼソートされている。

28
00:01:19,690 --> 00:01:22,450
しかし、我々はそれが完全にソートされた取得するために再度リストを介して実行する必要があります。

29
00:01:22,450 --> 00:01:29,250
二人は3未満であるので、我々はそれらを交換しないでください。

30
00:01:29,250 --> 00:01:31,700
>> 三つは、6未満であるので、我々はそれらを交換しないでください。

31
00:01:31,700 --> 00:01:35,500
シックスは5より大きい。我々は、交換しました。

32
00:01:35,500 --> 00:01:38,460
シックスは9未満である。我々はスワップしません。

33
00:01:38,460 --> 00:01:42,170
の2回目のパスの後、それは次のようになります[2、3、5、6、9]。パーフェクト。

34
00:01:42,170 --> 00:01:44,680
さて、擬似コードで書いてみましょう。

35
00:01:44,680 --> 00:01:48,450
基本的には、リスト内の各要素に対して、我々はそれを見る必要がある

36
00:01:48,450 --> 00:01:50,060
そして直接その右にある要素。

37
00:01:50,060 --> 00:01:53,420
彼らは互いに相対的順序が一致していない場合 - つまり、左側の要素なら

38
00:01:53,420 --> 00:01:56,810
右側の1を超えている - 私たちは2つの要素を交換してください。

39
00:01:56,810 --> 00:02:01,270
>> 我々は、リストのすべての要素のためにこれを行うには、我々は一つの通過を作りました。

40
00:02:01,270 --> 00:02:05,160
今、私たちは、単にリストを確実にするためにパススルー十分な回数を行う必要が

41
00:02:05,160 --> 00:02:06,480
完全に、正しくソートされます。

42
00:02:06,480 --> 00:02:08,889
しかし、我々はリストに通過する方法を何回も持っている

43
00:02:08,889 --> 00:02:10,400
我々がやっていることを保証するものでは？

44
00:02:10,400 --> 00:02:14,730
我々は完全に後方にリストを持っている場合だけでなく、最悪のシナリオです。

45
00:02:14,730 --> 00:02:17,840
それは数に等しいパススルーの数を取り

46
00:02:17,840 --> 00:02:19,730
要素がn-1の。

47
00:02:19,730 --> 00:02:24,720
これは直感的に意味をなさない場合は、単純な例だと思う - リスト[2,1]。

48
00:02:24,720 --> 00:02:28,430
>> これは正しくソートするために1パススルーかかるとしている。

49
00:02:28,430 --> 00:02:33,060
[3、2、1]  - 最悪の場合、3つの要素で逆方向にソートすることです

50
00:02:33,060 --> 00:02:34,830
それは、ソートに2回の反復を取るつもりです。

51
00:02:34,830 --> 00:02:37,980
1反復後に、それが[2、1、3]です。

52
00:02:37,980 --> 00:02:39,550
第二利回りソートされた配列[1、2、3]。

53
00:02:39,550 --> 00:02:43,350
だからあなたが一般的には、配列を経由する必要はありません知っている、

54
00:02:43,350 --> 00:02:46,790
nは配列内の要素の数はn-1回、より。

55
00:02:47,090 --> 00:02:50,470
最大の要素は "バブルアップ"する傾向があるので、それはバブルソートと呼ばれています

56
00:02:50,470 --> 00:02:51,950
かなりのスピードで右へ。

57
00:02:51,950 --> 00:02:53,980
実際には、このアルゴリズムは非常に興味深い挙動を持っています。

58
00:02:53,980 --> 00:02:57,410
>> 配列全体を通してメートルの繰り返しの後、

59
00:02:57,410 --> 00:02:59,000
右端のm要素が保証されています

60
00:02:59,000 --> 00:03:01,000
自分たちが正しい場所に並べ替えることができます。

61
00:03:01,000 --> 00:03:02,280
あなたは、あなた自身のためにこれを確認したい場合

62
00:03:02,280 --> 00:03:05,500
我々は完全に後方にリスト[9、6、5、3、2]でそれを試すことができます。

63
00:03:05,500 --> 00:03:08,220
リスト全体を1回通過した後、

64
00:03:08,220 --> 00:03:09,220
[書き込みの音]

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
右端の要素9は、その適切な場所にあります。

67
00:03:21,250 --> 00:03:24,760
パススルー秒後、6 'バブリングアップ "しなければならないでしょう

68
00:03:24,760 --> 00:03:26,220
右端から2番目の場所。

69
00:03:26,220 --> 00:03:28,840
6と9  -   - 右側にある2つの要素は、自分たちが正しい場所になります

70
00:03:28,840 --> 00:03:30,580
最初の二つのパススルー後。

71
00:03:30,580 --> 00:03:32,590
>> ですから、どのように我々は、アルゴリズムを最適化するために、これを使用することができますか？

72
00:03:32,590 --> 00:03:34,850
さて、配列を介して1つの反復の後

73
00:03:34,850 --> 00:03:37,690
私たちは実際に右端の要素をチェックする必要はありません

74
00:03:37,690 --> 00:03:39,200
私たちが知っているので、それはソートだ。

75
00:03:39,200 --> 00:03:43,050
2回繰り返した後、我々は、右端の2つの要素が整っている確かに知っている。

76
00:03:43,050 --> 00:03:48,260
だから、一般的には、k回反復した後の完全な配列を介して、

77
00:03:48,260 --> 00:03:51,550
私たちが知っているので、最後のk個の要素をチェックすることは冗長である

78
00:03:51,550 --> 00:03:52,360
彼らはすでに正しい場所にいる。

79
00:03:52,360 --> 00:03:54,870
>> ですから、n個の要素の配列をソートしている場合、

80
00:03:54,870 --> 00:03:57,870
最初の反復で - 最初のn-0  -  you'llは、すべての要素をソートする必要があります。

81
00:03:57,870 --> 00:04:04,170
2回目の反復では、すべての要素が、最後を見てみなければならないでしょう - 

82
00:04:04,170 --> 00:04:07,090
最初のn-1。

83
00:04:07,090 --> 00:04:10,520
もう1つの最適化リストが既にソートされているかどうかを確認することであるかもしれません

84
00:04:10,520 --> 00:04:11,710
各反復後。

85
00:04:11,710 --> 00:04:13,900
それが既にソートされている場合、我々はそれ以上の反復を行う必要はありません

86
00:04:13,900 --> 00:04:15,310
リストをスクロール。

87
00:04:15,310 --> 00:04:16,220
どのように我々はこれを行うことができますか？

88
00:04:16,220 --> 00:04:19,360
まあ、我々はリストのパススルー上の任意のスワップを行わない場合、

89
00:04:19,360 --> 00:04:22,350
それは我々が何を交換しなかったため、リストが既にソートされていることは明らかです。

90
00:04:22,350 --> 00:04:24,160
だから我々は間違いなく、再びソートする必要はありません。

91
00:04:24,160 --> 00:04:27,960
>> おそらく、あなたがに "ソートされていない 'と呼ばれるフラグ変数を初期化することができ

92
00:04:27,960 --> 00:04:30,990
あなたは上の任意の要素をスワップする必要がある場合はfalseとtrueに変更

93
00:04:30,990 --> 00:04:32,290
配列を介して1つの繰り返し。

94
00:04:32,290 --> 00:04:35,350
または同様に、あなたが作るどのように多くのスワップをカウントするカウンタを作る

95
00:04:35,350 --> 00:04:37,040
任意の反復で。

96
00:04:37,040 --> 00:04:40,040
、イテレーションの終わりには、要素のいずれかを交換しなかった場合

97
00:04:40,040 --> 00:04:41,780
あなたは、リストが既にソートされて、作業が終わっている知っている。

98
00:04:41,780 --> 00:04:44,090
バブルソートは、他のソートアルゴリズムのように、することができます

99
00:04:44,090 --> 00:04:46,960
順序付けメソッドを持つすべての要素のために働くために微調整。

100
00:04:46,960 --> 00:04:50,610
>> それはあなたの最初の1つが言う方法を持つ2つの要素を考えると、ある

101
00:04:50,610 --> 00:04:53,770
に等しいか、または秒未満、より大きい。

102
00:04:53,770 --> 00:04:56,870
例えば、あなたが言ってアルファベットの文字を並べ替えることができ

103
00:04:56,870 --> 00:05:00,520
その<B、B <cなど

104
00:05:00,520 --> 00:05:03,830
日曜日は月曜日未満であるか、曜日を並べ替えることができ

105
00:05:03,830 --> 00:05:05,110
これは火曜日未満です。

106
00:05:05,110 --> 00:05:09,630
>> バブルソートは、非常に効率的なまたは速いソートアルゴリズムを意味するものではまったくない。

107
00:05:09,630 --> 00:05:12,370
その最悪の場合のランタイムがnのビッグOである²

108
00:05:12,370 --> 00:05:14,810
あなたは、リストをn回の反復をしなければならないので、

109
00:05:14,810 --> 00:05:18,430
すべてのn個の要素をチェックして各nxnの、パススルー= nの²。

110
00:05:18,430 --> 00:05:22,730
この実行時間は要素数のように、増加を選別していることを意味します

111
00:05:22,730 --> 00:05:24,330
ランタイムは二次関数的に増加します。

112
00:05:24,330 --> 00:05:27,330
>> しかし、効率がプログラムの主要な関心事ではない場合

113
00:05:27,330 --> 00:05:29,550
またはあなただけの少数の要素をソートしている場合、

114
00:05:29,550 --> 00:05:31,660
あなたはバブルソートが便利な場合もありますので、

115
00:05:31,660 --> 00:05:33,360
それは理解することが最も簡単なソートアルゴリズムの一つだ

116
00:05:33,360 --> 00:05:34,250
とコードに。

117
00:05:34,250 --> 00:05:37,270
また、理論の翻訳の経験を得るための素晴らしい方法です

118
00:05:37,270 --> 00:05:40,220
実際の機能コードに変換アルゴリズム。

119
00:05:40,220 --> 00:05:43,000
まあ、それはあなたのためのバブルソートです。見てくれてありがとう。

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