1
00:00:00,500 --> 00:00:02,840
[Powered by Google Translate] [בלאָז סאָרט]

2
00:00:02,840 --> 00:00:04,560
[זשעקסאן סטיינגקאַמפּ האַרוואַרד אוניווערסיטעט]

3
00:00:04,560 --> 00:00:07,500
[דעם איז קס50. קס50טוו]

4
00:00:08,000 --> 00:00:11,730
בלאָז סאָרט איז אַ בייַשפּיל פון אַ סאָרטינג אַלגערידאַם -

5
00:00:11,730 --> 00:00:14,460
וואָס איז, אַ פּראָצעדור פֿאַר סאָרטינג אַ גאַנג פון עלעמענטן אין

6
00:00:14,460 --> 00:00:15,840
אַסענדינג אָדער אראפנידערן סדר.

7
00:00:15,840 --> 00:00:18,710
פֿאַר בייַשפּיל, אויב איר געוואלט צו סאָרט אַ מענגע קאַנסיסטינג פון די נומערן

8
00:00:18,710 --> 00:00:23,060
[3, 5, 2, 9], אַ ריכטיק ימפּלאַמענטיישאַן פון בלאָז סאָרט וואָלט צוריקקומען די

9
00:00:23,060 --> 00:00:26,260
אויסגעשטעלט מענגע [2, 3, 5, 9] אין אַסענדינג סדר.

10
00:00:26,260 --> 00:00:28,850
איצט, איך בין געגאנגען צו דערקלערן אין פּסעודאָקאָדע ווי די אַלגערידאַם אַרבעט.

11
00:00:28,850 --> 00:00:34,000
>> זאל ס זאָגן מיר רע סאָרטינג אַ רשימה פון 5 ינטאַדזשערז - 3, 2, 9, 6, און 5.

12
00:00:34,000 --> 00:00:37,650
די אַלגערידאַם סטאַרץ דורך קוקן בייַ די ערשטער צוויי עלעמענטן, 3 און 2,

13
00:00:37,650 --> 00:00:40,850
און קאָנטראָלירונג אויב זיי ניטאָ אויס פון סדר קאָרעוו צו יעדער אַנדערער.

14
00:00:40,850 --> 00:00:43,150
זיי זענען - 3 איז גרעסער ווי 2.

15
00:00:43,150 --> 00:00:45,190
צו זייַן אין אַסענדינג סדר, זיי זאָל זייַן די אנדערע וועג אַרום.

16
00:00:45,190 --> 00:00:46,610
אַזוי, מיר ויסבייַטן זיי.

17
00:00:46,610 --> 00:00:49,760
איצט דער רשימה קוקט ווי דאָס: [2, 3, 9, 6, 5].

18
00:00:49,760 --> 00:00:52,450
>> ווייַטער, מיר קוקן אין די רגע און דריט עלעמענטן, 3 און 9.

19
00:00:52,450 --> 00:00:55,770
זיי ניטאָ אין דער ריכטיק סדר קאָרעוו צו יעדער אַנדערער.

20
00:00:55,770 --> 00:00:58,800
וואָס איז, 3 איז ווייניקער ווי 9 אַזוי די אַלגערידאַם טוט נישט ויסבייַטן זיי.

21
00:00:58,800 --> 00:01:01,900
ווייַטער, מיר קוקן בייַ 9 און 6. זיי ניטאָ אויס פון סדר.

22
00:01:01,900 --> 00:01:04,260
>> אַזוי, מיר דאַרפֿן צו ויסבייַטן זיי ווייַל 9 איז גרעסער ווי 6.

23
00:01:04,260 --> 00:01:08,840
לאַסטלי, מיר קוקן אין די לעצטע צוויי ינטאַדזשערז, 9 און 5.

24
00:01:08,840 --> 00:01:10,850
זיי ניטאָ אויס פון סדר, אַזוי זיי מוזן זייַן סוואָפּט.

25
00:01:10,850 --> 00:01:13,360
נאָך דער ערשטער גאַנץ פאָרן דורך דער רשימה,

26
00:01:13,360 --> 00:01:17,140
עס קוקט ווי דאָס: [2, 3, 6, 5, 9].

27
00:01:17,140 --> 00:01:19,690
נישט שלעכט. עס ס כּמעט אויסגעשטעלט.

28
00:01:19,690 --> 00:01:22,450
אבער מיר דאַרפֿן צו לויפן דורך דער רשימה ווידער צו באַקומען עס גאָר אויסגעשטעלט.

29
00:01:22,450 --> 00:01:29,250
צוויי איז ווייניקער ווי 3, אַזוי מיר טאָן ניט ויסבייַטן זיי.

