1
00:00:06,762 --> 00:00:09,980
[Powered by Google Translate] טאַמי: זאל ס נעמען אַ קוק בייַ סעלעקציע סאָרט, אַ אַלגערידאַם

2
00:00:09,980 --> 00:00:12,800
פֿאַר גענומען אַ רשימה פון נומערן און סאָרטינג זיי.

3
00:00:12,800 --> 00:00:15,750
אַ אַלגערידאַם, געדענקען, איז פשוט אַ שריט-דורך-שריט

4
00:00:15,750 --> 00:00:18,370
פּראָצעדור פֿאַר אַקאַמפּלישינג אַ אַרבעט.

5
00:00:18,370 --> 00:00:21,470
די גרונט געדאַנק הינטער סעלעקציע סאָרט איז צו טיילן

6
00:00:21,470 --> 00:00:23,390
אונדזער רשימה אין צוויי פּאָרשאַנז -

7
00:00:23,390 --> 00:00:26,810
אַ אויסגעשטעלט חלק און אַ ונסאָרטעד חלק.

8
00:00:26,810 --> 00:00:30,200
אין יעדער שריט פון די אַלגערידאַם, אַ נומער איז אריבערגעפארן פון דער

9
00:00:30,200 --> 00:00:33,800
ונסאָרטעד חלק צו די אויסגעשטעלט חלק ביז יווענטשאַוואַלי די

10
00:00:33,800 --> 00:00:35,880
גאנצע רשימה איז אויסגעשטעלט.

11
00:00:35,880 --> 00:00:38,510
אַזוי דאָ ס אַ רשימה פון זעקס נומערן -

12
00:00:38,510 --> 00:00:44,010
23, 42, 4, 16, 8, און 15.

13
00:00:44,010 --> 00:00:47,680
רעכט איצט די גאנצע רשימה איז געהאלטן ונסאָרטעד.

14
00:00:47,680 --> 00:00:51,770
אפילו כאָטש אַ נומער ווי מאי 16 שוין זייַן אין זייַן ריכטיק

15
00:00:51,770 --> 00:00:56,040
אָרט, אונדזער אַלגערידאַם האט קיין וועג פון געוואוסט אַז ביז די

16
00:00:56,040 --> 00:00:57,980
גאנצע רשימה איז אויסגעשטעלט.

17
00:00:57,980 --> 00:01:01,355
אַזוי מיר וועט באַטראַכטן יעדער נומער צו זייַן ונסאָרטעד ביז מיר סאָרט

18
00:01:01,355 --> 00:01:03,800
עס זיך.

19
00:01:03,800 --> 00:01:06,890
מיר וויסן אַז מיר ווילן די רשימה צו זייַן אין אַסענדינג סדר.

20
00:01:06,890 --> 00:01:10,200
אַזוי מיר וועט ווילן צו בויען אַרויף די אויסגעשטעלט חלק פון אונדזער רשימה

21
00:01:10,200 --> 00:01:13,280
פון לינקס צו רעכט, קלענסטער צו גרעסטן.

22
00:01:13,280 --> 00:01:17,970
צו טאָן וואָס, מיר וועט דאַרפֿן צו געפֿינען די מינימום ונסאָרטעד עלעמענט

23
00:01:17,970 --> 00:01:21,350
און שטעלן אים אין די סוף פון די אויסגעשטעלט חלק.

24
00:01:21,350 --> 00:01:25,370
זינט דעם רשימה איז ניט אויסגעשטעלט, די בלויז וועג צו טאָן וואָס איז צו

25
00:01:25,370 --> 00:01:29,330
קוק אין יעדער עלעמענט אין דער ונסאָרטעד חלק, רימעמבערינג

26
00:01:29,330 --> 00:01:32,010
וואָס עלעמענט איז די לאָואַסט און קאַמפּערינג

27
00:01:32,010 --> 00:01:33,770
יעדער עלעמענט צו וואָס.

28
00:01:33,770 --> 00:01:36,150
אַזוי מיר וועט ערשטער קוקן בייַ די 23.

