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

2
00:00:05,726 --> 00:00:08,600
DOUG لويد: اختيار النوع هو
الخوارزمية التي، كما قد تتوقع،

3
00:00:08,600 --> 00:00:10,470
يفرز مجموعة من العناصر.

4
00:00:10,470 --> 00:00:12,470
وأذكر خوارزمية
هو عبارة عن مجموعة خطوة بخطوة

5
00:00:12,470 --> 00:00:15,260
من تعليمات لإكمال المهمة.

6
00:00:15,260 --> 00:00:17,580
>> في اختيار فرز
الفكرة الأساسية هي هذه،

7
00:00:17,580 --> 00:00:22,080
العثور على أصغر عنصر لم يتم فرزها و
إضافته إلى نهاية القائمة فرزها.

8
00:00:22,080 --> 00:00:26,970
على نحو فعال ما يفعل ذلك هو بناء
قائمة تم فرزها، عنصر واحد في وقت واحد.

9
00:00:26,970 --> 00:00:29,800
تقسمها إلى شبة الكود
يمكننا أن أذكر هذه الخوارزمية

10
00:00:29,800 --> 00:00:34,490
على النحو التالي، كرر هذا حتى
تبقى أية عناصر غير مصنفة.

11
00:00:34,490 --> 00:00:38,660
البحث عن طريق فرزها
البيانات للعثور على أصغر قيمة،

12
00:00:38,660 --> 00:00:44,130
ثم مبادلة أصغر قيمة مع
العنصر الأول من الجزء فرزها.

13
00:00:44,130 --> 00:00:47,130
>> قد تساعد على تصور هذا،
لذلك دعونا نلقي نظرة على هذا.

14
00:00:47,130 --> 00:00:49,710
لذلك هذا، وأنا أزعم، هو
مجموعة فرزها ولدي

15
00:00:49,710 --> 00:00:53,040
يشار إليه بالإشارة إلى أن جميع
من العناصر الملونة الحمراء،

16
00:00:53,040 --> 00:00:54,420
لا يتم فرز ومع ذلك.

17
00:00:54,420 --> 00:00:57,670
هذا هو كامل
جزء لم يتم فرزها من مجموعة.

18
00:00:57,670 --> 00:01:02,020
>> لذلك دعونا نذهب من خلال خطوات
اختيار لفرز هذه المجموعة.

19
00:01:02,020 --> 00:01:05,296
ذلك مرة أخرى، ونحن تكرار ستعمل
حتى لا تظل العناصر التي لم يتم فرزها.

20
00:01:05,296 --> 00:01:07,920
نحن ستعمل من خلال بحث
البيانات للعثور على أصغر قيمة،

21
00:01:07,920 --> 00:01:11,990
ثم مبادلة تلك القيمة مع
العنصر الأول من الجزء فرزها.

22
00:01:11,990 --> 00:01:14,380
>> الآن، مرة أخرى، كامل
مجموعة هي جزء لم يتم فرزها.

23
00:01:14,380 --> 00:01:16,534
جميع العناصر الحمراء هي التي لم يتم فرزها.

24
00:01:16,534 --> 00:01:18,700
لذلك نحن من خلال البحث عن و
نجد أصغر قيمة.

25
00:01:18,700 --> 00:01:20,533
نبدأ في البداية،
نذهب إلى النهاية،

26
00:01:20,533 --> 00:01:23,630
نجد أصغر قيمة هي، واحدة.

27
00:01:23,630 --> 00:01:24,860
لذلك هذا جزء واحد.

28
00:01:24,860 --> 00:01:29,440
ثم الجزء الثاني، مبادلة تلك القيمة مع
العنصر الأول من الجزء فرزها،

29
00:01:29,440 --> 00:01:31,340
أو أول عنصر الأحمر.

30
00:01:31,340 --> 00:01:34,980
>> في هذه الحالة من شأنه أن يكون
خمسة، لذلك نحن مبادلة واحدة وخمس سنوات.

31
00:01:34,980 --> 00:01:37,320
عندما نفعل هذا، يمكننا
ترى بالعين المجردة التي كانت لدينا

32
00:01:37,320 --> 00:01:41,260
انتقل أصغر عنصر قيمة
في المصفوفة، إلى البداية.

33
00:01:41,260 --> 00:01:43,920
فرز نحو فعال ذلك العنصر.

34
00:01:43,920 --> 00:01:47,520
>> وحتى نتمكن من تأكيد الواقع
والدولة التي واحدة، يتم فرز.

35
00:01:47,520 --> 00:01:52,080
ولذا فإننا سوف تشير إلى جزء فرز
من مجموعة لدينا، من خلال تلوين أنها الأزرق.

36
00:01:52,080 --> 00:01:53,860
>> ونحن الآن مجرد تكرار العملية مرة أخرى.

37
00:01:53,860 --> 00:01:57,430
نحن نبحث من خلال الجزء فرزها من
مجموعة للعثور على أصغر عنصر.

38
00:01:57,430 --> 00:01:59,000
في هذه الحالة، فإنه من اثنين.

39
00:01:59,000 --> 00:02:02,100
>> نحن مبادلة مع أول
عنصر الجزء فرزها.

