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
[דאס איז קס50. - 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
מיר ערשטער נעמען די 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
אין טעכניש תּנאָים, צונויפגיסן סאָרט איז אָ (N קלאָץ ען),

88
00:06:02,000 --> 00:06:07,380
וועראַז אַלע פון ​​בלאָז סאָרט, ינסערשאַן סאָרט, און סעלעקציע סאָרט ביסט אָ (N ²).

89
00:06:07,380 --> 00:06:11,120
אין פאַקט, ווי איר וועט לערנען באַלד, איר וועט נישט זייַן ביכולת צו קומען אַרויף מיט אַ סאָרט

90
00:06:11,120 --> 00:06:14,820
אַז פּערפאָרמז בעסער ווי אָ (N קלאָץ N) אין די אַלגעמיינע פאַל.

91
00:06:14,820 --> 00:06:19,120
ווידער, טאָן ניט זאָרג וועגן דעם גרויס אָ נאָוטיישאַן אויב איר האָט ניט געזען עס נאָך.

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
>> מייַן נאָמען איז ראָב באָוודען, און דאָס איז קס50.

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
[מיספּאָוק] איך סקרוד אַרויף -

114
00:07:39,290 --> 00:07:41,190
[לאַפס]

115
00:07:41,190 --> 00:07:44,190
איך טאָן ניט וויסן וואָס -