29
00:01:36,150 --> 00:01:38,650
דאס איז דער ערשטער עלעמענט מיר ווע געזען, אַזוי מיר וועט געדענקען

30
00:01:38,650 --> 00:01:40,050
עס ווי די מינימום.

31
00:01:40,050 --> 00:01:42,320
ווייַטער מיר וועט קוקן אין 42.

32
00:01:42,320 --> 00:01:46,720
42 איז גרעסערע ווי 23, אַזוי 23 איז נאָך די מינימום.

33
00:01:46,720 --> 00:01:51,210
ווייַטער איז די 4 וואָס איז ווייניקער ווי 23, אַזוי מיר וועט געדענקען 4

34
00:01:51,210 --> 00:01:52,880
ווי די נייַ מינימום.

35
00:01:52,880 --> 00:01:56,380
ווייַטער איז 16 וואָס איז גרעסערע ווי 4, אַזוי 4

36
00:01:56,380 --> 00:01:57,980
איז נאָך די מינימום.

37
00:01:57,980 --> 00:02:03,670
8 איז גרעסערע ווי 4, און 15 איז גרעסערע ווי 4, אַזוי 4 מוזן זייַן

38
00:02:03,670 --> 00:02:05,980
דער קלענסטער ונסאָרטעד עלעמענט.

39
00:02:05,980 --> 00:02:09,350
אַזוי אַפֿילו כאָטש ווי יומאַנז מיר קענען תיכף זען אַז 4 איז

40
00:02:09,350 --> 00:02:12,300
די מינימום עלעמענט, אונדזער אַלגערידאַם דאַרף צו קוקן בייַ

41
00:02:12,300 --> 00:02:15,710
יעדער ונסאָרטעד עלעמענט, אַפֿילו נאָך מיר ווע געפונען די 4 - דער

42
00:02:15,710 --> 00:02:16,860
מינימום עלעמענט.

43
00:02:16,860 --> 00:02:19,900
אַזוי איצט אַז מיר ווע געפונען די מינימום עלעמענט, 4, מיר וועט וועלן

44
00:02:19,900 --> 00:02:23,410
צו מאַך עס אין די אויסגעשטעלט חלק פון די רשימה.

45
00:02:23,410 --> 00:02:27,320
זינט דאס איז דער ערשטער שריט, דעם מיטל מיר וועלן צו שטעלן 4 בייַ

46
00:02:27,320 --> 00:02:29,680
דער אָנהייב פון דער רשימה.

47
00:02:29,680 --> 00:02:33,040
רעכט איצט 23 איז בייַ דעם אָנהייב פון דער רשימה, אַזוי

48
00:02:33,040 --> 00:02:36,080
לאָזן ס ויסבייַטן די 4 און די 23.

49
00:02:36,080 --> 00:02:38,870
אַזוי איצט אונדזער רשימה קוקט ווי דעם.

50
00:02:38,870 --> 00:02:42,710
מיר וויסן אַז 4 מוזן זייַן אין זייַן לעצט אָרט, ווייַל עס איז

51
00:02:42,710 --> 00:02:45,890
ביידע דער קלענסטער עלעמענט און די עלעמענט אין די אָנהייב

52
00:02:45,890 --> 00:02:46,960
פון די רשימה.

53
00:02:46,960 --> 00:02:50,650
אַזוי דעם מיטל וואָס מיר טאָן ניט אלץ דאַרפֿן צו מאַך עס ווידער.

54
00:02:50,650 --> 00:02:53,910
אַזוי לאָזן ס איבערחזרן דעם פּראָצעס צו לייגן אן אנדער עלעמענט צו די

55
00:02:53,910 --> 00:02:55,910
אויסגעשטעלט חלק פון די רשימה.

56
00:02:55,910 --> 00:02:58,950
מיר וויסן אַז מיר טאָן ניט דאַרפֿן צו קוקן בייַ די 4, ווייַל עס ס

57
00:02:58,950 --> 00:03:00,000
שוין אויסגעשטעלט.

