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
אז, בואו נסתכל pseudocode חלק שמתאר את צעדינו רק שבוצעו.

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, אנחנו iterating דרך החלק הממוין מימין לשמאל.

73
00:05:20,980 --> 00:05:26,010
אנחנו רוצים לעצור iterating פעם האלמנט מהשמאל למיקום הנוכחי שלנו

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
>> אנחנו יודעים שזה בסדר להכניס לתוך j עמדה,

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
באופן אינטואיטיבי, זה נשמע כמו פעולת O (n ^ 2).

90
00:06:47,950 --> 00:06:51,840
>> כאשר מסתכלים על pseudocode, יש לנו לולאה מקוננת בתוך לולאה אחרת,

91
00:06:51,840 --> 00:06:55,290
אשר, אכן, נשמע כמו פעולת O (n ^ 2).

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
אז, זה אומר שאנחנו עלולים לעשות השוואה אחד לאלמנט השני,

97
00:07:20,090 --> 00:07:24,660
שתי השוואות לגורם השלישי, וכן הלאה.

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
>> אנחנו לא נכנסנו לסיכומים לכאן, אבל מתברר שהסיכום זה שווה

101
00:07:47,270 --> 00:07:57,900
n (n - 1) מעל 2, שהוא שווה ערך n ^ 2/2 - n / 2.

102
00:07:57,900 --> 00:08:00,800
כאשר מדברים על זמן ריצת אסימפטוטי,

103
00:08:00,800 --> 00:08:05,170
n ^ 2 מונח זה הולך לשלוט טווח n זה.

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
אז, אנחנו רק צריכים על סדר פעולות n.

108
00:08:25,050 --> 00:08:29,740
>> זה אומר שיש סוג ההכנסה במקרה הטוב ביותר את ביצועים של n,

109
00:08:29,740 --> 00:08:34,130
שאנו מייצגים בΩ (n).

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
אה, עשינו את זה - בום! >>