1
00:00:00,000 --> 00:00:03,360
>> [இசை]

2
00:00:03,360 --> 00:00:04,522

3
00:00:04,522 --> 00:00:06,730
டக் LLOYD: சரி,
குமிழி வரிசையாக்கம் ஒரு வழிமுறையாகும்

4
00:00:06,730 --> 00:00:08,730
நீங்கள் கூறுகளை ஒரு தொகுப்பு வரிசைப்படுத்த பயன்படுத்த முடியும்.

5
00:00:08,730 --> 00:00:10,850
அது வேலை எப்படி ஒரு பார்க்கலாம்.

6
00:00:10,850 --> 00:00:13,240
>> எனவே அடிப்படை யோசனை பின்னால்
குமிழி வரிசையாக்கம் இது.

7
00:00:13,240 --> 00:00:17,340
நாம் பொதுவாக அதிக நகர்த்த வேண்டும்
பொதுவாக வலது மதிப்பு உறுப்புகள்,

8
00:00:17,340 --> 00:00:20,340
பொதுவாக மதிப்பு உறுப்புகள் குறைக்க
இடது, நாம் எதிர்பார்ப்பதை போல.

9
00:00:20,340 --> 00:00:23,256
நாம் குறைந்த விஷயங்கள் இருக்க வேண்டும்
தொடக்கத்தில், மற்றும் அதிக விஷயங்களை

10
00:00:23,256 --> 00:00:24,970
இறுதியில் இருக்க.

11
00:00:24,970 --> 00:00:26,130
>> இதை நாம் எப்படி செய்ய வேண்டும்?

12
00:00:26,130 --> 00:00:28,040
சரி சூடோகுறியீடு குறியீடு,
நம்மால் சொல்ல முடியும்,

13
00:00:28,040 --> 00:00:30,320
ஒரு அல்லாத பூஜ்ஜியம் மதிப்பை ஒரு மாற்று எதிர் அமைக்க.

14
00:00:30,320 --> 00:00:32,570
நாம் ஒரு இரண்டாவது அதை செய்ய ஏன் நாம் பார்க்க வேண்டும்.

15
00:00:32,570 --> 00:00:36,090
பின்னர் நாம் பின்வரும் மீண்டும்
இடமாற்று கவுண்டர் 0 வரை செயல்முறை,

16
00:00:36,090 --> 00:00:39,910
அல்லது நாம் எந்த பரிமாற்றங்கள் வரை.

17
00:00:39,910 --> 00:00:43,170
>> இடமாற்று எதிர் மீட்டமை
0 அது ஏற்கனவே 0, இல்லை என்றால்.

18
00:00:43,170 --> 00:00:46,420
பின்னர் ஒவ்வொரு பார்க்க
கூறுகள் அடுத்தடுத்த ஜோடி.

19
00:00:46,420 --> 00:00:49,550
அந்த இரண்டு கூறுகள் இருந்தால்
இல்லை பொருட்டு, அவர்களை இடமாற்றம்,

20
00:00:49,550 --> 00:00:51,620
மற்றும் இடமாற்று எதிர் 1 சேர்க்க.

21
00:00:51,620 --> 00:00:53,870
நீங்கள் நினைத்துக்கொண்டு
நீங்கள் அதை கற்பனை முன்,

22
00:00:53,870 --> 00:00:57,471
இந்த குறைந்த நகர்த்த வேண்டும் என்று கவனிக்க
இடது மதிப்பு உறுப்புகள்

23
00:00:57,471 --> 00:01:00,720
மற்றும் உயர், வலது உறுப்புகள் மதிப்பு
திறம்பட நாம் என்ன செய்ய வேண்டும், என்ன செய்து,

24
00:01:00,720 --> 00:01:03,940
அந்த குழுக்கள் நகர்த்த
அந்த வழியில் கூறுகள்.

25
00:01:03,940 --> 00:01:07,035
தான் எப்படி இந்த கற்பனை நாம்
எங்கள் வரிசை பயன்படுத்தி பார்க்க வேண்டும்

26
00:01:07,035 --> 00:01:10,504
நாம் சோதிக்க பயன்படுத்தப்படும் என்று
இந்த வழிமுறைகளை வெளியே.

27
00:01:10,504 --> 00:01:13,420
நாம் இங்கே மீண்டும் ஒரு வரிசையாக்கம் செய்யப்படாத வரிசை வேண்டும்
உறுப்புகள் அனைத்தும் சுட்டிக்காட்டப்படுகிறது