40
00:02:02,100 --> 00:02:05,540
في هذه الحالة اثنين يحدث أيضا أن تكون
العنصر الأول من الجزء فرزها.

41
00:02:05,540 --> 00:02:08,650
لذلك نحن مبادلة اثنين مع نفسه،
والتي في الواقع يترك اثنين فقط

42
00:02:08,650 --> 00:02:11,257
أين هو، وانها فرزها.

43
00:02:11,257 --> 00:02:13,840
استمرار جرا، ونحن من خلال البحث عن
العثور على أصغر عنصر.

44
00:02:13,840 --> 00:02:15,030
انها الثلاث.

45
00:02:15,030 --> 00:02:17,650
نحن مبادلة مع أول
عنصر، وهو خمسة.

46
00:02:17,650 --> 00:02:19,450
والآن يتم فرز ثلاثة.

47
00:02:19,450 --> 00:02:22,440
>> نحن نبحث عن طريق مرة أخرى، ونحن
العثور على أصغر عنصر هو أربعة.

48
00:02:22,440 --> 00:02:28,070
نحن مبادلة مع العنصر الأول لل
جزء لم يتم فرزها، والآن يتم فرز الأربعة.

49
00:02:28,070 --> 00:02:29,910
>> نجد أن خمسة من
أصغر عنصر.

50
00:02:29,910 --> 00:02:32,900
نحن مبادلة مع أول
عنصر الجزء فرزها.

51
00:02:32,900 --> 00:02:34,740
والآن يتم فرز الخمسة.

52
00:02:34,740 --> 00:02:36,660
>> ثم أخيرا، لدينا
جزء لم يتم فرزها يتألف

53
00:02:36,660 --> 00:02:38,576
من مجرد عنصر واحد،
لذلك نحن من خلال البحث عن

54
00:02:38,576 --> 00:02:41,740
ونجد أن ستة هو
أصغر، في واقع الأمر، العنصر فقط.

55
00:02:41,740 --> 00:02:44,906
وبعد ذلك يمكننا أن نقول أن يتم فرز عليه.

56
00:02:44,906 --> 00:02:47,530
ونحن الآن قد تحولت مجموعة لدينا
من يجري فرزها تماما

57
00:02:47,530 --> 00:02:52,660
باللون الأحمر، إلى مرتبة تماما
في الزرقاء، وذلك باستخدام اختيار نوع.

58
00:02:52,660 --> 00:02:54,920
>> إذن ما هو أسوأ سيناريو هنا؟

59
00:02:54,920 --> 00:02:57,830
حسنا في أسوأ المطلق
الحالة، يتعين علينا أن ننظر أكثر

60
00:02:57,830 --> 00:03:02,170
جميع عناصر المصفوفة ل
العثور على أصغر عنصر لم يتم فرزها،

61
00:03:02,170 --> 00:03:04,750
وعلينا أن نكرر
هذه العملية n مرة.

62
00:03:04,750 --> 00:03:09,090
مرة واحدة لكل عنصر من المصفوفة
لأننا فقط، في هذه الخوارزمية،

63
00:03:09,090 --> 00:03:12,180
عنصر واحد في وقت ونوع.

64
00:03:12,180 --> 00:03:13,595
>> ما هو أفضل سيناريو؟

65
00:03:13,595 --> 00:03:15,040
حسنا انها بالضبط نفس الشيء، أليس كذلك؟

66
00:03:15,040 --> 00:03:18,440
لدينا في الواقع إلى ما زالت الخطوة من خلال
كل عنصر واحد من مجموعة

67
00:03:18,440 --> 00:03:22,040
من أجل التأكد من أنه هو،
في الواقع، أصغر عنصر.

68
00:03:22,040 --> 00:03:26,760
>> وبالتالي فإن أسوأ حالة وقت، ونحن
لديك لتكرار عملية ن مرات،

69
00:03:26,760 --> 00:03:28,960
مرة واحدة لكل من العناصر ن.

70
00:03:28,960 --> 00:03:31,940
وفي أحسن الأحوال،
علينا أن تفعل الشيء نفسه.

71
00:03:31,940 --> 00:03:35,340
>> حتى التفكير في العودة إلى موقعنا
الحسابية الأدوات التعقيد،

72
00:03:35,340 --> 00:03:39,250
ما رأيك هو أسوأ
وقت الحال بالنسبة لاختيار نوع؟

73
00:03:39,250 --> 00:03:41,840
ما رأيك هو الأفضل
وقت الحال بالنسبة لاختيار نوع؟

74
00:03:41,840 --> 00:03:44,760

75
00:03:44,760 --> 00:03:49,325
>> هل تخمين الكبير O ن تربيع،
والكبير أوميغا ن المربعة؟

76
00:03:49,325 --> 00:03:49,950
كنت على حق.

77
00:03:49,950 --> 00:03:52,490
تلك هي، في الواقع،
أسوأ الحالات وأفضل حالة تشغيل

78
00:03:52,490 --> 00:03:55,100
مرات، لاختيار نوع.

79
00:03:55,100 --> 00:03:56,260
>> أنا دوغ ويد.

80
00:03:56,260 --> 00:03:58,600
هذا هو CS50.

81
00:03:58,600 --> 00:04:00,279