1
00:00:00,000 --> 00:00:02,290
[Powered by Google Translate] [செருகும் வரிசையாக்கம்]

2
00:00:02,290 --> 00:00:04,240
[டாமி MacWilliam] [ஹார்வர்ட் பல்கலைக்கழகம்]

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
>> அவ்வாறு செய்ய, நாம் 23 முதல் 42 ஒப்பிட்டு வேண்டும் - எங்கள் வரிசைப்படுத்தப்பட்ட பகுதியில் மட்டும் உறுப்பு இதுவரை.

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
நாங்கள் 42 வலது 4 வைக்க வேண்டும் என்றால், எங்கள் பட்டியலில் பொருட்டு வெளியே இருக்கும்.

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 அதிகமாக இருக்கும். நாம் 4 மற்றும் 23 இடையே 16 சேர்க்க விரும்புகிறேன் போன்ற, அது தெரிகிறது.

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
எனவே, நாம் 4 மற்றும் 16 இடையே 8 சேர்க்க விரும்புகிறேன்.

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
>> நாம், அதை நிலை J செருக, பரவாயில்லை என்று

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
நாம் பிக் O குறிப்புமுறை இந்த நேரத்தை குறிக்கும் என்று நினைவு.

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 / 2 - சமமான n ^ 2/2 என்பது 2 க்கும், - n (1 n).

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
என் பெயர் டாமி, மற்றும் இந்த CS50 உள்ளது.

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
ஓ, நாம் தான் காரணம் - >> பூம்!