1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [מיון מיזוג]

2
00:00:02,000 --> 00:00:04,000
[רוב אודן - אוניברסיטת הרווארד]

3
00:00:04,000 --> 00:00:07,000
[זה CS50. - CS50.TV]

4
00:00:07,000 --> 00:00:09,000
בואו נדבר על סוג המיזוג.

5
00:00:09,000 --> 00:00:14,000
עד כה ראה את מיון בועות, מיון הכנסה, ומיון בחירה.

6
00:00:14,000 --> 00:00:17,000
למרות שאני יהיה סוג של גל היד שלי על מה שאני מתכוון טוב יותר,

7
00:00:17,000 --> 00:00:21,000
סוג למזג בדרך מבצע טוב יותר מכל 3 סוגים אלה.

8
00:00:22,000 --> 00:00:27,000
>> אבל לפני שמדבר על סוג המיזוג, בואו נדבר על מיזוג 2 רשימות ממוינות.

9
00:00:27,000 --> 00:00:31,000
אנחנו קוראים לתהליך של לקיחת 2 רשימות ממוינות, כמו אלה,

10
00:00:31,000 --> 00:00:35,000
ועושה רשימה אחת ממוינת מתוכם - ממזג את הרשימות.

11
00:00:35,000 --> 00:00:37,750
איך אנחנו יכולים לעשות את זה?

12
00:00:37,750 --> 00:00:41,290
ובכן, רעיון אחד הוא פשוט להיצמד רשימה אחת על סוף הרשימה השנייה

13
00:00:41,290 --> 00:00:43,830
ולאחר מכן למיין את הרשימה שהתקבלה.

14
00:00:43,830 --> 00:00:47,220
>> אמנם זה עובד, זה הרבה עבודה מיותרת.

15
00:00:47,220 --> 00:00:49,900
אנחנו יכולים לעשות את זה מהר יותר מאשר רק מיון.

16
00:00:49,900 --> 00:00:54,100
שים לב שרעיון שגוי אחד הוא פשוט לקחת את הכוסות לסירוגין מכל רשימה.

17
00:00:54,100 --> 00:00:56,460
למרות שאולי נראה כמו זה עובד בהתחלה,

18
00:00:56,460 --> 00:01:05,760
עושה שאנחנו בסופו של דבר עם 4, 8, 15, 23, 16 - הודעה כי 16 ו 23 נמצאים מחוץ למקום.

19
00:01:05,760 --> 00:01:09,380
הסיבה לכך היא 2 אלמנטים שצריכים להופיע ברציפות ברשימה הממוזגת

20
00:01:09,380 --> 00:01:11,720
הם באותה הרשימה ראשונית.

21
00:01:11,720 --> 00:01:14,850
בני 15 ו 16 נמצא ברשימה בצד השמאל.

22
00:01:14,850 --> 00:01:19,810
החוכמה היא לנצל את העובדה ששני הרשימות כבר מסודרות.

23
00:01:19,810 --> 00:01:23,320
זה אומר שאם אנחנו רק מסתכלים על האלמנטים הראשונים של שתי הרשימות -

24
00:01:23,320 --> 00:01:29,580
כאן, 4 ו 8 - אחד מהם חייבות להיות גם המרכיב הראשון ברשימה הממוזגת.

25
00:01:29,580 --> 00:01:31,620
ובכן, מדוע זה כך?

26
00:01:31,620 --> 00:01:33,520
שתי הרשימות הללו כבר מסודרים,

27
00:01:33,520 --> 00:01:38,410
וכך גם 4 או 8 חייבים להיות האלמנט הקטן ביותר כאשר אנו משלבים את 2 רשימות.

28
00:01:38,410 --> 00:01:41,770
במקרה זה, הקטן ביותר הוא 4,

29
00:01:41,770 --> 00:01:46,370
כדי שנוכל להוציא 4 ולהפוך אותו לאלמנט הראשון של הרשימה הממוזגת שלנו.

30
00:01:46,370 --> 00:01:50,710
עכשיו אנחנו ממשיכים ממזגים את 3 אלמנטים הנותרים של הרשימה הראשונה

31
00:01:50,710 --> 00:01:52,920
ו 4 אלמנטים של הרשימה השנייה.

32
00:01:52,920 --> 00:01:57,150
>> שוב, אנחנו צריכים רק להסתכל על האלמנט הראשון של שתי הרשימות.

33
00:01:57,150 --> 00:02:01,060
הקטן יותר של 2 חייב להיות המרכיב השני ברשימה הממוזגת שלנו.

34
00:02:01,060 --> 00:02:05,440
הפעם, בין 8 ל 15 הקטנים ביותר הוא 8, ולכן אנחנו מוסיפים כי

35
00:02:05,440 --> 00:02:09,240
כמרכיב השני ברשימה הממוינת שלנו.

36
00:02:09,240 --> 00:02:12,180
אנחנו יכולים להמשיך להשוות את המרכיבים הראשונים של שתי הרשימות

37
00:02:12,180 --> 00:02:14,420
והסרה קטנה יותר של 2.