28
00:01:13,420 --> 00:01:14,840
சிவப்பு இருப்பது.

29
00:01:14,840 --> 00:01:17,970
நான் என் இடமாற்று எதிர் அமைக்கிறேன்
ஒரு பூஜ்யமற்ற மதிப்பு.

30
00:01:17,970 --> 00:01:20,610
நான் தன்னிச்சையாக தேர்வு
எதிர்மறை 1 வேண்டும் அது 0, இல்லை.

31
00:01:20,610 --> 00:01:23,840
நாம் இந்த செயல்முறை மீண்டும் விரும்பவில்லை
இடமாற்று எதிர் வரை 0.

32
00:01:23,840 --> 00:01:26,540
நான் என் இடமாற்று அமைக்க ஏன் இந்த
சில அல்லாத பூஜ்ஜியம் மதிப்பை எதிர்,

33
00:01:26,540 --> 00:01:29,400
இல்லையென்றால்
இடமாற்று கவுண்டர் 0 இருக்க வேண்டும்.

34
00:01:29,400 --> 00:01:31,610
நாம் கூட தொடங்க முடியாது
படிமுறை செயல்முறை.

35
00:01:31,610 --> 00:01:33,610
எனவே மீண்டும், படிகள் மாறி
இடமாற்று வகையில் மாற்றுவது

36
00:01:33,610 --> 00:01:37,900
0, பின்னர் ஒவ்வொரு அடுத்தடுத்த பாருங்கள்
ஜோடி, மற்றும் அவர்கள் பொருட்டு வெளியே என்றால்,

37
00:01:37,900 --> 00:01:40,514
அவர்களை இடமாற்றம், 1 சேர்க்க
இடமாற்று எதிர்.

38
00:01:40,514 --> 00:01:41,680
எனவே இந்த செயல்முறை ஆரம்பிக்கலாம்.

39
00:01:41,680 --> 00:01:44,430
எனவே நாம் என்ன செய்ய முதல் விஷயம்
நாம் 0 இடமாற்று எதிர் அமைத்தோம்

40
00:01:44,430 --> 00:01:46,660
மற்றும் நாம் பார்த்து தொடங்க
ஒவ்வொரு அடுத்தடுத்த ஜோடி.

41
00:01:46,660 --> 00:01:49,140
>> எனவே நாம் முதலில் 5 மற்றும் 2 பார்த்து தொடங்க.

42
00:01:49,140 --> 00:01:52,410
நாம் அவர்கள் வெளியே என்று பார்க்கிறோம்
உத்தரவிட மற்றும் நாம் அவர்களை மாற்ற.

43
00:01:52,410 --> 00:01:53,830
நாம் பரிமாறிக்கொள்ளலாம் எதிர் 1 சேர்க்க.

44
00:01:53,830 --> 00:01:57,860
எனவே இப்போது எங்கள் இடமாற்று எதிர் 1,
மற்றும் 2 மற்றும் 5 மாற்றப்படுகிறது.

45
00:01:57,860 --> 00:01:59,370
இப்போது நாம் மீண்டும் செயல்முறை மீண்டும்.

46
00:01:59,370 --> 00:02:03,540
>> நாம் அடுத்த அடுத்தடுத்த ஜோடி பாருங்கள்,
5 மற்றும் அவர்கள் வரிசையில் போதவில்லை 1 வேண்டும்,

47
00:02:03,540 --> 00:02:06,960
நாம் அவர்களை மாற்ற மற்றும் சேர்க்க
இடமாற்று இடத்திற்கு 1.

48
00:02:06,960 --> 00:02:08,900
பின்னர் நாம் 5 மற்றும் 3 பார்.

49
00:02:08,900 --> 00:02:13,830
அவர்கள் வெளியே ஒழுங்கு, நாம் மாற்ற
அவர்களுக்கும் நாம் இடமாற்று எதிர் 1 சேர்க்க.

50
00:02:13,830 --> 00:02:15,550
பின்னர் நாம் 5 மற்றும் 6 பார்.

51
00:02:15,550 --> 00:02:18,630
அவர்கள் வரிசையில் இருக்கும், நாம் உண்மையில் இல்லை
எதையும் இந்த நேரத்தில் இடமாற்றம் செய்ய வேண்டும்.

52
00:02:18,630 --> 00:02:20,250
பின்னர் நாம் 6 மற்றும் 4 பாருங்கள்.

