1
00:00:00,000 --> 00:00:02,826
>> [عزف الموسيقى]

2
00:00:02,826 --> 00:00:05,660

3
00:00:05,660 --> 00:00:09,370
>> DOUG لويد: لذا الإدراج النوع هو آخر
خوارزمية يمكننا استخدامها لفرز صفيف.

4
00:00:09,370 --> 00:00:12,350
الفكرة وراء هذه الخوارزمية
هو بناء مجموعة فرزها بك

5
00:00:12,350 --> 00:00:19,670
في مكان، وتحويل العناصر من
الطريق كما تذهب، لإفساح المجال.

6
00:00:19,670 --> 00:00:22,240
هذا يختلف قليلا
من اختيار نوع أو فقاعة

7
00:00:22,240 --> 00:00:25,460
النوع، على سبيل المثال، حيث
نحن ضبط المواقع،

8
00:00:25,460 --> 00:00:26,910
أين نحن مما يجعل مقايضة.

9
00:00:26,910 --> 00:00:29,760
>> في هذه الحالة ما نحن عليه فعلا
به هو عناصر انزلاق

10
00:00:29,760 --> 00:00:31,390
أكثر، للخروج من الطريق.

11
00:00:31,390 --> 00:00:34,030
كيف هذه الخوارزمية
العمل في شبة الكود؟

12
00:00:34,030 --> 00:00:37,646
حسنا دعنا نقول فقط أن تعسفا
يتم فرز العنصر الأول للمجموعة.

13
00:00:37,646 --> 00:00:38,770
نحن نبني في مكانه.

14
00:00:38,770 --> 00:00:42,660
>> نحن gonna الذهاب عنصر واحد في وقت واحد
بناء عليه، وبالتالي فإن أول شيء نراه

15
00:00:42,660 --> 00:00:43,890
هي مجموعة عنصر واحد.

16
00:00:43,890 --> 00:00:47,720
وبحكم التعريف، وهو واحد
يتم فرز عنصر صفيف.

17
00:00:47,720 --> 00:00:50,850
>> ثم سنقوم بتكرار هذه العملية until--
سنقوم تكرار العملية التالية

18
00:00:50,850 --> 00:00:52,900
حتى يتم فرز جميع العناصر.

19
00:00:52,900 --> 00:00:57,770
نظرة على عنصر لم يتم فرزها المقبل و
أدخله في جزء فرزها،

20
00:00:57,770 --> 00:01:01,209
عن طريق تحويل العدد المطلوب
من العناصر للخروج من الطريق.

21
00:01:01,209 --> 00:01:03,750
نأمل أن هذا التصور
سوف تساعدك على معرفة بالضبط ما هو

22
00:01:03,750 --> 00:01:05,980
يحدث مع الإدراج النوع.

23
00:01:05,980 --> 00:01:08,010
>> ذلك مرة أخرى، وهنا لدينا
مجموعة غير مصنفة بأكملها،

24
00:01:08,010 --> 00:01:10,970
جميع العناصر المشار إليها باللون الأحمر.

25
00:01:10,970 --> 00:01:13,320
ودعونا اتبع
خطوات شبة الكود لدينا.

26
00:01:13,320 --> 00:01:16,970
أول شيء نقوم به، ونحن ندعو ل
العنصر الأول من مجموعة وفرزها.

27
00:01:16,970 --> 00:01:20,920
لذلك نحن سنقول فقط
خمسة، كنت فرزها الآن.

28
00:01:20,920 --> 00:01:24,570
>> ثم ننظر إلى القادم
عنصر لم يتم فرزها من مجموعة

29
00:01:24,570 --> 00:01:27,610
ونحن نريد أن إدراج هذا
في جزء فرزها،

30
00:01:27,610 --> 00:01:29,750
عن طريق تحويل العناصر أكثر.

31
00:01:29,750 --> 00:01:33,470
حتى الاثنين هو فرزها المقبل
عنصر من عناصر المصفوفة.

32
00:01:33,470 --> 00:01:36,250
ومن الواضح أنها تنتمي قبل
خمسة، وذلك ما سنفعله

33
00:01:36,250 --> 00:01:41,580
هو نوع من عقد اجتماعين جانبا للحظة واحدة،
تحويل خمسة أكثر، ومن ثم إدراج اثنين

34
00:01:41,580 --> 00:01:43,210
قبل خمس سنوات، أين يجب أن تذهب.

35
00:01:43,210 --> 00:01:45,280
والآن نستطيع أن نقول أن يتم فرز اثنين.

36
00:01:45,280 --> 00:01:48,400
>> هكذا كما ترون، لدينا فقط حتى الآن
نظرت إلى اثنين من عناصر المصفوفة.

37
00:01:48,400 --> 00:01:50,600
ونحن لم ننظر في
راحة على الإطلاق، ولكن لدينا

38
00:01:50,600 --> 00:01:54,582
حصلت على هذين العنصرين تم الفرز حسب
طريق آلية التحول.

39
00:01:54,582 --> 00:01:56,410
>> لذلك نكرر العملية مرة أخرى.

40
00:01:56,410 --> 00:01:58,850
نظرة على فرزها المقبل
العنصر، وهذا هو واحد.

41
00:01:58,850 --> 00:02:04,010
دعونا نرى أن جانبا للحظة واحدة،
تحول كل شيء انتهى، ووضع واحد

42
00:02:04,010 --> 00:02:05,570
حيث يجب ان تذهب.

43
00:02:05,570 --> 00:02:08,110
>> مرة أخرى، لا يزال، لدينا من أي وقت مضى فقط
نظرت إلى واحد، اثنان، وخمسة.