58
00:03:00,000 --> 00:03:03,540
אַזוי מיר קענען אָנהייבן בייַ די 42, וואָס מיר וועט געדענקען ווי דער

59
00:03:03,540 --> 00:03:05,290
מינימום עלעמענט.

60
00:03:05,290 --> 00:03:08,700
אַזוי ווייַטער מיר וועט קוקן אין די 23 וואָס איז ווייניקער ווי 42, אַזוי מיר

61
00:03:08,700 --> 00:03:11,620
געדענקען 23 איז די נייַ מינימום.

62
00:03:11,620 --> 00:03:14,870
ווייַטער מיר זען די 16 וואָס איז ווייניקער ווי 23, אַזוי

63
00:03:14,870 --> 00:03:16,800
16 איז די נייַ מינימום.

64
00:03:16,800 --> 00:03:19,720
איצט מיר קוקן אין די 8 וואָס איז ווייניקער ווי 16, אַזוי

65
00:03:19,720 --> 00:03:21,130
8 איז די נייַ מינימום.

66
00:03:21,130 --> 00:03:25,900
און לעסאָף 8 איז ווייניקער ווי 15, אַזוי מיר וויסן אַז 8 איז אַ מינימום

67
00:03:25,900 --> 00:03:27,780
ונסאָרטעד עלעמענט.

68
00:03:27,780 --> 00:03:30,660
אַזוי אַז מיטל מיר זאָל צוגעבן 8 צו די אויסגעשטעלט

69
00:03:30,660 --> 00:03:32,450
חלק פון די רשימה.

70
00:03:32,450 --> 00:03:35,990
רעכט איצט 4 איז דער בלויז אויסגעשטעלט עלעמענט, אַזוי מיר ווילן צו אָרט

71
00:03:35,990 --> 00:03:38,410
די 8 ווייַטער צו די 4.

72
00:03:38,410 --> 00:03:41,920
זינט 42 איז דער ערשטער עלעמענט אין דער ונסאָרטעד חלק פון די

73
00:03:41,920 --> 00:03:47,260
רשימה, מיר וועט ווילן צו ויסבייַטן די 42 און די 8.

74
00:03:47,260 --> 00:03:49,680
אַזוי איצט אונדזער רשימה קוקט ווי דעם.

75
00:03:49,680 --> 00:03:53,830
4 און 8 פאָרשטעלן די אויסגעשטעלט חלק פון דער רשימה, און די

76
00:03:53,830 --> 00:03:56,440
רוען נומערן פאָרשטעלן די ונסאָרטעד

77
00:03:56,440 --> 00:03:58,260
חלק פון די רשימה.

78
00:03:58,260 --> 00:04:00,630
אַזוי לאָזן ס פאָרזעצן מיט אנדערן יטעראַטיאָן.

79
00:04:00,630 --> 00:04:03,850
מיר אָנהייבן מיט 23 דעם צייַט, זינט מיר טאָן ניט דאַרפֿן צו קוקן בייַ

80
00:04:03,850 --> 00:04:05,770
די 4 און דער 8 ענימאָר ווייַל זיי ווע

81
00:04:05,770 --> 00:04:07,660
שוין געווען אויסגעשטעלט.

82
00:04:07,660 --> 00:04:10,270
16 איז ווייניקער ווי 23, אַזוי מיר וועט געדענקען

83
00:04:10,270 --> 00:04:12,070
16 ווי די נייַ מינימום.

84
00:04:12,070 --> 00:04:18,149
16 איז ווייניקער ווי 42, אָבער 15 איז ווייניקער ווי 16, אַזוי 15 מוזן זייַן

85
00:04:18,149 --> 00:04:20,480
די מינימום ונסאָרטעד עלעמענט.

86
00:04:20,480 --> 00:04:24,580
אַזוי איצט מיר ווילן צו ויסבייַטן די 15 און די 23 צו

87
00:04:24,580 --> 00:04:26,310
געבן אונדז דעם רשימה.