53
00:02:20,250 --> 00:02:24,920
அவர்கள் பொருட்டு வெளியே தான் இருக்கிறோம், நாம் மாற்ற
அவர்களுக்கும் நாம் இடமாற்று எதிர் 1 சேர்க்க.

54
00:02:24,920 --> 00:02:26,230
>> இப்போது என்ன ஆயிற்று கவனிக்கிறது.

55
00:02:26,230 --> 00:02:29,514
நாங்கள் இறுதியில் 6 அனைத்து வழி சென்றார்.

56
00:02:29,514 --> 00:02:32,180
தேர்வு மாதிரி எனவே, நீங்கள் கிடைத்தால்,
அந்த வீடியோ பார்த்திருக்கிறேன், நாம் செய்தது என்ன இருந்தது

57
00:02:32,180 --> 00:02:35,290
நாங்கள் நகரும் முடிந்தது
கட்டிடத்தில் சிறிய உறுப்புகள்

58
00:02:35,290 --> 00:02:39,640
இருந்து அடிப்படையில் வரிசைப்படுத்தப்பட்ட வரிசை
பெரிய, சிறிய வலமாக.

59
00:02:39,640 --> 00:02:43,200
குமிழி வரிசையாக்கம் வழக்கில், நாம் என்றால்
இந்த குறிப்பிட்ட வழிமுறை தொடர்ந்து,

60
00:02:43,200 --> 00:02:46,720
நாம் உண்மையில் கட்டி போகிறாய்
வலது இருந்து வரிசைப்படுத்தப்பட்ட வரிசை

61
00:02:46,720 --> 00:02:49,100
சிறிய, பெரிய இடது.

62
00:02:49,100 --> 00:02:53,840
நாம் திறம்பட 6, குதுகலித்தது
பெரிய மதிப்பு, இறுதியில் அனைத்து வழி.

63
00:02:53,840 --> 00:02:56,165
>> எனவே நாம் இப்போது அறிவிக்க முடியும்
என்று வரிசைப்படுத்தப்பட்ட என்று,

64
00:02:56,165 --> 00:02:59,130
எதிர்காலத்தில் iterations--
வரிசை நடக்கிறது மீண்டும்

65
00:02:59,130 --> 00:03:01,280
நாம் இனி 6 கருத்தில் கொள்ள வேண்டும்.

66
00:03:01,280 --> 00:03:03,850
நாம் மட்டும் கருத்தில் கொள்ள வேண்டும்
வரிசையாக்கம் செய்யப்படாத கூறுகள்

67
00:03:03,850 --> 00:03:06,299
போது நாம் அடுத்தடுத்த ஜோடிகள் தேடும்.

68
00:03:06,299 --> 00:03:08,340
எனவே நாம் ஒரு முடித்தேன்
குமிழி வரிசையாக்கம் வழியாக.

69
00:03:08,340 --> 00:03:11,941
எனவே இப்போது நாம் கேள்வி செல்ல,
இடமாற்று கவுண்டர் 0 வரை மீண்டும்.

70
00:03:11,941 --> 00:03:13,690
சரி இடமாற்று எதிர்
4 எனவே, நாங்கள் போகிறோம்

71
00:03:13,690 --> 00:03:15,410
மீண்டும் இந்த செயற்பாட்டை மீண்டும் வைக்க.

72
00:03:15,410 --> 00:03:19,180
>> நாம் இடமாற்று வகையில் மாற்றுவது போகிறோம்
0, மற்றும் ஒவ்வொரு அடுத்தடுத்த ஜோடி பாருங்கள்.

73
00:03:19,180 --> 00:03:21,890
எனவே நாம் அவர்கள் 1 வேண்டும் 2 தொடங்க மற்றும்
வெளியே ஒழுங்கு, நாம் அவர்களை மாற்ற

74
00:03:21,890 --> 00:03:23,620
மற்றும் நாம் இடமாற்று எதிர் 1 சேர்க்க.

75
00:03:23,620 --> 00:03:25,490
2 மற்றும் 3, அவர்கள் விதமாக இருக்கும்.

76
00:03:25,490 --> 00:03:27,060
அங்கே என்ன செய்ய வேண்டும் தேவையில்லை.

77
00:03:27,060 --> 00:03:28,420
3 மற்றும் 5 வரிசையில் உள்ளன.

78
00:03:28,420 --> 00:03:30,150
நாம் அங்கு எதுவும் செய்ய தேவையில்லை.

