[Powered by Google Translate] [குமிழி வரிசையாக்கம்] [JACKSON STEINKAMP ஹார்வர்ட் பல்கலைக்கழகம்] [இந்த CS50 உள்ளது. CS50TV] குமிழி வரிசை வரிசையாக்க படிமுறையின் ஒரு உதாரணம் - என்று, உறுப்புகள் தொகுப்பில் வரிசையாக்கம் ஒரு செயல்முறை ஏறுவரிசை அல்லது இறங்கு. நீங்கள் ஒரு வரிசையில் அடுக்க வேண்டும் என்றால் உதாரணமாக, எண்கள் கொண்ட [3, 5, 2, 9], குமிழ் வரிசை ஒரு சரியான செயல்படுத்த மீண்டும் வரிசைப்படுத்தப்பட்ட வரிசை [2, 3, 5, 9] ஏறுவரிசையில் உள்ள. இப்போது, நான் வழிமுறையை எவ்வாறு சூடோகுறியீடு உள்ள விளக்க போகிறேன். 

3, 2, 9, 6, மற்றும் 5 - நாம் 5 முழு பட்டியலை வரிசையாக்கம் சொல்கிறீர்கள். வழிமுறை, முதல் இரண்டு கூறுகள், 3 மற்றும் 2 பார்ப்பதன் மூலம் தொடங்குகிறது அவர்கள் ஒருவருக்கொருவர் வரிசையை விட்டு என்றால் சரி. அவர்கள் - 3 2 அதிகமாக இருக்கும். ஏறு வரிசையில் இருக்க, அவர்கள் வேறு இருக்க வேண்டும். எனவே, நாம் அவர்களை இடமாற்றம். [2, 3, 9, 6, 5]: இப்போது பட்டியலில் இந்த தெரிகிறது. 

அடுத்து, நாம் இரண்டாவது மற்றும் மூன்றாவது கூறுகள், 3 மற்றும் 9 பாருங்கள். அவர்கள் ஒருவருக்கொருவர் உறவினர் சரியான வரிசையில் இல்லை. படிமுறை அவர்களை இடமாற்றம் இல்லை 9 விட குறைவான என்று, 3. அடுத்து, நாங்கள் 9 மற்றும் 6 பாருங்கள். அவர்கள் வரிசையில் போதவில்லை. 

எனவே, நாம் 9 6 அதிகமாக இருப்பதால் அவற்றை மாற்ற வேண்டும். இறுதியாக, நாம் கடந்த இரண்டு முழு எண்கள், 9 மற்றும் 5 பாருங்கள். அவர்கள் வரிசையில் போதவில்லை, எனவே அவர்கள் பண்டமாற்று வேண்டும். பட்டியல் மூலம் முதல் முழு பாஸ் பின்னர், [2, 3, 6, 5, 9]: இந்த மாதிரி. மோசம் இல்லை. இது கிட்டத்தட்ட வரிசைப்படுத்தப்பட்ட. ஆனால் நாங்கள் அதை முற்றிலும் வரிசைப்படுத்தப்பட்ட பெற மீண்டும் பட்டியல் மூலம் இயக்க வேண்டும். இரண்டு 3 குறைவாக உள்ளது, எனவே நாம் அவர்களை இடமாற்றம் இல்லை. 

மூன்று 6 குறைவாக உள்ளது, எனவே நாம் அவர்களை இடமாற்றம் இல்லை. ஆறு 5 விட பெரியது. நாம் மாற்றப்பட்டது. ஆறு 9 குறைவாக உள்ளது. நாம் இடமாற்றம் இல்லை. மூலம் இரண்டாவது பாஸ் பின்னர், இந்த மாதிரி: [2, 3, 5, 6, 9]. ஆனால். இப்போது, அது சூடோகுறியீடு எழுத நாம். அடிப்படையில், பட்டியலில் ஒவ்வொரு உறுப்பு நாம் அதை பார்க்க வேண்டும் மற்றும் நேரடியாக அதன் வலது உறுப்பு. அவர்கள் வரிசையில் ஒவ்வொரு பிற தொடர்புடைய அவுட் என்றால் - அந்த, என்றால் இடது உறுப்பு வலது ஒன்றை விட அதிகமாக இருக்கும் - நாம் இரண்டு கூறுகள் இடமாற்றம் வேண்டும். 

