1
00:00:00,000 --> 00:00:02,290
[Powered by Google Translate] [ינסערטיאָן סאָרט]

2
00:00:02,290 --> 00:00:04,240
[טאַמי מאַקווילליאַם] [האַרוואַרד אוניווערסיטעט]

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
אַזוי, לאָזן ס נעמען אַ קוק בייַ עטלעכע פּסעודאָקאָדע וואָס באשרייבט די טריט מיר נאָר געטאן.

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, מיר רע יטעראַטינג דורך די אויסגעשטעלט חלק פון רעכט צו לינקס.

73
00:05:20,980 --> 00:05:26,010
מיר ווילן צו האַלטן יטעראַטינג אַמאָל די עלעמענט צו די לינקס פון אונדזער קראַנט שטעלע

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
>> מיר וויסן אַז עס ס אָוקיי צו אַרייַנלייגן אין שטעלע דזש,

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
צוריקרופן אַז מיר פאָרשטעלן דעם פליסנדיק צייַט מיט גרויס אָ נאָוטיישאַן.

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
ינטויטיוולי, דעם סאָונדס ווי אַן אָ (N ^ 2) אָפּעראַציע.

90
00:06:47,950 --> 00:06:51,840
>> קוקן בייַ אונדזער פּסעודאָקאָדע, מיר האָבן אַ שלייף נעסטעד ין אנדערן שלייף,

91
00:06:51,840 --> 00:06:55,290
וואָס, טאַקע, סאָונדס ווי אַן אָ (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 (ען - 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
אַזוי, ינסערשאַן סאָרט איז גרויס אָ (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
מייַן נאָמען איז טאַמי, און דאָס איז קס50.

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
אָה, מיר האבן וואָס - >> בום!