88
00:04:26,310 --> 00:04:30,500
די אויסגעשטעלט חלק פון דער רשימה באשטייט פון 4, 8 און 15, און

89
00:04:30,500 --> 00:04:33,210
די יסודות זענען נאָך ונסאָרטעד.

90
00:04:33,210 --> 00:04:36,900
אבער עס פּונקט אַזוי כאַפּאַנז אַז דער ווייַטער ונסאָרטעד עלעמענט, 16,

91
00:04:36,900 --> 00:04:38,480
איז שוין אויסגעשטעלט.

92
00:04:38,480 --> 00:04:42,060
אבער, עס ס קיין וועג פֿאַר אונדזער אַלגערידאַם צו וויסן אַז 16

93
00:04:42,060 --> 00:04:45,230
איז שוין אין זייַן ריכטיק אָרט, אַזוי מיר נאָך דאַרפֿן צו

94
00:04:45,230 --> 00:04:47,870
איבערחזרן פּונקט דער זעלביקער פּראָצעס.

95
00:04:47,870 --> 00:04:53,750
אַזוי מיר זען אַז 16 איז ווייניקער ווי 42, און 16 איז ווייניקער ווי 23, אַזוי

96
00:04:53,750 --> 00:04:56,230
16 מוזן זייַן די מינימום עלעמענט.

97
00:04:56,230 --> 00:04:59,010
עס ס אוממעגלעך צו ויסבייַטן דעם עלעמענט מיט זיך, אַזוי מיר קענען

98
00:04:59,010 --> 00:05:01,780
פשוט לאָזן עס אין דעם אָרט.

99
00:05:01,780 --> 00:05:04,660
אַזוי מיר דאַרפֿן איינער מער פאָרן פון אונדזער אַלגערידאַם.

100
00:05:04,660 --> 00:05:09,370
42 איז גרעסער ווי 23, אַזוי 23 מוזן זייַן די

101
00:05:09,370 --> 00:05:10,970
מינימום ונסאָרטעד עלעמענט.

102
00:05:10,970 --> 00:05:17,410
אַמאָל מיר ויסבייַטן די 23 און די 42, מיר סוף זיך מיט אונדזער לעצט

103
00:05:17,410 --> 00:05:18,530
אויסגעשטעלט רשימה -

104
00:05:18,530 --> 00:05:23,390
4, 8, 15, 16, 23, 42.

105
00:05:23,390 --> 00:05:26,830
מיר וויסן 42 מוזן זייַן אין די ריכטיק אָרט זינט עס ס די

106
00:05:26,830 --> 00:05:30,210
בלויז עלעמענט לינקס, און אַז ס סעלעקציע סאָרט.

107
00:05:30,210 --> 00:05:32,100
זאל ס איצט פאָרמאַלייז אונדזער אַלגערידאַם מיט עטלעכע

108
00:05:32,100 --> 00:05:34,540
פּסעודאָקאָדע.

109
00:05:34,540 --> 00:05:37,760
אויף שורה איין, מיר קענען זען אַז מיר דאַרפֿן צו ויסשטימען איבער

110
00:05:37,760 --> 00:05:39,530
יעדער עלעמענט פון דער רשימה.

111
00:05:39,530 --> 00:05:42,150
אַחוץ די לעצטע עלעמענט, זינט די 1 עלעמענט

112
00:05:42,150 --> 00:05:44,230
רשימה איז שוין אויסגעשטעלט.

113
00:05:44,230 --> 00:05:48,100
אויף שורה צוויי, מיר באַטראַכטן די ערשטער עלעמענט פון דער ונסאָרטעד

114
00:05:48,100 --> 00:05:51,080
חלק פון דער רשימה צו זייַן דעם מינימום, ווי מיר האט מיט אונדזער

115
00:05:51,080 --> 00:05:53,750
בייַשפּיל, אַזוי מיר האָבן עפּעס צו פאַרגלייַכן צו.

116
00:05:53,750 --> 00:05:57,260
שורה דרייַ הייבט אַ רגע שלייף אין וואָס מיר יטעראַטע איבער