79
00:03:30,150 --> 00:03:32,515
>> 5 மற்றும் 4, அவர்கள் வெளியே இருக்கிறார்கள்
ஒழுங்கு, மற்றும் நாம்

80
00:03:32,515 --> 00:03:35,130
அவர்களை இடமாற்றம் மற்றும் சேர்க்க வேண்டும்
இடமாற்று இடத்திற்கு 1.

81
00:03:35,130 --> 00:03:38,880
இப்போது நாம், 5 சென்றார்
அடுத்த பெரிய உறுப்பு,

82
00:03:38,880 --> 00:03:40,920
வரிசையாக்கம் செய்யப்படாத பகுதியில் இறுதியில்.

83
00:03:40,920 --> 00:03:44,360
எனவே நாம் இப்போதே அழைக்க முடியும்
வரிசைப்படுத்தப்பட்ட பகுதியை பகுதி.

84
00:03:44,360 --> 00:03:47,180
>> இப்போது நீங்கள் தேடும்
திரை மற்றும் ஒருவேளை நீங்கள் சொல்ல முடியும்,

85
00:03:47,180 --> 00:03:50,130
என்னால் முடியும் வரிசை என்று
இப்போது பிரிக்கப்பட்டுள்ளது.

86
00:03:50,130 --> 00:03:51,820
ஆனால் நாம் இன்னும் என்று நிரூபிக்க முடியாது.

87
00:03:51,820 --> 00:03:54,359
நாம் ஒரு உத்தரவாதம் இல்லை
என்று அது வரிசைப்படுத்தப்பட்ட.

88
00:03:54,359 --> 00:03:56,900
ஆனால் இந்த இடத்தில் இடமாற்று ஆகிறது
எதிர் நாடகம் வந்து போகிறது.

89
00:03:56,900 --> 00:03:59,060
>> எனவே நாம் ஒரு பாஸ் நிறைவு.

90
00:03:59,060 --> 00:04:00,357
இடமாற்று எதிர் 2.

91
00:04:00,357 --> 00:04:02,190
எனவே நாம் மீண்டும் செல்கிறோம்
மீண்டும் இந்த செயற்பாட்டை,

92
00:04:02,190 --> 00:04:04,290
இடமாற்று கவுண்டர் 0 வரை மீண்டும்.

93
00:04:04,290 --> 00:04:05,550
0 இடமாற்று எதிர் மீட்டமை.

94
00:04:05,550 --> 00:04:06,820
எனவே நாம் அதை மீட்டமைக்க வேண்டும்.

95
00:04:06,820 --> 00:04:09,810
>> இப்போது ஒவ்வொரு அடுத்தடுத்த ஜோடி பாருங்கள்.

96
00:04:09,810 --> 00:04:11,880
என்று, பொருட்டு 1 மற்றும் 2 தான்.

97
00:04:11,880 --> 00:04:13,590
2 மற்றும் 3 வரிசையில் உள்ளன.

98
00:04:13,590 --> 00:04:15,010
3 மற்றும் 4 வரிசையில் உள்ளன.

99
00:04:15,010 --> 00:04:19,250
எனவே இந்த கட்டத்தில், நாம் முடித்துவிட்டேன் கவனிக்க
ஒவ்வொரு அடுத்தடுத்த ஜோடி பார்த்து,

100
00:04:19,250 --> 00:04:22,530
ஆனால் இடமாற்று எதிர் இன்னும் 0 தான்.

101
00:04:22,530 --> 00:04:25,520
>> நாங்கள் மாற இல்லை என்றால்
எந்த உறுப்புகள், அவர்கள் பின்னர்

102
00:04:25,520 --> 00:04:28,340
மூலம், வரிசையில் இருக்க வேண்டும்
இந்த செயல்முறை நல்லொழுக்கம்.

103
00:04:28,340 --> 00:04:32,000
அதனால் வகையான ஒரு திறன்,
என்று நாம் கணினி விஞ்ஞானிகள் அன்பு,

104
00:04:32,000 --> 00:04:35,560
நாம் இப்போது அறிவிக்க
முழு வரிசையில் வேண்டும்

105
00:04:35,560 --> 00:04:38,160
நாங்கள் செய்யவில்லை, ஏனெனில், வரிசைப்படுத்தப்பட்ட
எந்த உறுப்புகள் இடமாற்ற வேண்டும்.

106
00:04:38,160 --> 00:04:40,380
அந்த அழகான நன்றாக இருக்கிறது.

