[இசை] டக் LLOYD: சரி, குமிழி வரிசையாக்கம் ஒரு வழிமுறையாகும் நீங்கள் கூறுகளை ஒரு தொகுப்பு வரிசைப்படுத்த பயன்படுத்த முடியும். அது வேலை எப்படி ஒரு பார்க்கலாம். 

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

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

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

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

நாம் அடுத்த அடுத்தடுத்த ஜோடி பாருங்கள், 5 மற்றும் அவர்கள் வரிசையில் போதவில்லை 1 வேண்டும், நாம் அவர்களை மாற்ற மற்றும் சேர்க்க இடமாற்று இடத்திற்கு 1. பின்னர் நாம் 5 மற்றும் 3 பார். அவர்கள் வெளியே ஒழுங்கு, நாம் மாற்ற அவர்களுக்கும் நாம் இடமாற்று எதிர் 1 சேர்க்க. பின்னர் நாம் 5 மற்றும் 6 பார். அவர்கள் வரிசையில் இருக்கும், நாம் உண்மையில் இல்லை எதையும் இந்த நேரத்தில் இடமாற்றம் செய்ய வேண்டும். பின்னர் நாம் 6 மற்றும் 4 பாருங்கள். அவர்கள் பொருட்டு வெளியே தான் இருக்கிறோம், நாம் மாற்ற அவர்களுக்கும் நாம் இடமாற்று எதிர் 1 சேர்க்க. 

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

எனவே நாம் இப்போது அறிவிக்க முடியும் என்று வரிசைப்படுத்தப்பட்ட என்று, எதிர்காலத்தில் iterations-- வரிசை நடக்கிறது மீண்டும் நாம் இனி 6 கருத்தில் கொள்ள வேண்டும். நாம் மட்டும் கருத்தில் கொள்ள வேண்டும் வரிசையாக்கம் செய்யப்படாத கூறுகள் போது நாம் அடுத்தடுத்த ஜோடிகள் தேடும். எனவே நாம் ஒரு முடித்தேன் குமிழி வரிசையாக்கம் வழியாக. எனவே இப்போது நாம் கேள்வி செல்ல, இடமாற்று கவுண்டர் 0 வரை மீண்டும். சரி இடமாற்று எதிர் 4 எனவே, நாங்கள் போகிறோம் மீண்டும் இந்த செயற்பாட்டை மீண்டும் வைக்க. 

நாம் இடமாற்று வகையில் மாற்றுவது போகிறோம் 0, மற்றும் ஒவ்வொரு அடுத்தடுத்த ஜோடி பாருங்கள். எனவே நாம் அவர்கள் 1 வேண்டும் 2 தொடங்க மற்றும் வெளியே ஒழுங்கு, நாம் அவர்களை மாற்ற மற்றும் நாம் இடமாற்று எதிர் 1 சேர்க்க. 2 மற்றும் 3, அவர்கள் விதமாக இருக்கும். அங்கே என்ன செய்ய வேண்டும் தேவையில்லை. 3 மற்றும் 5 வரிசையில் உள்ளன. நாம் அங்கு எதுவும் செய்ய தேவையில்லை. 

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

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

எனவே நாம் ஒரு பாஸ் நிறைவு. இடமாற்று எதிர் 2. எனவே நாம் மீண்டும் செல்கிறோம் மீண்டும் இந்த செயற்பாட்டை, இடமாற்று கவுண்டர் 0 வரை மீண்டும். 0 இடமாற்று எதிர் மீட்டமை. எனவே நாம் அதை மீட்டமைக்க வேண்டும். 

இப்போது ஒவ்வொரு அடுத்தடுத்த ஜோடி பாருங்கள். என்று, பொருட்டு 1 மற்றும் 2 தான். 2 மற்றும் 3 வரிசையில் உள்ளன. 3 மற்றும் 4 வரிசையில் உள்ளன. எனவே இந்த கட்டத்தில், நாம் முடித்துவிட்டேன் கவனிக்க ஒவ்வொரு அடுத்தடுத்த ஜோடி பார்த்து, ஆனால் இடமாற்று எதிர் இன்னும் 0 தான். 

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

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

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

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

நான் டக் லாயிட் இருக்கிறேன். இந்த CS50 உள்ளது.