[Powered by Google Translate] [செருகும் வரிசையாக்கம்]
[டாமி MacWilliam] [ஹார்வர்ட் பல்கலைக்கழகம்]
[இந்த CS50.TV உள்ளது]
இன் செருகும் வரிசையாக்கம் பாருங்கள், எண்கள் பட்டியல் எடுத்து அவர்களை வரிசையாக்கம் ஒரு படிமுறை அழைத்து செல்லலாம்.
ஒரு வழிமுறை, நினைவில், வெறுமனே ஒரு பணியை நிறைவேற்றும் ஒரு படி படிப்படியாக செயல்முறை.
செருகும் வரிசையாக்கம் பின்னால் அடிப்படை கருத்து, இரு பகுதிகள் எங்கள் பட்டியலில் பிரிக்க வேண்டும்
ஒரு வரிசைப்படுத்தப்பட்ட பகுதி மற்றும் ஒரு வரிசையாக்கம் செய்யப்படாத பகுதி.
>> படிமுறை ஒவ்வொரு அடியிலும், பல நகர்த்தப்படுகிறது
வரிசையாக்கம் செய்யப்படாத பகுதியை இருந்து வரிசைப்படுத்தப்பட்ட பகுதிக்கு
இறுதியில் வரை முழு பட்டியல் பிரிக்கப்பட்டுள்ளது.
23, 42, 4, 16, 8, மற்றும் 15 - இங்கே ஆறு வரிசையாக்கம் செய்யப்படாத எண்களின் பட்டியல்.
இந்த எண்கள் ஏறுவரிசையில் அனைத்து இல்லை என்பதால், அவர்கள் வரிசையாக்கம் செய்யப்படாத.
நாம் இன்னும் வரிசையாக்க ஆரம்பிக்கவே இல்லை என்பதால், நாங்கள் ஆறு கூறுகளை நம் வரிசையாக்கம் செய்யப்படாத பகுதி நினைப்பாய்.
>> ஒருமுறை நாங்கள் வரிசையாக்க தொடங்க, நாம் இந்த இடது இந்த வரிசையில் எண்கள் வைக்கிறேன்.
எனவே, நாட்டின் 23, எங்கள் பட்டியலில் முதல் உறுப்பு கொண்ட ஆரம்பிப்போம்.
நாம், இதுவரை நம் வரிசைப்படுத்தப்பட்ட பகுதியில் எந்த கூறுகள் இல்லை
எனவே வெறுமனே நம் வரிசைப்படுத்தப்பட்ட பகுதியை தொடக்க மற்றும் முடிவு இருக்கும் 23 பரிசீலனை செய்வோம்.
இப்போது, நம் வரிசைப்படுத்தப்பட்ட பகுதியை ஒரு எண், 23, உள்ளது
எங்கள் வரிசையாக்கம் செய்யப்படாத பகுதியை இந்த ஐந்து எண்கள் உள்ளன.
இப்போது வரிசைப்படுத்தப்பட்டுள்ளது பகுதியை நமது வரிசையாக்கம் செய்யப்படாத பகுதி, 42, அடுத்த எண்ணை சேர்க்க வேண்டும்.
>> அவ்வாறு செய்ய, நாம் 23 முதல் 42 ஒப்பிட்டு வேண்டும் - எங்கள் வரிசைப்படுத்தப்பட்ட பகுதியில் மட்டும் உறுப்பு இதுவரை.
நாற்பத்தி இரண்டு 23 விட பெரியதாக உள்ளது, எனவே நாம் வெறுமனே முடிவுக்கு 42 சேர்க்க முடியும்
பட்டியல் வரிசையில் பகுதியை. கிரேட்!
இப்போது எங்கள் வரிசைப்படுத்தப்பட்ட பகுதி இரண்டு கூறுகள் உள்ளன, நமது வரிசையாக்கம் செய்யப்படாத பகுதியை நான்கு உறுப்புகள் உள்ளன.
எனவே, வரிசையாக்கம் செய்யப்படாத பகுதியில் அடுத்த உறுப்பு, இப்போது 4 செல்ல அனுமதிக்க.
எனவே, இந்த வரிசையில் பகுதியில் அமைந்துள்ள வைக்க வேண்டும்?
>> நினைவிருக்கிறதா, நாம் வரிசையில் இந்த எண்ணை வைக்க வேண்டும்
எனவே எங்கள் வரிசைப்படுத்தப்பட்ட பகுதி சரியாக எல்லா நேரங்களிலும் வரிசையில் உள்ளது.
நாங்கள் 42 வலது 4 வைக்க வேண்டும் என்றால், எங்கள் பட்டியலில் பொருட்டு வெளியே இருக்கும்.
எனவே, நமது வகையான பகுதியில் வலது மற்றும் இடது நகரும் தொடர்ந்து நாம்.
நாம் நகர்த்த என, புதிய எண் அறை செய்ய ஒரு இடத்தில் கீழே ஒவ்வொரு எண்ணை மாற்ற வேண்டும்.
சரி, 4 கூட குறைவாக 23, எனவே நாம் இங்கு அதை வைக்க முடியாது.
நாட்டின் 23 சரியான ஒரு இடத்தில் செல்லலாம்.
>> நாம் வரிசைப்படுத்தப்பட்ட பகுதியில் முதல் ஸ்லாட்டில் 4 வைக்க விரும்புகிறேன் என்று.
பட்டியலில் இந்த இடத்தில் ஏற்கனவே காலியாக இருந்தது என்பதை கவனிக்க,
நாம் அவர்களை சந்தித்தோம் நாம் வரிசைப்படுத்தப்பட்ட கூறுகள் கீழே நகரும் ஏனெனில்.
எல்லாம் சரி. எனவே, நாம் பாதி அங்கே இருக்கிறோம்.
இந்த வரிசையில் பகுதி 16 சேர்த்துக்கொள்வதன் மூலம் நமது வழிமுறையை தொடரலாம்.
பதினாறு குறைவாக 42 க்கும், எனவே வலது 42 மாற்றுவதற்கு அனுமதி இல்லை.
பதினாறு குறைவாக 23 க்கும், எனவே அந்த உறுப்பு மாற்ற நாம் உள்ளது.
>> இப்போது, 16 4 அதிகமாக இருக்கும். நாம் 4 மற்றும் 23 இடையே 16 சேர்க்க விரும்புகிறேன் போன்ற, அது தெரிகிறது.
வலமிருந்து பட்டியலை வரிசையாக்கம் பகுதி வழியாக செல்லும் போது,
4 எண்ணிக்கையை விட குறைவு என்று நாம் பார்த்த முதல் எண்
நாம் சேர்க்க முயற்சிக்கும்.
எனவே, இப்போது நாம், இந்த வெற்று ஸ்லாட்டில் 16 சேர்த்துவிடும்
இதில், ஞாபகமிருக்கட்டும், நாம் வகையான பகுதியில் நகரும் உறுப்புகள் விவரங்களை
நாம் அவர்களை சந்தித்தோம் என்று.
>> எல்லாம் சரி. இப்போது, நாங்கள் நான்கு வரிசைப்படுத்தப்பட்ட உறுப்புகள் மற்றும் இரண்டு வரிசையாக்கம் செய்யப்படாத கூறுகள் உள்ளன.
எனவே, இந்த வரிசையில் பகுதியை நோக்கி 8 நகர்த்த வேண்டும்.
எட்டு குறைவாக 42 ஆகும்.
எட்டு குறைவாக 23 ஆகும்.
மற்றும் 8 குறைவாக 16 ஆகும்.
ஆனால் 8 4 அதிகமாக இருக்கும்.
எனவே, நாம் 4 மற்றும் 16 இடையே 8 சேர்க்க விரும்புகிறேன்.
15 - இப்போது நாம் மட்டும் வரிசைப்படுத்த இன்னும் ஒரு உறுப்பு உள்ளது.
பதினைந்து, குறைவான 42 ஆகும்
பதினைந்து குறைவாக 23 ஆகும்.
மற்றும் 15 க்கும் குறைவான 16 ஆகும்.
ஆனால் 15 8 அதிகமாக இருக்கும்.
>> நாம் எமது இறுதி செருகும் செய்ய வேண்டும், அங்கு எனவே, இங்கு தான்.
நாம் முடித்துவிட்டீர்கள்.
நாம், வரிசையாக்கம் செய்யப்படாத பகுதியில் இல்லை கூறுகள்
எங்கள் வரிசைப்படுத்தப்பட்ட பகுதியை சரியான வரிசையில் இல்லை.
எண்கள் சிறிய இருந்து பெரிய உத்தரவிட்டார்.
எனவே, நாம் தான் செய்ய வழிமுறைகளை தெளிவாக குறிப்பிடும் சில சூடோகுறியீடு பாருங்கள் நாம்.
>> வரி 1, நாம் பட்டியலில் ஒவ்வொரு உறுப்பு மீது மீண்டும் கூறு வேண்டும் என்று பார்க்கலாம்
முதல் தவிர, வரிசையாக்கம் செய்யப்படாத பகுதியில் முதல் உறுப்பு இருந்து வெறுமனே மாறும்
வரிசைப்படுத்தப்பட்ட பகுதியில் முதல் உறுப்பு.
கோடுகள் 2 மற்றும் 3 ம் தேதி, நாம் வரிசையாக்கம் செய்யப்படாத பகுதியில் நமது தற்போதைய இடத்தை தடம்.
உறுப்பு, நாம் தற்போது வரிசைப்படுத்தப்பட்ட பகுதியை நோக்கி நகரும் எண்ணை பிரதிநிதித்துவப்படுத்துகிறது
மற்றும் ஜே வரிசையாக்கம் செய்யப்படாத பகுதியை நமது குறியீட்டு பிரதிபலிக்கிறது.
>> வரி 4, நாம் வலமிருந்து வரிசைப்படுத்தப்பட்ட பகுதி வழியே தேடி வருகிறோம்.
நாம் நமது தற்போதைய நிலையில் இடது உறுப்பு ஒருமுறை தேடி நிறுத்த வேண்டும்
நாம் சேர்க்க முயற்சிக்கும் உறுப்பு விட குறைவாக உள்ளது.
வரி 5, நாம் சரியான ஒரு இடத்தில் சந்திக்கும் ஒவ்வொரு உறுப்பு மாற்றம்.
நாம் முதல் உறுப்பு கண்டறிய போது அந்த வழியில், நாங்கள் செருக ஒரு தெளிவான இட வேண்டும்
நாம் நகர்ந்து கொண்டிருக்கிறோம் உறுப்பு குறைவான.
வரி 6, நாம் வரிசைப்படுத்தப்பட்ட பகுதி வழியாக விட்டு செல்ல தொடர எங்கள் எதிர் மேம்படுத்தும்.
இறுதியாக, வரி 7, நாம் பட்டியலை வரிசையாக்கம் பகுதியை நோக்கி உறுப்பு சேர்க்கைக்கு.
>> நாம், அதை நிலை J செருக, பரவாயில்லை என்று
நாம் ஏற்கனவே சரியான அங்கே ஒரு இடைவெளி இருக்க வேண்டும் என்று உறுப்பு சென்றார் ஏனெனில்.
நினைவிருக்கிறதா, நாம், இடது வலது இருந்து வரிசைப்படுத்தப்பட்ட பகுதி வழியாக நகர்ந்து
ஆனால் நாம் இடது இருந்து வலது வரிசையாக்கம் செய்யப்படாத பகுதி வழியாக செல்லும்.
எல்லாம் சரி. இப்போது வழிமுறையை எடுத்து இயங்கும் எவ்வளவு காலம் ஒரு பார்க்கலாம்.
நாம் முதலில் இந்த வழிமுறையை மோசமான இயக்க வேண்டும், அது எவ்வளவு நேரம் எடுக்கும் கேள்வி கேட்கிறேன்.
நாம் பிக் O குறிப்புமுறை இந்த நேரத்தை குறிக்கும் என்று நினைவு.
எங்கள் பட்டியலில் வரிசைப்படுத்த பொருட்டு, நாம், வரிசையாக்கம் செய்யப்படாத பகுதியில் உறுப்புகள் மீது மீண்டும் கூறு வேண்டியிருந்தது
மற்றும் திறன் வரிசைப்படுத்தப்பட்ட பகுதியில் அனைத்து உறுப்புகள் மீது அந்த உறுப்புகள் ஒவ்வொன்றும், ஒரு.
உள்ளுணர்வாக, ஒரு ஓ (n ^ 2) அறுவை சிகிச்சை போல் தெரிகிறது.
>> எங்கள் சூடோகுறியீடு பார்த்து, நாம், மற்றொரு வளைய உள்ளே காக்கப்பட்ட ஒரு வளைய வேண்டும்
இது, உண்மையில், ஒரு ஓ (n ^ 2) அறுவை சிகிச்சை போன்ற உள்ளது.
எனினும், பட்டியல் வரிசையில் பகுதி மிகவும் இறுதி வரை முழு பட்டியலை கொண்டிருக்கும்.
இன்னும், நாம் சாத்தியமான வரிசைப்படுத்தப்பட்ட பகுதி மிகவும் தொடக்கத்தில் ஒரு புதிய உறுப்பு சேர்க்க முடியும்
படிமுறை ஒவ்வொரு மறு செய்கை அன்று,
இதில் நாம் வரிசைப்படுத்தப்பட்ட பகுதியில் தற்போது ஒவ்வொரு உறுப்பு பார்க்க வேண்டும் என்று பொருள்.
எனவே, நாம் சாத்தியமான, இரண்டாவது உறுப்பு ஒரு ஒப்பீடு செய்ய முடியும் என்றால்
மூன்றாவது உறுப்பு இரண்டு ஒப்பீடுகள், மற்றும் பல.
எனவே, படிகள் எண்ணிக்கை 1 முதல் பட்டியல் கழித்து 1 நீளம் முழு கூடுதல் ஆகும்.
நாம் ஒரு கூட்டுத்தொகை இந்த பிரதிநிதித்துவம் முடியும்.
>> நாம் இங்கே கூட்டுத்தொகைகளின் போக மாட்டேன், ஆனால் இந்த கூட்டுத்தொகை சமமாக இருக்கும் என்று மாறும்
n / 2 - சமமான n ^ 2/2 என்பது 2 க்கும், - n (1 n).
எந்த அறிகுறியும் இயக்க பற்றி பேசும் போது,
இந்த n ^ 2 கால இந்த n கால ஆதிக்கம் செலுத்த போகிறது.
எனவே, செருகும் வரிசையாக்கம் பிக் ஓ (n ^ 2) ஆகும்.
நாம் ஏற்கனவே வரிசையாக்கம் பட்டியலில் செருகும் வரிசையாக்கம் ஓடி என்றால்.
அந்த வழக்கில், நாம் சாதாரணமாக விட்டு இருந்து வலது வரிசைப்படுத்தப்பட்ட பகுதியை உருவாக்க விரும்புகிறேன்.
எனவே, நாம் மட்டுமே n நடவடிக்கைகளை வரிசையில் வேண்டும்.
>> என்று, செருகும் வரிசையாக்கம் n ஒரு சிறந்த வழக்கு செயல்திறன் உள்ளது என்று அர்த்தம்
இதில் நாம் Ω (n) மூலம் பிரதிநிதித்துவம்.
என்று, செருகும் வரிசையாக்கம் இது தான்
பல வழிமுறைகளை ஒன்று நாம் ஒரு பட்டியல் வரிசைப்படுத்த பயன்படுத்தலாம்.
என் பெயர் டாமி, மற்றும் இந்த CS50 உள்ளது.
[CS50.TV]
ஓ, நீ ஒரு முறை அதை துவங்கும் நிறுத்த முடியாது.
ஓ, நாம் தான் காரணம் - >> பூம்!