107
00:04:40,380 --> 00:04:43,260
>> அதனால் என்ன மோசமான வழக்கு
குமிழி வரிசையாக்கம் சூழ்நிலையில்?

108
00:04:43,260 --> 00:04:46,240
மோசமான வழக்கில் வரிசை உள்ளது
முற்றிலும் தலைகீழ் வரிசையில்,

109
00:04:46,240 --> 00:04:49,870
மற்றும் நாம் ஒவ்வொரு குமிழி வேண்டும்
பெரிய உறுப்புகள் அனைத்தும்

110
00:04:49,870 --> 00:04:51,780
வரிசை முழுவதும் வழி.

111
00:04:51,780 --> 00:04:55,350
மற்றும் நாம் திறம்பட மேலும் வேண்டும்
குமிழி சிறிய உறுப்புகள் அனைத்தும் திரும்ப

112
00:04:55,350 --> 00:04:57,050
மிகவும் வரிசை முழுவதும் அனைத்து வழி,.

113
00:04:57,050 --> 00:05:01,950
எனவே n உறுப்புகள் ஒவ்வொன்றும் செல்ல வேண்டும்
மற்ற n உறுப்புகள் அனைத்து முழுவதும்.

114
00:05:01,950 --> 00:05:04,102
அதனால் மோசமான சூழ்நிலையில் தான்.

115
00:05:04,102 --> 00:05:05,810
சிறந்த வழக்கில்
சூழ்நிலையில், இருப்பினும், இந்த ஆகிறது

116
00:05:05,810 --> 00:05:07,880
தேர்வு வகையான இருந்து சற்று வித்தியாசமாக.

117
00:05:07,880 --> 00:05:10,040
வரிசை ஏற்கனவே உள்ளது
நாங்கள் செல்லும் போது பேசி தீர்க்கப்படும்.

118
00:05:10,040 --> 00:05:12,550
நாம் எந்த செய்ய வேண்டும்
முதல் பாஸ் பரிமாற்றங்கள்.

119
00:05:12,550 --> 00:05:14,940
எனவே நாம் பார்க்க வேண்டும்
குறைவான உறுப்புகள், சரியான?

120
00:05:14,940 --> 00:05:18,580
நாம் இந்த மீண்டும் இல்லை
மடங்கிற்கும் அதிகமான எண்ணிக்கையை செயல்படுத்தவும்.

121
00:05:18,580 --> 00:05:19,540
>> அதனால் என்ன அர்த்தம்?

122
00:05:19,540 --> 00:05:22,390
அதனால் என்ன மோசமான சூழ்நிலையில் தான்
குமிழி வரிசையாக்கம், மற்றும் என்ன

123
00:05:22,390 --> 00:05:25,330
குமிழி வகையான சிறந்த வழக்கு சூழ்நிலையில்?

124
00:05:25,330 --> 00:05:27,770
நீங்கள் யூகிக்க?

125
00:05:27,770 --> 00:05:32,420
மோசமான வழக்கில் நீங்கள், மீண்டும் கூறு வேண்டும்
அனைத்து n உறுப்புகள் n முறை முழுவதும்.

126
00:05:32,420 --> 00:05:34,220
எனவே மோசமான ஸ்கொயர் n.

127
00:05:34,220 --> 00:05:36,550
>> வரிசை செய்தபின் இருந்தால்
வரிசைப்படுத்தப்பட்ட எனினும், நீங்கள் மட்டும்

128
00:05:36,550 --> 00:05:38,580
ஒவ்வொரு பார்க்க வேண்டும்
ஒரு முறை கூறுகள்.

129
00:05:38,580 --> 00:05:42,670
மற்றும் இடமாற்று எதிர் இன்னும் 0 இருந்தால்,
நீங்கள் இந்த வரிசை வரிசைப்படுத்தப்பட்டுள்ளது சொல்ல முடியும்.

130
00:05:42,670 --> 00:05:45,780
அதனால் சிறந்த வழக்கில், இந்த ஆகிறது
தேர்வை விட உண்மையில் நல்லது

131
00:05:45,780 --> 00:05:49,230
இதுவரை எங்கள் வழிமுறைகளை எந்தவொரு அது n, ஒமேகா தான்.

132
00:05:49,230 --> 00:05:50,270
>> நான் டக் லாயிட் இருக்கிறேன்.

133
00:05:50,270 --> 00:05:52,140
இந்த CS50 உள்ளது.

134
00:05:52,140 --> 00:05:54,382