1
00:00:00,000 --> 00:00:02,290
[Powered by Google Translate] [ترتيب الإدراج]

2
00:00:02,290 --> 00:00:04,240
[تومي MacWilliam] [جامعة هارفارد]

3
00:00:04,240 --> 00:00:07,290
[هذا CS50.TV]

4
00:00:07,290 --> 00:00:13,060
دعونا نلقي نظرة على نوع الإدراج، خوارزمية لاتخاذ قائمة الأرقام والفرز لهم.

5
00:00:13,060 --> 00:00:18,300
خوارزمية، تذكر، هو مجرد إجراء خطوة بخطوة لإنجاز المهمة.

6
00:00:18,300 --> 00:00:23,640
الفكرة الأساسية وراء نوع الإدراج، هو تقسيم قائمتنا إلى جزئين،

7
00:00:23,640 --> 00:00:26,580
جزء مصنفة وجزء لم يتم فرزها.

8
00:00:26,580 --> 00:00:29,290
>> في كل خطوة من خطوات الخوارزمية، يتم نقل عدد

9
00:00:29,290 --> 00:00:32,439
لم يتم فرزها من الجزء إلى الجزء مصنفة

10
00:00:32,439 --> 00:00:35,680
حتى في نهاية المطاف يتم فرز القائمة بأكملها.

11
00:00:35,680 --> 00:00:43,340
ستجد هنا لائحة من ستة أرقام لم يتم فرزها - 23، 42، 4، 16، 8، و 15.

12
00:00:43,340 --> 00:00:47,680
وبما أن هذه الأرقام ليست كل شيء في ترتيب تصاعدي، لم يتم فرزها كنت فيها.

13
00:00:47,680 --> 00:00:53,890
لأننا لم نبدأ بعد الفرز، نحن سنعتبر جميع العناصر الستة لدينا جزء لم يتم فرزها.

14
00:00:53,890 --> 00:00:59,270
>> مرة واحدة نبدأ الفرز، وسوف نضع هذه الأرقام مصنفة على يسار هذه.

15
00:00:59,270 --> 00:01:03,600
لذلك، دعونا نبدأ مع 23، العنصر الأول في قائمتنا.

16
00:01:03,600 --> 00:01:06,930
ليس لدينا أي عناصر في جزء دينا مصنفة حتى الآن،

17
00:01:06,930 --> 00:01:12,460
لذلك دعونا النظر ببساطة 23 إلى تكون بداية ونهاية الجزء دينا فرزها.

18
00:01:12,460 --> 00:01:16,510
الآن، لدينا فرز جزء واحد عدد (23 عاما)

19
00:01:16,510 --> 00:01:20,260
والتي لم يتم فرزها لديه جزء دينا هذه الأرقام الخمسة.

20
00:01:20,260 --> 00:01:27,320
دعونا الآن إدراج الرقم التالي في جزء لدينا لم يتم فرزها، 42 عاما، في الجزء فرزها.

21
00:01:27,320 --> 00:01:35,930
>> للقيام بذلك، سنحتاج إلى مقارنة 42 إلى ال 23 - العنصر الوحيد في جزء دينا مصنفة حتى الآن.

22
00:01:35,930 --> 00:01:41,980
اثنين وأربعين أكبر من 23، حتى نتمكن من إلحاق ببساطة من 42 إلى نهاية

23
00:01:41,980 --> 00:01:45,420
من الجزء مصنفة من القائمة. عظيم!

24
00:01:45,420 --> 00:01:51,850
الآن لدينا جزء اثنين من عناصر مصنفة، والتي لم يتم فرزها لدينا جزء من أربعة عناصر.

25
00:01:51,850 --> 00:01:57,200
لذلك، دعنا ننتقل الآن إلى 4، العنصر التالي في جزء لم يتم فرزها.

26
00:01:57,200 --> 00:02:00,230
لذلك، يجب أن توضع هذه حيث في الجزء مصنفة؟

27
00:02:00,230 --> 00:02:04,220
>> تذكر، ونحن نريد لوضع هذا الرقم في ترتيب فرزها