38
00:02:14,420 --> 00:02:19,460
השוואה בין 15 ל 23, 15 היא קטנה יותר ואז זה האלמנט השלישי שלנו.

39
00:02:21,000 --> 00:02:23,910
עכשיו משווה 16 ו 23, 16 הם קטנים יותר.

40
00:02:23,910 --> 00:02:26,820
אז זה היסוד הרביעי.

41
00:02:26,820 --> 00:02:30,390
>> שים לב כי 2 אלמנטים הגיעו מאותה הרשימה ברציפות.

42
00:02:30,390 --> 00:02:34,400
זו הסיבה שהרשימה הממוזגת לא יכולה רק יסודות חלופיים מאת 2 הרשימות.

43
00:02:34,400 --> 00:02:40,020
השוואה בין 50 ל 23, 23 היא קטנה יותר, ולכן אנחנו בוחרים את זה.

44
00:02:40,770 --> 00:02:44,070
בין 50 ל 42, 42 הם קטנים יותר.

45
00:02:44,070 --> 00:02:48,290
בין 50 ל 108, 50 הם קטנים יותר.

46
00:02:48,290 --> 00:02:52,330
ולבסוף, יש לנו רק 108, כך שהוא חייב ללכת בסוף הרשימה שלנו.

47
00:02:53,750 --> 00:02:56,180
שים לב שיש לנו רשימה יפה, מסודרת.

48
00:02:56,180 --> 00:02:59,040
בכל פעם שהשווינו את 2 המרכיבים הראשונים של את 2 רשימות

49
00:02:59,040 --> 00:03:02,730
היינו יכול לקבוע את האלמנט הבא ברשימה הממוזגת.

50
00:03:02,730 --> 00:03:08,070
זה אומר שאם את הרשימה הסופית מכילה מספרי n, כאשר n כאן הוא 8,

51
00:03:08,070 --> 00:03:12,610
אז אנחנו צריכים ברוב השוואות n כדי לקבל את כל המספרים האלה למקום הנכון.

52
00:03:13,230 --> 00:03:16,230
כגון אלגוריתם אמר לרוץ בזמן ליניארי,

53
00:03:16,230 --> 00:03:18,090
אבל אל תדאגו בקשר לזה כאן.

54
00:03:18,570 --> 00:03:22,810
>> באמצעות האלגוריתם שלנו למיזוג, אנחנו יכולים לעשות את אלגוריתם מיון מיזוג מהיר.

55
00:03:22,810 --> 00:03:25,170
אז, בואו לאפס את הרשימות שלנו.

56
00:03:35,210 --> 00:03:37,750
ישנם 2 צעדים גדולים בתהליך של מיון מיזוג.

57
00:03:37,750 --> 00:03:41,500
ראשית, ברציפות לפצל את הרשימה של כוסות לחצי

58
00:03:41,500 --> 00:03:44,860
עד שיש לנו חבורה של רשימות רק עם 1 הכוס ב.

59
00:03:44,860 --> 00:03:47,350
אל תדאגו אם רשימה מכילה מספר אי זוגי

60
00:03:47,350 --> 00:03:49,880
ואתה לא יכול לעשות חתך נקי לחלוטין ביניהם.

61
00:03:49,880 --> 00:03:53,750
רק באופן שרירותי לבחור לאיזו רשימה שתכלול את הכוס הנוספת פנימה

62
00:03:53,750 --> 00:03:56,240
אז, בואו לפצל הרשימות האלה.

63
00:03:58,140 --> 00:04:01,310
עכשיו יש לנו 2 רשימות.

64
00:04:04,120 --> 00:04:06,570
עכשיו יש לנו 4 רשימות.

65
00:04:10,350 --> 00:04:13,870
>> ועכשיו יש לנו 8 רשימות עם כוס אחת בכל רשימה.

66
00:04:13,870 --> 00:04:16,630
אז זהו זה לשלב 1.

67
00:04:16,630 --> 00:04:22,230
עבור שלב 2, אנחנו שוב ושוב למזג זוגות של רשימות באמצעות אלגוריתם המיזוג שלמדנו בעבר.

68
00:04:22,230 --> 00:04:29,160
מיזוג 108 ו 15, אנחנו בסופו של דבר עם הרשימה 15, 108.

69
00:04:30,330 --> 00:04:36,250
מיזוג 50 ו 4, אנחנו בסופו של דבר עם 4, 50.

70
00:04:36,960 --> 00:04:41,400
מיזוג 8 ו 42, אנחנו בסופו של דבר עם 8, 42.

71
00:04:42,790 --> 00:04:48,130
ומיזוג של 23 ו 16, אנחנו בסופו של דבר עם 16, 23.

72
00:04:49,740 --> 00:04:52,450
עכשיו כל הרשימות שלנו הן בגודל 2.

73
00:04:53,020 --> 00:04:56,180
שים לב שכל אחד 4 הרשימות ממוינת.

74
00:04:56,180 --> 00:04:59,160
>> אז אנחנו יכולים להתחיל התמזגות זוגות של רשימות שוב.

75
00:04:59,160 --> 00:05:03,240
מיזוג 15 ו 108 ו 4 ו 50 -