117
00:05:57,260 --> 00:05:59,170
יעדער ונסאָרטעד עלעמענט.

118
00:05:59,170 --> 00:06:02,150
מיר וויסן אַז נאָך איך יטעראַטיאָנס, די אויסגעשטעלט חלק

119
00:06:02,150 --> 00:06:05,330
פון אונדזער רשימה מוזן האָבן איך יסודות אין עס זינט יעדער שריט

120
00:06:05,330 --> 00:06:06,890
סאָרץ איין עלעמענט.

121
00:06:06,890 --> 00:06:11,770
אַזוי דער ערשטער ונסאָרטעד עלעמענט מוזן זייַן אין שטעלע איך פּלוס 1.

122
00:06:11,770 --> 00:06:15,440
אויף שורה פיר, מיר פאַרגלייַכן די קראַנט עלעמענט צו די מינימום

123
00:06:15,440 --> 00:06:17,750
עלעמענט וואָס מיר ווע געזען אַזוי ווייַט.

124
00:06:17,750 --> 00:06:20,560
אויב די קראַנט עלעמענט איז קלענערער ווי די מינימום

125
00:06:20,560 --> 00:06:23,870
עלעמענט, דעמאָלט מיר געדענקען די קראַנט עלעמענט ווי די נייַ

126
00:06:23,870 --> 00:06:26,250
מינימום אויף שורה פינף.

127
00:06:26,250 --> 00:06:29,900
צום סוף, אויף שורות זעקס און זיבן, מיר ויסבייַטן די מינימום

128
00:06:29,900 --> 00:06:33,080
עלעמענט מיט דעם ערשטער ונסאָרטעד עלעמענט, דערמיט

129
00:06:33,080 --> 00:06:36,990
אַדינג עס צו די אויסגעשטעלט חלק פון די רשימה.

130
00:06:36,990 --> 00:06:40,030
אַמאָל מיר האָבן אַ אַלגערידאַם, אַ וויכטיק קשיא צו פרעגן

131
00:06:40,030 --> 00:06:43,370
זיך ווי פּראָוגראַמערז איז ווי לאַנג האט וואָס נעמען?

132
00:06:43,370 --> 00:06:46,970
מיר וועט ערשטער פרעגן די קשיא ווי לאַנג טוט עס נעמען פֿאַר דעם

133
00:06:46,970 --> 00:06:50,070
אַלגערידאַם צו לויפן אין די ערגסט פאַל?

134
00:06:50,070 --> 00:06:51,640
צוריקרופן מיר פאָרשטעלן דעם פליסנדיק

135
00:06:51,640 --> 00:06:55,060
צייַט מיט גרויס אָ נאָוטיישאַן.

136
00:06:55,060 --> 00:06:58,650
אין סדר צו באַשליסן די מינימום ונסאָרטעד עלעמענט, מיר

137
00:06:58,650 --> 00:07:01,880
יסענשאַלי האט צו פאַרגלייַכן יעדער עלעמענט אין דער רשימה צו

138
00:07:01,880 --> 00:07:04,040
יעדער אַנדערער עלעמענט אין דער רשימה.

139
00:07:04,040 --> 00:07:08,430
ינטויטיוולי, דעם סאָונדס ווי אַן אָ פון N סקווערד אָפּעראַציע.

140
00:07:08,430 --> 00:07:12,050
קוקן בייַ אונדזער פּסעודאָקאָדע, מיר אויך האָבן אַ שלייף נעסטעד ין

141
00:07:12,050 --> 00:07:14,420
אן אנדער שלייף, וואָס טאַקע סאָונדס ווי אַן אָ

142
00:07:14,420 --> 00:07:16,480
פון N סקווערד אָפּעראַציע.

143
00:07:16,480 --> 00:07:19,250
אבער, געדענקען אַז מיר האבן נישט דאַרפֿן צו קוק איבער די

144
00:07:19,250 --> 00:07:23,460
גאנצע רשימה ווען דיטערמאַנינג די מינימום ונסאָרטעד עלעמענט?