28
00:02:04,220 --> 00:02:08,680
لذلك لدينا جزء مصنفة تبقى مصنفة بشكل صحيح في جميع الأوقات.

29
00:02:08,680 --> 00:02:14,380
إذا ما وضعنا في 4 إلى يمين 42، بعد ذلك سوف تكون لدينا قائمة من النظام.

30
00:02:14,380 --> 00:02:18,380
لذلك، دعونا المضي اليمين إلى اليسار في جزء نوع دينا.

31
00:02:18,380 --> 00:02:23,260
ونحن نمضي، دعونا تحويل كل رقم إلى أسفل مكان لإفساح المجال أمام عدد جديد.

32
00:02:25,440 --> 00:02:31,740
حسنا، 4 هو أيضا أقل من 23، لذلك نحن لا يمكن وضعه هنا أيضا.

33
00:02:31,740 --> 00:02:34,480
دعنا ننتقل ال 23 حق مكان واحد.

34
00:02:36,500 --> 00:02:43,120
>> هذا يعني أننا ترغب في وضع 4 في أول فتحة في الجزء فرزها.

35
00:02:43,120 --> 00:02:46,300
لاحظ كيف هذه المساحة في قائمة بالفعل فارغة،

36
00:02:46,300 --> 00:02:51,120
لأن كنا تتحرك عناصر مصنفة على النحو لقد واجهنا بها.

37
00:02:51,120 --> 00:02:52,740
حسنا. لذلك، نحن هناك في منتصف الطريق.

38
00:02:52,740 --> 00:02:57,990
دعونا مواصلة أنظمتنا عن طريق إدراج ال 16 في الجزء فرزها.

39
00:02:59,260 --> 00:03:03,820
ستة عشر أقل من 42 عاما، لذلك دعونا تحويل 42 إلى اليمين.

40
00:03:05,700 --> 00:03:10,190
ستة عشر هو أيضا أقل من 23، لذلك دعونا أيضا تحول هذا العنصر.

41
00:03:11,790 --> 00:03:20,820
>> الآن، 16 هو أكبر من 4. لذلك، يبدو أننا ترغب في إدراج ال 16 بين 4 و 23 في.

42
00:03:20,820 --> 00:03:24,620
في الوقت الذي يتجه من خلال الشريحة من قائمة مصنفة من اليمين إلى اليسار،

43
00:03:24,620 --> 00:03:29,160
4 هو الرقم الأول رأيناه أصغر من عدد

44
00:03:29,160 --> 00:03:31,540
نحاول إدراج.

45
00:03:31,540 --> 00:03:35,820
حتى الآن، يمكننا إدراج ال 16 في هذه الفتحة الفارغة،

46
00:03:35,820 --> 00:03:40,520
التي تذكر، لقد أنشأنا من قبل عناصر الحركة في الجزء نوع أكثر

47
00:03:40,520 --> 00:03:43,340
كما أننا قد واجهت بها.

48
00:03:43,340 --> 00:03:47,900
>> حسنا. الآن، لدينا أربعة عناصر فرزها والتي لم يتم فرزها عنصرين.

49
00:03:47,900 --> 00:03:51,600
لذلك، دعنا ننتقل ال 8 في الجزء فرزها.

50
00:03:51,600 --> 00:03:55,010
ثمانية أقل من 42.

51
00:03:55,010 --> 00:03:56,940
ثمانية أقل من 23.

52
00:03:56,940 --> 00:04:00,230
و8 هو أقل من 16.

53
00:04:00,230 --> 00:04:03,110
لكن 8 هو أكبر من 4.

54
00:04:03,110 --> 00:04:07,280
لذلك، نود أن إدراج ال 8 بين 4 و 16 في.

55
00:04:09,070 --> 00:04:13,650
والآن لدينا واحد فقط أكثر عنصر غادر لفرز - ال 15.

56
00:04:13,950 --> 00:04:16,589
أقل من خمسة عشر (42 عاما)

57
00:04:16,589 --> 00:04:19,130
خمسة عشر أقل من 23.