நாம் பட்டியலை ஒவ்வொரு உறுப்பு செய்ய, மற்றும் நாம் ஒரு பாஸ் செய்துவிட்டேன். இப்போது நாம் ஒரு பட்டியல் உறுதி கடந்து செல்லும் போதும் முறை செய்ய வேண்டும் முழுமையாக, சரியாக பிரிக்கப்பட்டுள்ளது. ஆனால் நாம் பட்டியலை வழியாக எப்படி பல முறை இல்லை நாம் என்ன என்று உத்தரவாதம்? நாம் முற்றிலும் பின்னோக்கி பட்டியலில் இருந்தால் நன்றாக, மிக மோசமான சூழ்நிலையில் உள்ளது. அது பல சமமாக கடந்து throughs பல எடுக்கிறது உறுப்புகள் n-1. இந்த உள்ளுணர்வாக பயன் இல்லை என்றால், ஒரு எளிய வழக்கு என்று - பட்டியல் [2, 1]. 

இந்த சரியாக வரிசைப்படுத்த ஒரு கடந்து செல்லும் நடக்கப்போகிறது. [3, 2, 1] - மோசமான, 3 கூறுகளை கொண்டு பின்னோக்கி வரிசைப்படுத்தப்பட்ட என்று இது மாதிரி 2 மீண்டும் எடுத்து நடக்கிறது. ஒரு மறு செய்கை பின்னர், அது [, 3 1 2] தான். இரண்டாவது விளைச்சல் வரிசைப்படுத்தப்பட்ட வரிசை [1, 2, 3]. எனவே, நீங்கள் பொதுவாக, வரிசையின் வழியாக செல்ல வேண்டும் தெரியும் n அணியின் உறுப்புகள் எண்ணிக்கை n-1 ​​முறை, அதிக. பெரிய சக்திகள் 'மேல்தோன்றும்' ஏனெனில், அது குமிழ் வரிசை என்று அழகான விரைவில் வலது. உண்மையில், இந்த வழிமுறை மிகவும் சுவாரசியமான நடத்தை உள்ளது. 

முழு வரிசையில் மூலம் மீ மீண்டும் பிறகு, rightmost மீ கூறுகள் உத்தரவாதம் அவர்கள் சரியான இடத்தில் வரிசைப்படுத்தப்பட்ட வேண்டும். நீங்கள், உங்களை இந்த பார்க்க விரும்பினால் நாம் முற்றிலும் பின்னோக்கி பட்டியல் [9, 6, 5, 3, 2] அதை முயற்சி செய்யலாம். முழு பட்டியல் மூலம் ஒரு பாஸ் பின்னர், [எழுத்து ஒலி] [6, 9, 5, 3, 2], [6, 5, 9, 3, 2], [6, 5, 3, 9, 2], [6, 5, 3, 2, 9] rightmost உறுப்பு 9 அதன் சரியான இடத்தில் உள்ளது. கடந்து செல்லும் இரண்டாவது பிறகு, 6 ​​'குதுகலித்தது அப்' வேண்டும் இரண்டாவது rightmost இடத்தில். 6 மற்றும் 9 - - வலது இரண்டு கூறுகள் அவற்றின் சரியான இடங்களில் இருக்கும் முதல் இரண்டு பாஸ்-throughs பிறகு. 

எனவே, நாங்கள் எப்படி வழிமுறை மேம்படுத்த இந்த பயன்படுத்த முடியும்? நன்றாக, வரிசை மூலம் ஒரு மறு செய்கை பிறகு நாம் உண்மையில் rightmost உறுப்பு பார்க்க தேவையில்லை எங்களுக்கு தெரியும், ஏனெனில் அது வரிசைப்படுத்தப்பட்ட. இரண்டு மீண்டும் பிறகு, நாம் rightmost இரண்டு கூறுகள் இடத்தில் இருக்கும் நிச்சயம் தெரியும். எனவே, பொதுவாக, முழு வரிசை மூலம், k மீண்டும் பிறகு, எங்களுக்கு தெரியும் என்பதால், கடந்த கே கூறுகள் சோதனை பணிநீக்கம் உள்ளது அவர்கள் ஏற்கனவே சரியான இடத்தில் இருக்கிறது. 