30
00:01:29,250 --> 00:01:31,700
>> דרייַ איז ווייניקער ווי 6, אַזוי מיר טאָן ניט ויסבייַטן זיי.

31
00:01:31,700 --> 00:01:35,500
זעקס איז גרעסער ווי 5. מיר סוואָפּט.

32
00:01:35,500 --> 00:01:38,460
זעקס איז ווייניקער ווי 9. מיר טאָן ניט ויסבייַטן.

33
00:01:38,460 --> 00:01:42,170
נאָך די רגע פאָרן דורך, עס קוקט ווי דאָס: [2, 3, 5, 6, 9]. גאנץ.

34
00:01:42,170 --> 00:01:44,680
איצט, לאָזן ס שרייַבן עס אין פּסעודאָקאָדע.

35
00:01:44,680 --> 00:01:48,450
בייסיקלי, פֿאַר יעדער עלעמענט אין דער רשימה, מיר דאַרפֿן צו קוקן בייַ אים

36
00:01:48,450 --> 00:01:50,060
און די עלעמענט גלייַך צו זייַן רעכט.

37
00:01:50,060 --> 00:01:53,420
אויב זיי זענען אויס פון סדר קאָרעוו צו יעדער אנדערע - וואָס איז, אויב דער עלעמענט אויף די לינקס

38
00:01:53,420 --> 00:01:56,810
איז גרעסער ווי דער איינער אויף די רעכט - מיר זאָל ויסבייַטן די צוויי יסודות.

39
00:01:56,810 --> 00:02:01,270
>> מיר טאָן דעם פֿאַר יעדער עלעמענט פון דער רשימה, און מיר 'ווע געמאכט איינער פאָרן דורך.

40
00:02:01,270 --> 00:02:05,160
איצט מיר נאָר האָבן צו טאָן דעם פאָרן-דורך גענוג מאל צו ענשור די רשימה

41
00:02:05,160 --> 00:02:06,480
איז גאָר, רעכט אויסגעשטעלט.

42
00:02:06,480 --> 00:02:08,889
אבער ווי פילע מאל טאָן מיר האָבן צו פאָרן דורך די רשימה צו

43
00:02:08,889 --> 00:02:10,400
גאַראַנטירן אַז מיר רע געטאן?

44
00:02:10,400 --> 00:02:14,730
נו, די ערגסט-פאַל סצענאַר איז אויב מיר האָבן אַ גאָר קאַפּויער רשימה.

45
00:02:14,730 --> 00:02:17,840
דעמאָלט עס נעמט אַ נומער פון פאָרן-טרוז גלייַך צו די נומער

46
00:02:17,840 --> 00:02:19,730
פון עלעמענטן N-1.

47
00:02:19,730 --> 00:02:24,720
אויב דאָס טוט נישט מאַכן זינען ינטויטיוולי, טראַכטן פון אַ פּשוט פאַל - דער רשימה [2, 1].

48
00:02:24,720 --> 00:02:28,430
>> דאס איז געגאנגען צו נעמען איין פאָרן-דורך צו סאָרט ריכטיק.

49
00:02:28,430 --> 00:02:33,060
[3, 2, 1] - די ערגסט פאַל איז אַז מיט 3 יסודות אויסגעשטעלט קאַפּויער,

50
00:02:33,060 --> 00:02:34,830
עס ס געגאנגען צו נעמען 2 יטעראַטיאָנס צו סאָרט.

51
00:02:34,830 --> 00:02:37,980
נאָך איינער יטעראַטיאָן, עס ס [2, 1, 3].

52
00:02:37,980 --> 00:02:39,550
די רגע ייעלדס די אויסגעשטעלט מענגע [1, 2, 3].

53
00:02:39,550 --> 00:02:43,350
אַזוי איר וויסן איר קיינמאָל האָבן צו גיין דורך די מענגע, אין אַלגעמיין,

54
00:02:43,350 --> 00:02:46,790
מער ווי N-1 מאל, ווו ען איז די נומער פון עלעמענטן אין דער מענגע.

55
00:02:47,090 --> 00:02:50,470
עס ס גערופן בלאָז סאָרט ווייַל דער גרעסטער יסודות טענד צו 'בלאָז-אַרויף'

56
00:02:50,470 --> 00:02:51,950
צו די רעכט שיין געשווינד.

57
00:02:51,950 --> 00:02:53,980
אין פאַקט, דעם אַלגערידאַם האט זייער טשיקאַווע נאַטור.

58
00:02:53,980 --> 00:02:57,410
>> נאָך עם יטעראַטיאָנס דורך די גאנצע מענגע,

59
00:02:57,410 --> 00:02:59,000
די ריגהטמאָסט ב עלעמענטן זענען געראַנטיד

60
00:02:59,000 --> 00:03:01,000
צו זייַן אויסגעשטעלט אין זייער ריכטיק אָרט.