145
00:07:23,460 --> 00:07:26,600
אַמאָל מיר געוואוסט אַז די 4 איז געווען אויסגעשטעלט, פֿאַר בייַשפּיל, מיר האבן ניט

146
00:07:26,600 --> 00:07:28,170
דאַרפֿן צו קוקן בייַ אים ווידער.

147
00:07:28,170 --> 00:07:31,020
אַזוי טוט דעם נידעריקער דער פליסנדיק צייַט?

148
00:07:31,020 --> 00:07:34,510
פֿאַר אונדזער רשימה פון לענג 6, מיר דארף צו מאַכן פינף

149
00:07:34,510 --> 00:07:37,990
קאַמפּעראַסאַנז פֿאַר דער ערשטער עלעמענט, פיר קאַמפּעראַסאַנז פֿאַר

150
00:07:37,990 --> 00:07:40,750
די רגע עלעמענט, און אַזוי אויף.

151
00:07:40,750 --> 00:07:44,690
אַז מיטל אַז די גאַנץ נומער פון טריט איז דער סאַכאַקל פון

152
00:07:44,690 --> 00:07:49,160
די ינטאַדזשערז פון 1 צו די לענג פון די רשימה מינוס 1.

153
00:07:49,160 --> 00:07:51,005
מיר קענען פאָרשטעלן דעם מיט אַ סאַמיישאַן.

154
00:07:57,980 --> 00:07:59,910
מיר וועלן נישט גיין אין סאַמיישאַנז דאָ.

155
00:07:59,910 --> 00:08:04,900
אבער עס טורנס אויס אַז דעם סאַמיישאַן איז גלייַך צו N מאל

156
00:08:04,900 --> 00:08:07,540
N מינוס 1 איבער 2.

157
00:08:07,540 --> 00:08:14,220
אָדער עקוויוואַלענטלי, N סקווערד איבער 2 מינוס N איבער 2.

158
00:08:14,220 --> 00:08:18,860
ווען גערעדט וועגן אַסימפּטאָטיק רונטימע, דעם N סקווערד טערמין

159
00:08:18,860 --> 00:08:22,070
איז געגאנגען צו באַהערשן דעם N טערמין.

160
00:08:22,070 --> 00:08:27,850
אַזוי סעלעקציע סאָרט איז אָ פון N סקווערד.

161
00:08:27,850 --> 00:08:31,460
צוריקרופן אַז אין אונדזער בייַשפּיל, סעלעקציע סאָרט נאָך דארף צו

162
00:08:31,460 --> 00:08:33,850
טשעק אויב אַ נומער וואָס איז שוין אויסגעשטעלט

163
00:08:33,850 --> 00:08:35,450
דארף צו זייַן אריבערגעפארן.

164
00:08:35,450 --> 00:08:38,929
אַזוי אַז מיטל אַז אויב מיר געלאפן סעלעקציע סאָרט איבער אַן שוין

165
00:08:38,929 --> 00:08:43,070
אויסגעשטעלט רשימה, עס וואָלט דאַרפן די זעלבע נומער פון טריט ווי עס

166
00:08:43,070 --> 00:08:46,340
וואָלט ווען פליסנדיק איבער אַ גאָר ונסאָרטעד רשימה.

167
00:08:46,340 --> 00:08:51,470
אַזוי סעלעקציע סאָרט האט אַ בעסטער פאַל פאָרשטעלונג פון N סקווערד,

168
00:08:51,470 --> 00:08:56,820
וואָס מיר פאָרשטעלן מיט תוו N סקווערד.

169
00:08:56,820 --> 00:08:58,600
און אַז ס עס פֿאַר סעלעקציע סאָרט.

170
00:08:58,600 --> 00:09:00,630
נאָר איינער פון די פילע אַלגערידאַמז מיר קענען

171
00:09:00,630 --> 00:09:02,390
נוצן צו סאָרט אַ רשימה.

172
00:09:02,390 --> 00:09:05,910
מייַן נאָמען איז טאַמי, און דאָס איז קס50.