58
00:04:19,130 --> 00:04:21,750
و 15 أقل من 16.

59
00:04:21,750 --> 00:04:24,810
ولكن 15 أكبر من 8.

60
00:04:24,810 --> 00:04:27,440
>> لذلك، وهنا حيث نحن نريد أن نجعل الإدراج النهائي.

61
00:04:28,770 --> 00:04:30,330
وننتهي.

62
00:04:30,330 --> 00:04:33,540
ليس لدينا أكثر من العناصر التي لم يتم فرزها في الجزء،

63
00:04:33,540 --> 00:04:36,670
وجزء لدينا مصنفة في الترتيب الصحيح.

64
00:04:36,670 --> 00:04:40,270
تنظم الأرقام من الأصغر إلى الأكبر.

65
00:04:40,270 --> 00:04:44,330
لذلك، دعونا نلقي نظرة على بعض شبة الكود الذي يصف الخطوات التي يقوم فقط.

66
00:04:46,760 --> 00:04:51,740
>> في السطر 1، يمكننا أن نرى أننا بحاجة إلى تكرار عبر كل عنصر في القائمة

67
00:04:51,740 --> 00:04:57,060
ما عدا الأولى، ومنذ العنصر الأول في جزء لم يتم فرزها ببساطة تصبح

68
00:04:57,060 --> 00:05:00,220
العنصر الأول في جزء فرزها.

69
00:05:00,220 --> 00:05:06,320
على خطوط 2 و 3، ونحن تتبع مكاننا الحالي في جزء لم يتم فرزها.

70
00:05:06,320 --> 00:05:10,450
العنصر يمثل عدد نتحرك حاليا في الجزء فرزها،

71
00:05:10,450 --> 00:05:15,600
ويمثل ي فهرسنا في جزء لم يتم فرزها.

72
00:05:15,600 --> 00:05:20,980
>> على خط 4، ونحن بالتكرار عبر الجزء مصنفة من اليمين إلى اليسار.

73
00:05:20,980 --> 00:05:26,010
نحن نريد لوقف بالتكرار مرة واحدة العنصر إلى يسار موقفنا الحالي

74
00:05:26,010 --> 00:05:30,050
أقل من عنصر نحاول إدراج.

75
00:05:30,050 --> 00:05:35,600
على السطر 5، ونحن تحويل كل عنصر نواجه مسافة واحدة إلى اليمين.

76
00:05:35,600 --> 00:05:40,950
وبهذه الطريقة، سيكون لدينا مساحة واضحة لإدراجها في حين نجد العنصر الأول

77
00:05:40,950 --> 00:05:44,080
أقل من العنصر أننا نسير.

78
00:05:44,080 --> 00:05:50,800
على السطر 6، ونحن لدينا تحديث العداد لمواصلة التحرك من خلال ترك جزء فرزها.

79
00:05:50,800 --> 00:05:56,860
وأخيرا، في السطر 7، ونحن ادخال عنصر في الجزء مصنفة من القائمة.

80
00:05:56,860 --> 00:06:00,020
>> ونحن نعلم أنه لا بأس أن تضاف الى ي الموقف،

81
00:06:00,020 --> 00:06:05,360
لقد انتقلنا لأن بالفعل العنصر الذي اعتادت ان تكون هناك مسافة واحدة إلى اليمين.

82
00:06:05,360 --> 00:06:09,460
تذكر، أننا نسير من خلال الشريحة مصنفة من اليمين إلى اليسار،

83
00:06:09,460 --> 00:06:13,960
ولكننا نسير من خلال الشريحة التي لم يتم فرزها من اليسار إلى اليمين.

84
00:06:13,960 --> 00:06:19,090
حسنا. الآن دعونا نلقي نظرة على كيفية تشغيل طويلة أن خوارزمية استغرق.

85
00:06:19,090 --> 00:06:25,300
سنطلب للمرة الأولى مسألة كم من الوقت يستغرق لهذه الخوارزمية لتشغيل في أسوأ الأحوال.

86
00:06:25,300 --> 00:06:29,040
أذكر أننا نمثل هذا الوقت تعمل مع تدوين O الكبير.