61
00:03:01,000 --> 00:03:02,280
אויב איר ווילן צו זען דאָס פֿאַר זיך,

62
00:03:02,280 --> 00:03:05,500
מיר קענען פּרובירן עס אויף אַ גאָר קאַפּויער רשימה [9, 6, 5, 3, 2].

63
00:03:05,500 --> 00:03:08,220
נאָך איינער פאָרן דורך די גאנצע רשימה,

64
00:03:08,220 --> 00:03:09,220
[געזונט פון שרייבן]

65
00:03:09,220 --> 00:03:18,790
[6, 9, 5, 3, 2], [6, 5, 9, 3, 2], [6, 5, 3, 9, 2], [6, 5, 3, 2, 9]

66
00:03:18,790 --> 00:03:21,250
די ריגהטמאָסט עלעמענט 9 איז אין זייַן געהעריק אָרט.

67
00:03:21,250 --> 00:03:24,760
נאָך די רגע פאָרן-דורך, די 6 וועט האָבן 'באַבאַלד-אַרויף' צו די

68
00:03:24,760 --> 00:03:26,220
רגע ריגהטמאָסט אָרט.

69
00:03:26,220 --> 00:03:28,840
די צוויי עלעמענטן אויף די רעכט - 6 און 9 - וועט זייַן אין זייער ריכטיק ערטער

70
00:03:28,840 --> 00:03:30,580
נאָך דער ערשטער צוויי פאָרן-טרוז.

71
00:03:30,580 --> 00:03:32,590
>> אַזוי, ווי קענען מיר נוצן דאָס צו אַפּטאַמייז די אַלגערידאַם?

72
00:03:32,590 --> 00:03:34,850
נו, נאָך איינער יטעראַטיאָן דורך די מענגע

73
00:03:34,850 --> 00:03:37,690
מיר טאָן נישט פאקטיש דאַרפֿן צו קאָנטראָלירן די ריגהטמאָסט עלעמענט

74
00:03:37,690 --> 00:03:39,200
ווייַל מיר וויסן עס ס אויסגעשטעלט.

75
00:03:39,200 --> 00:03:43,050
נאָך צוויי יטעראַטיאָנס, מיר וויסן פֿאַר זיכער די ריגהטמאָסט צוויי עלעמענטן זענען אין פּלאַץ.

76
00:03:43,050 --> 00:03:48,260
אַזוי, אין אַלגעמיין, נאָך ק יטעראַטיאָנס דורך די פול מענגע,

77
00:03:48,260 --> 00:03:51,550
קאָנטראָלירונג די לעצטע ק עלעמענטן איז יבעריק זינט מיר וויסן

78
00:03:51,550 --> 00:03:52,360
זיי ניטאָ אין דער ריכטיק אָרט שוין.

79
00:03:52,360 --> 00:03:54,870
>> אַזוי אויב איר ניטאָ סאָרטינג אַ מענגע פון ​​N עלעמענטן,

80
00:03:54,870 --> 00:03:57,870
אויף דער ערשטער יטעראַטיאָן - יול האָבן צו סאָרט אַלע פון ​​די יסודות - דער ערשטער N-0.

81
00:03:57,870 --> 00:04:04,170
אויף דער רגע יטעראַטיאָן, איר וועט האָבן צו קוקן אין אַלע פון ​​די יסודות אָבער די לעצט -

82
00:04:04,170 --> 00:04:07,090
דער ערשטער N-1.

83
00:04:07,090 --> 00:04:10,520
אן אנדער אַפּטאַמאַזיישאַן זאל זייַן צו טשעק אויב די רשימה איז שוין אויסגעשטעלט

84
00:04:10,520 --> 00:04:11,710
נאָך יעדער יטעראַטיאָן.

85
00:04:11,710 --> 00:04:13,900
אויב עס ס 'שוין אויסגעשטעלט, מיר טאָן ניט דאַרפֿן צו מאַכן קיין מער יטעראַטיאָנס

86
00:04:13,900 --> 00:04:15,310
דורך דער רשימה.

87
00:04:15,310 --> 00:04:16,220
ווי קענען מיר טאָן דעם?

88
00:04:16,220 --> 00:04:19,360
נו, אויב מיר טאָן ניט מאַכן קיין סוואַפּס אויף אַ פאָרן-דורך פון דער רשימה,

89
00:04:19,360 --> 00:04:22,350
עס ס 'קלאָר אַז די רשימה איז שוין אויסגעשטעלט ווייַל מיר האבן נישט ויסבייַטן עפּעס.

90
00:04:22,350 --> 00:04:24,160
אַזוי מיר באשטימט טאָן ניט האָבן צו סאָרט ווידער.