நீங்கள் n உறுப்புகள் ஒரு வரிசை வரிசையாக்க நீங்கள் இவ்வளவு என்றால், முதல் மறு செய்கை மீது - you'll கூறுகள் அனைத்து வரிசைப்படுத்த வேண்டும் - முதல் n-0. இரண்டாவது மறு செய்கை, நீங்கள் கூறுகள் அனைத்து ஆனால் கடந்த பார்க்க வேண்டும் - n-1 முதல். மற்றொரு ஆப்டிமைசேஷன் பட்டியல் ஏற்கனவே வரிசையாக்கம் என்று பரிசோதிக்க வேண்டும் ஒவ்வொரு மறுசெய்கையும் பிறகு. ஏற்கனவே வரிசையாக்கம் இருந்தால், நாம் எந்த மீண்டும் செய்ய தேவையில்லை பட்டியல் மூலம். எப்படி இதை செய்ய முடியும்? சரி, நாம் ஒரு பட்டியல் கடந்து செல்லும் எந்த பரிமாற்றங்கள் செய்ய வில்லை என்றால், நாம் எதையும் மாற்ற முடியாது, ஏனெனில் பட்டியல் ஏற்கனவே வரிசையாக்கம் என்று தெளிவாக இருக்கிறது. எனவே நாம் நிச்சயமாக மீண்டும் வரிசைப்படுத்த இல்லை. 

ஒருவேளை நீங்கள் 'சரியாகவில்லை' என்று ஒரு கொடி மாறி துவக்க முடியும் நீங்கள் எந்த கூறுகளை மாற்ற வேண்டும் என்றால், தவறான மற்றும் உண்மை அதை மாற்ற வரிசை மூலம் ஒரு மறு செய்கை. அல்லது இதேபோல், நீங்கள் எத்தனை பரிமாற்றங்கள் எண்ணுவதற்கு எதிர்ப்பு செய்ய எந்த மறு செய்கை அன்று. ஒரு மறு செய்கை இறுதியில், நீங்கள் உறுப்புகள் எந்த இடமாற்றம் செய்யவில்லை என்றால், நீங்கள் பட்டியல் ஏற்கனவே வரிசையாக்கம் மற்றும் நீங்கள் முடித்துவிட்டீர்கள் தெரியும். குமிழி வரிசை, மற்ற வரிசையாக்க படிமுறைகள் போல், இருக்க முடியும் ஒரு வரிசைப்படுத்தும் முறையை கொண்ட எந்த உறுப்புகள் வேலை மாற்றி அமைக்கப்படும். 

என்று நீங்கள் சொல்ல ஒரு வழி இரண்டு கூறுகள் கொடுக்கப்பட்ட, என்று முதல் ஒரு சமமாக அல்லது இரண்டாவது விட குறைவாக, அதிகமாக உள்ளது. உதாரணமாக, நீங்கள் சொல்லி எழுத்துக்கள் கடிதங்களை வரிசைப்படுத்த முடியும் ஒரு <ப, ப <கேட்ச், பல என்று ஞாயிறு திங்கள் குறைவாக இருக்கும் அல்லது நீங்கள் வார நாட்களில் வரிசைப்படுத்த முடியும் இது செவ்வாயன்று விட குறைவாக உள்ளது. 

எந்த ஒரு மிக திறமையான அல்லது வேகமாக வரிசையாக்க படிமுறை என்பது மூலம் குமிழி வரிசை ஆகும். அதன் மோசமான இயக்க n, பிக் ஓ இது ² நீங்கள் ஒரு பட்டியல் மூலம் n மீண்டும் செய்ய வேண்டும், ஏனெனில் ஒவ்வொரு கடந்து செல்லும் அனைத்து n உறுப்புகள் சோதனை, nxn = n ². இந்த இயக்க நேரம் கூறுகள் எண்ணிக்கை நீங்கள், அதிகரிக்கும் வரிசையாக்க என்று அர்த்தம் ரன் நேரம் இருபடி அதிகரிக்கிறது. 

ஆனால் திறன் உங்கள் திட்டத்தின் ஒரு முக்கிய கவலை இல்லை என்றால் அல்லது நீங்கள் மட்டுமே கூறுகள் ஒரு சிறிய எண்ணிக்கையிலான வரிசையாக்க என்றால், நீங்கள் குமிழி வரிசையாக்கம் பயனுள்ளதாக இருக்கும், ஏனெனில் அதை புரிந்து கொள்ள எளிய வரிசையாக்க படிமுறைகளில் ஒன்றாக மற்றும் குறியீடு வேண்டும். இது ஒரு கோட்பாட்டு மொழிபெயர்ப்பது அனுபவம் பெற ஒரு வழி உண்மையான செயல்பாட்டை குறியீடு மாற்றும் வழிமுறை. அந்த நீ குமிழ் வரிசை தான். பார்த்து நன்றி. CS50.TV