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 لويد: كل الحق، لذلك
فقاعة النوع هو خوارزمية

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
إذا كانت هذه العناصر هما
ليس في النظام، ومقايضتهم،

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
وبذلك نكون قد أنهى واحدة
تمر عبر فقاعة النوع.

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
حتى نبدأ مع 2 و 1-- انهم
من النظام، لذلك نحن مقايضتهم

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
لذلك كل من العناصر ن أن تتحرك
عبر كل من العناصر غيرها ن.

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
في أسوأ حال كان لديك لتكرار
في جميع العناصر ن ن مرات.

126
00:05:32,420 --> 00:05:34,220
لذلك ن تربيع أسوأ الحالات.

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
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