91
00:04:24,160 --> 00:04:27,960
>> טאָמער איר קען ינישאַלייז אַ פאָן בייַטעוודיק גערופן 'נישט אויסגעשטעלט' צו

92
00:04:27,960 --> 00:04:30,990
פאַלש און טוישן עס צו אמת אויב איר האָבן צו ויסבייַטן קיין יסודות אויף

93
00:04:30,990 --> 00:04:32,290
איינער יטעראַטיאָן דורך די מענגע.

94
00:04:32,290 --> 00:04:35,350
אָדער סימילאַרלי, מאַכן אַ קאָונטער צו ציילן ווי פילע סוואַפּס איר מאַכן

95
00:04:35,350 --> 00:04:37,040
אויף קיין געגעבן יטעראַטיאָן.

96
00:04:37,040 --> 00:04:40,040
אין די סוף פון אַ יטעראַטיאָן, אויב איר האט ניט ויסבייַטן קיין פון די עלעמענטן,

97
00:04:40,040 --> 00:04:41,780
איר וויסן די רשימה איז שוין אויסגעשטעלט און איר ניטאָ געטאן.

98
00:04:41,780 --> 00:04:44,090
בלאָז סאָרט, ווי אנדערע סאָרטינג אַלגערידאַמז, קענען זייַן

99
00:04:44,090 --> 00:04:46,960
טוויקט צו אַרבעטן פֿאַר קיין עלעמענטן וואָס האָבן אַן אָרדערינג אופֿן.

100
00:04:46,960 --> 00:04:50,610
>> וואָס איז, געגעבן צוויי עלעמענטן איר האָבן אַ וועג צו זאָגן אויב דער ערשטער איינער

101
00:04:50,610 --> 00:04:53,770
איז גרעסער ווי, גלייַך צו אָדער ווייניקער ווי די רגע.

102
00:04:53,770 --> 00:04:56,870
פֿאַר בייַשפּיל, איר קען סאָרט אותיות פון דעם אלפאבעט דורך זאגן

103
00:04:56,870 --> 00:05:00,520
אַז אַ <בייטן, בייטן <C, אאז"ו ו

104
00:05:00,520 --> 00:05:03,830
אָדער איר קען סאָרט טעג פון די וואָך ווו זונטאג איז ווייניקער ווי מאנטיק

105
00:05:03,830 --> 00:05:05,110
וואָס איז ווייניקער ווי דינסטאג.

106
00:05:05,110 --> 00:05:09,630
>> בלאָז סאָרט איז דורך קיין מיטל אַ זייער עפעקטיוו אָדער פעסט סאָרטינג אַלגערידאַם.

107
00:05:09,630 --> 00:05:12,370
זייַן ערגסט-פאַל רונטימע איז גרויס אָ פון N ²

108
00:05:12,370 --> 00:05:14,810
ווייַל איר האָבן צו מאַכן N יטעראַטיאָנס דורך אַ רשימה

109
00:05:14,810 --> 00:05:18,430
קאָנטראָלירונג אַלע N יסודות יעדער פאָרן-דורך, נקסן = N ².

110
00:05:18,430 --> 00:05:22,730
דאס לויפן צייַט מיטל וואָס ווי די נומער פון עלעמענטן איר ניטאָ סאָרטינג ינקריסיז,

111
00:05:22,730 --> 00:05:24,330
די לויפן צייַט ינקריסיז קוואַדראַטיקאַללי.

112
00:05:24,330 --> 00:05:27,330
>> אבער אויב עפעקטיווקייַט איז נישט אַ הויפּט דייַגע פון ​​דיין פּראָגראַם

113
00:05:27,330 --> 00:05:29,550
אָדער אויב איר ניטאָ בלויז סאָרטינג אַ קליין נומער פון עלעמענטן,

114
00:05:29,550 --> 00:05:31,660
איר זאל געפֿינען בלאָז סאָרט נוצלעך ווייַל

115
00:05:31,660 --> 00:05:33,360
עס ס איינער פון די סימפּלאַסט סאָרטינג אַלגערידאַמז צו פֿאַרשטיין

116
00:05:33,360 --> 00:05:34,250
און צו קאָד.

117
00:05:34,250 --> 00:05:37,270
עס ס אויך אַ גרויס וועג צו באַקומען דערפאַרונג מיט איבערזעצן אַ טעאָרעטיש

118
00:05:37,270 --> 00:05:40,220
אַלגערידאַם אין פאַקטיש פאַנגקשאַנינג קאָד.

119
00:05:40,220 --> 00:05:43,000
נו, אַז ס בלאָז סאָרט פֿאַר איר. דאַנק פֿאַר וואַטשינג.

120
00:05:43,000 --> 00:05:44,000
CS50.TV