87
00:06:32,530 --> 00:06:38,500
كان لدينا من أجل فرز قائمتنا، لتكرار عبر العناصر في جزء لم يتم فرزها،

88
00:06:38,500 --> 00:06:43,430
ولكل من هذه العناصر، ربما أكثر من جميع العناصر في الجزء فرزها.

89
00:06:43,430 --> 00:06:47,950
حدسي، وهذا يبدو وكأنه عملية (ن ^ 2) O.

90
00:06:47,950 --> 00:06:51,840
>> أبحث في شبة الكود، لدينا حلقة متداخلة داخل حلقة أخرى،

91
00:06:51,840 --> 00:06:55,290
التي، في الواقع، يبدو وكأنه عملية (ن ^ 2) O.

92
00:06:55,290 --> 00:07:01,590
ومع ذلك، فإن جزء من قائمة مصنفة لا يحتوي على القائمة بأكملها حتى النهاية.

93
00:07:01,590 --> 00:07:06,920
ومع ذلك، يمكن أن يحتمل إدراج عنصر جديد في بداية الجزء مصنفة

94
00:07:06,920 --> 00:07:09,320
على كل التكرار من الخوارزمية،

95
00:07:09,320 --> 00:07:14,500
وهو ما يعني أن كنا أن ننظر إلى كل عنصر من عناصر حاليا في الجزء فرزها.

96
00:07:14,500 --> 00:07:20,090
لذلك، وهذا يعني أننا يمكن أن تجعل المقارنة 1 للعنصر الثاني،

97
00:07:20,090 --> 00:07:24,660
2 المقارنات للعنصر الثالث، وهلم جرا.

98
00:07:24,660 --> 00:07:32,480
لذا، فإن العدد الإجمالي للخطوات هو مجموع الأعداد الصحيحة من 1 إلى طول قائمة ناقص 1.

99
00:07:32,480 --> 00:07:35,240
يمكننا تمثيل هذا مع الجمع.

100
00:07:41,170 --> 00:07:47,270
>> ونحن لن نذهب إلى summations هنا، ولكن تبين أن هذا الجمع يساوي

101
00:07:47,270 --> 00:07:57,900
ن (ن - 1) أكثر من 2، وهو ما يعادل ن ^ 2/2 - ن / 2.

102
00:07:57,900 --> 00:08:00,800
عندما نتحدث عن وقت مقارب،

103
00:08:00,800 --> 00:08:05,170
هذا المصطلح ^ N 2 سوف تهيمن على هذا المصطلح ن.

104
00:08:05,170 --> 00:08:11,430
لذلك، النوع الكبير الإدراج O (N ^ 2).

105
00:08:11,430 --> 00:08:16,150
ماذا لو ركضنا نوع الإدراج على قائمة تم فرزها بالفعل.

106
00:08:16,150 --> 00:08:20,960
في هذه الحالة، كنا ببساطة بناء الجزء مصنفة من اليسار إلى اليمين.

107
00:08:20,960 --> 00:08:25,050
لذلك، سنحتاج فقط بناء على أمر من الخطوات ن.

108
00:08:25,050 --> 00:08:29,740
>> وهذا يعني أن لديه نوع الإدراج أداء أفضل حالة ن،

109
00:08:29,740 --> 00:08:34,130
التي نمثلها مع Ω (ن).

110
00:08:34,130 --> 00:08:36,190
وهذا كل شيء عن نوع الإدراج،

111
00:08:36,190 --> 00:08:40,429
مجرد واحدة من العديد من الخوارزميات يمكننا استخدامها لفرز قائمة.

112
00:08:40,429 --> 00:08:43,210
اسمي تومي، وهذا هو CS50.

113
00:08:43,210 --> 00:08:44,880
[CS50.TV]

114
00:08:46,110 --> 00:08:49,230
أوه، لا يمكنك أن تتوقف أنه بمجرد بدء تشغيله.

115
00:09:01,620 --> 00:09:04,760
أوه، فعلنا ذلك - بوم >>!