76
00:05:03,240 --> 00:05:11,170
קודם כל לקחת 4, אז 15, אז 50, אז 108.

77
00:05:11,170 --> 00:05:15,120
מיזוג 8, 42 ו 16, 23,

78
00:05:15,120 --> 00:05:22,440
אנו לוקחים 1 8, 16, 23 אז, ולאחר מכן 42.

79
00:05:22,440 --> 00:05:27,370
אז עכשיו יש לנו רק 2 רשימות של גודל 4, כל אחד מהם ממוין.

80
00:05:27,370 --> 00:05:30,980
אז עכשיו אנחנו למזג 2 הרשימות האלה.

81
00:05:30,980 --> 00:05:33,440
ראשית אנחנו לוקחים 4.

82
00:05:33,440 --> 00:05:36,580
אז אנחנו לוקחים 8.

83
00:05:36,580 --> 00:05:50,700
אנחנו לוקחים את 15 ו 16, אז 23, אז בן 42, אז 50, אז 108.

84
00:05:50,700 --> 00:05:52,220
ואנחנו נעשינו.

85
00:05:52,220 --> 00:05:54,900
עכשיו יש לנו רשימה ממוינת.

86
00:05:54,900 --> 00:05:57,890
אז כמה מהר היה זה בדיוק?

87
00:05:57,890 --> 00:06:02,000
במונחים טכניים, מעין מיזוג הוא O (n log n),

88
00:06:02,000 --> 00:06:07,380
ואילו כל מיון בועות, מיון הכנסה, ומיון בחירה הוא O (n ²).

89
00:06:07,380 --> 00:06:11,120
למעשה, כפי שאתה תלמד בקרוב, אתה לא תוכל לבוא עם סוג

90
00:06:11,120 --> 00:06:14,820
המבצעת טובה יותר מאשר O (n log n) במקרה הכללי.

91
00:06:14,820 --> 00:06:19,120
שוב, אל תדאגו סימון O גדול זה אם אתה לא ראית אותו עדיין.

92
00:06:19,120 --> 00:06:23,490
>> רק יודע שזה אומר שאם אנחנו רוצים למיין רשימה גדולה באמת

93
00:06:23,490 --> 00:06:26,820
מיון בועות, מיון הכנסה, ובחירת סוג עלול לקחת

94
00:06:26,820 --> 00:06:29,500
באופן משמעותי יותר מאשר למזג מיון.

95
00:06:29,500 --> 00:06:33,210
זה לא אומר שסוג המיזוג יהיה מהיר יותר לכל הרשימות

96
00:06:33,210 --> 00:06:36,220
או אפילו לכל רשימה אחת מתחת לגודל מסוים.

97
00:06:36,220 --> 00:06:41,950
לדוגמה, סוג ההכנסה עלול להיות מהסוג המהיר ביותר עבור כל הרשימות קטנות יותר מ 5 אלמנטים.

98
00:06:41,950 --> 00:06:47,360
בפועל, מעין מיזוג הוא בדרך כלל מהר יותר לרשימות קטנות כמו 50 אלמנטים.

99
00:06:47,360 --> 00:06:51,120
>> אבל מהירות נוספת זה לא באה ללא מחיר.

100
00:06:51,120 --> 00:06:54,770
בניגוד למינים האחרים שלנו, אשר לוקח את הרשימה ולשנות את הרשימה במקום

101
00:06:54,770 --> 00:06:58,740
עד שנגיע לרשימה ממוינת, מעין מיזוג צריך מרחב נוסף

102
00:06:58,740 --> 00:07:00,900
למזג 2 רשימות יחד.

103
00:07:00,900 --> 00:07:04,690
אנחנו לא יכולים להשתמש באופן מיידי את הרשימות שנמצאים מוזגו כדי לאחסן את הרשימה הממוזגת

104
00:07:04,690 --> 00:07:08,880
מאז שעשוי לעקוף אלמנטים שעדיין צריכים להיות ממוזגים.

105
00:07:08,880 --> 00:07:13,540
המרחב הזה הוא קצת מחיר, אבל זה בדרך כלל אינו בלתי סביר.

106
00:07:13,540 --> 00:07:15,330
וזהו זה לסוג המיזוג.

107
00:07:15,330 --> 00:07:18,490
>> השם שלי הוא רוב אודן, וזה CS50.

108
00:07:18,490 --> 00:07:20,500
[CS50.TV]

109
00:07:20,500 --> 00:07:24,000
- בחירה ומיון.

110
00:07:24,000 --> 00:07:25,880
[צוחק]

111
00:07:25,880 --> 00:07:31,480
אה, יש גם לקחת את זה כי אני עברתי איך אני מציג אותו.

112
00:07:31,480 --> 00:07:35,680
רשימה בצד השמאל. זה היה טעות דפוס.

113
00:07:35,680 --> 00:07:39,290
[Misspoke] אני דפוק -

114
00:07:39,290 --> 00:07:41,190
[צוחק]

115
00:07:41,190 --> 00:07:44,190
אני לא יודע מה -