44
00:02:08,110 --> 00:02:12,480
نحن لا نعرف ماذا قادم،
ولكن لدينا فرز تلك العناصر الثلاثة.

45
00:02:12,480 --> 00:02:16,030
>> عنصر لم يتم فرزها التالي هو
ثلاثة، ولذا فإننا سوف ضعه جانبا.

46
00:02:16,030 --> 00:02:18,200
سنقوم تحول على ما نحن
تحتاج إلى الذي، وهذه المرة

47
00:02:18,200 --> 00:02:21,820
ليس كل شيء كما في السابق
حالتين، انها مجرد خمسة.

48
00:02:21,820 --> 00:02:25,440
وبعد ذلك سنقوم عصا ثلاثة في،
بين اثنين وخمسة.

49
00:02:25,440 --> 00:02:27,849
>> ستة هو القادم فرزها
عنصر للمجموعة.

50
00:02:27,849 --> 00:02:31,140
في واقع الأمر ستة هو أكبر من خمسة، لذلك
نحن لسنا بحاجة حتى للقيام بأي مقايضة.

51
00:02:31,140 --> 00:02:35,710
يمكننا أن تك فقط ستة الحق على ل
نهاية الجزء فرزها.

52
00:02:35,710 --> 00:02:38,270
>> وأخيرا، أربعة هو
اخر عنصر لم يتم فرزها.

53
00:02:38,270 --> 00:02:42,060
ولذا فإننا سوف ضعه جانبا، وتحول أكثر
العناصر نحن بحاجة إلى تحويل أكثر،

54
00:02:42,060 --> 00:02:43,780
ثم وضعت أربعة حيث تنتمي.

55
00:02:43,780 --> 00:02:46,400
ونتطلع الآن، لدينا نوع
من جميع العناصر.

56
00:02:46,400 --> 00:02:48,150
لاحظ مع الإدراج
النوع، لم يكن لدينا

57
00:02:48,150 --> 00:02:50,240
للذهاب ذهابا وإيابا عبر مجموعة.

58
00:02:50,240 --> 00:02:54,720
ذهبنا فقط عبر مجموعة
مرة واحدة، ونحن تحولت الأمور

59
00:02:54,720 --> 00:02:59,870
أن كنا اجه بالفعل، من أجل
لإفساح المجال للعناصر الجديدة.

60
00:02:59,870 --> 00:03:02,820
>> إذن ما هو أسوأ حالة
السيناريو مع الإدراج الفرز؟

61
00:03:02,820 --> 00:03:05,090
في أسوأ الحالات، و
الصفيف في ترتيب عكسي.

62
00:03:05,090 --> 00:03:11,180
لديك لتحويل كل عنصر من العناصر ن
ما يصل الى مناصب ن، كل نحن مرة واحدة

63
00:03:11,180 --> 00:03:12,880
جعل الإدراج.

64
00:03:12,880 --> 00:03:15,720
كما أن هناك العديد من التحول.

65
00:03:15,720 --> 00:03:18,014
>> في أفضل الأحوال، و
يتم فرز مجموعة تماما.

66
00:03:18,014 --> 00:03:20,680
ونوع من مثل ما حدث
مع خمسة وستة في المثال،

67
00:03:20,680 --> 00:03:23,779
حيث أننا يمكن أن مجرد تك على
دون الحاجة إلى القيام بأي تحويل،

68
00:03:23,779 --> 00:03:24,820
كنا نفعل أساسا ذلك.

69
00:03:24,820 --> 00:03:27,560
>> إذا كنت تتخيل أن لدينا
وكانت مجموعة واحدة خلال ستة،

70
00:03:27,560 --> 00:03:29,900
كنا تبدأ من خلال
إعلان واحد تم فرزها.

71
00:03:29,900 --> 00:03:33,300
اثنين يأتي بعد واحد حتى يمكننا فقط
نقول، حسنا، حسنا يتم فرز واحد واثنين.

72
00:03:33,300 --> 00:03:36,190
ثلاثة ويأتي بعد ذلك اثنين، OK،
يتم فرز واحد واثنين وثلاثة.

73
00:03:36,190 --> 00:03:39,590
>> نحن لا يجعل أي مقايضة، ونحن
مجرد نقل هذا الخط التعسفي

74
00:03:39,590 --> 00:03:42,460
بين فرزها وفرزها ونحن نمضي.

75
00:03:42,460 --> 00:03:46,646
بفعالية كما فعلنا في المثال،
تحول العناصر الأزرق، كلما تقدمنا.

76
00:03:46,646 --> 00:03:48,270
إذن ما هو أسوأ حالة وقت التشغيل، ثم؟

77
00:03:48,270 --> 00:03:51,854
تذكر، إذا كان لدينا لتحويل كل من
العناصر ن ربما المواقف ن،

78
00:03:51,854 --> 00:03:54,020
نأمل أن تمنحك
فكرة أن أسوأ الحالات

79
00:03:54,020 --> 00:03:57,770
وقت التشغيل هو يا كبير من ن تربيع.

80
00:03:57,770 --> 00:04:00,220
>> إذا كان الصفيف هي تماما
مرتبة، كل ما عليك القيام به

81
00:04:00,220 --> 00:04:04,480
هو أن ننظر في كل عنصر واحد
مرة واحدة، ثم ننتهي.

82
00:04:04,480 --> 00:04:08,440
حتى في أفضل الأحوال، فإنه من أوميغا ن.

83
00:04:08,440 --> 00:04:09,490
>> أنا دوغ ويد.

84
00:04:09,490 --> 00:04:11,760
هذا هو CS50.

85
00:04:11,760 --> 00:04:13,119