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

2
00:00:02,840 --> 00:00:04,560
[JACKSON STEINKAMP ஹார்வர்ட் பல்கலைக்கழகம்]

3
00:00:04,560 --> 00:00:07,500
[இந்த CS50 உள்ளது. CS50TV]

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
>> 3, 2, 9, 6, மற்றும் 5 - நாம் 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
படிமுறை அவர்களை இடமாற்றம் இல்லை 9 விட குறைவான என்று, 3.

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
அது பல சமமாக கடந்து throughs பல எடுக்கிறது

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
ஒரு மறு செய்கை பின்னர், அது [, 3 1 2] தான்.

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 அணியின் உறுப்புகள் எண்ணிக்கை 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
rightmost மீ கூறுகள் உத்தரவாதம்

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
rightmost உறுப்பு 9 அதன் சரியான இடத்தில் உள்ளது.

67
00:03:21,250 --> 00:03:24,760
கடந்து செல்லும் இரண்டாவது பிறகு, 6 ​​'குதுகலித்தது அப்' வேண்டும்

68
00:03:24,760 --> 00:03:26,220
இரண்டாவது rightmost இடத்தில்.

69
00:03:26,220 --> 00:03:28,840
6 மற்றும் 9 - - வலது இரண்டு கூறுகள் அவற்றின் சரியான இடங்களில் இருக்கும்

70
00:03:28,840 --> 00:03:30,580
முதல் இரண்டு பாஸ்-throughs பிறகு.

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
நாம் உண்மையில் rightmost உறுப்பு பார்க்க தேவையில்லை

74
00:03:37,690 --> 00:03:39,200
எங்களுக்கு தெரியும், ஏனெனில் அது வரிசைப்படுத்தப்பட்ட.

75
00:03:39,200 --> 00:03:43,050
இரண்டு மீண்டும் பிறகு, நாம் rightmost இரண்டு கூறுகள் இடத்தில் இருக்கும் நிச்சயம் தெரியும்.

76
00:03:43,050 --> 00:03:48,260
எனவே, பொதுவாக, முழு வரிசை மூலம், k மீண்டும் பிறகு,

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
முதல் மறு செய்கை மீது - you'll கூறுகள் அனைத்து வரிசைப்படுத்த வேண்டும் - முதல் 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
ஒரு <ப, ப <கேட்ச், பல என்று

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 உறுப்புகள் சோதனை, nxn = 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