1
00:00:00,500 --> 00:00:02,840
[Powered by Google Translate] [ترتيب BUBBLE]

2
00:00:02,840 --> 00:00:04,560
[JACKSON 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
>> دعونا نقول اننا فرز قائمة أعداد صحيحة من 5 - 3، 2، 9، 6، و 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
>> المقبل، ونحن ننظر إلى العناصر الثانية والثالثة و 3 و 9.

19
00:00:52,450 --> 00:00:55,770
انهم في الترتيب الصحيح بالنسبة لبعضها البعض.

20
00:00:55,770 --> 00:00:58,800
وهذا هو، 3 هو أقل من 9 حتى الخوارزمية لا مقايضتهم.

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
وأخيرا، فإننا ننظر إلى أعداد صحيحة الماضيين، 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، 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
أكبر من واحد على حق - يجب علينا مبادلة العنصرين.

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
>> هذا هو الذهاب الى اتخاذ مرور واحد من خلال لفرز بشكل صحيح.

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
بعد واحد التكرار، انها [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-1 مرات، حيث n هو عدد العناصر في الصفيف.

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
ويضمن أقصى اليمين عناصر م

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
بعد مرور واحد من خلال القائمة بأكملها،

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
أقصى اليمين المركز الثاني.

69
00:03:26,220 --> 00:03:28,840
العناصر اثنين على اليمنى - 6 و 9 - سيكون في أماكنهم الصحيحة

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
حسنا، بعد واحدة تكرار من خلال مجموعة

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

76
00:03:43,050 --> 00:03:48,260
لذلك، بشكل عام، بعد تكرار ك من خلال مجموعة كاملة،

77
00:03:48,260 --> 00:03:51,550
التحقق من العناصر ك مشاركة لا لزوم لها لأننا نعرف

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
على التكرار الأول - اختر مربع الطباعة أن ترتب كل العناصر - أول ن-0.

81
00:03:57,870 --> 00:04:04,170
على التكرار الثاني، سيكون لديك للنظر في جميع العناصر ولكن الماضي -

82
00:04:04,170 --> 00:04:07,090
أول N-1.

83
00:04:07,090 --> 00:04:10,520
قد يكون الأمثل أخرى للتحقق مما إذا تم فرزها بالفعل قائمة

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
كاذبة وتغييره إلى 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
>> وهذا هو، نظرا عنصرين لديك وسيلة لقول ما اذا الأول

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
أن <ب، ب <ج، الخ.

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
في أسوأ الحالات وقت كبير O ² ن

108
00:05:12,370 --> 00:05:14,810
لأن لديك لجعل التكرار ن خلال قائمة

109
00:05:14,810 --> 00:05:18,430
التحقق من جميع العناصر ن كل تمريري، nxn = ن ².

110
00:05:18,430 --> 00:05:22,730
هذا يعني أن وقت التشغيل حيث وصل عدد من العناصر كنت الفرز الزيادات،

111
00:05:22,730 --> 00:05:24,330
وقت التشغيل يزيد quadratically.

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