[இசை] டக் LLOYD: சரி, ஒரு பிணைப்பு வகையான மற்றொரு வழிமுறை நாங்கள் தீர்த்துக்கொள்ள பயன்படுத்த முடியும் என்று ஒரு வரிசைக்கு கூறுகள். நாம் பார்க்க வேண்டும் என ஆனால், அது கிடைத்து விட்டது ஒரு மிகவும் அடிப்படை வேறுபாடு தேர்வு மாதிரி, குமிழி இருந்து வகையான, மற்றும் செருகும் வரிசையாக்கம் அது உண்மையில் அழகான கெட்டிக்காரத்தனம் செய்ய. ஒன்றிணைப்பு பின்னால் அடிப்படை கருத்து வகையான சிறிய அணிகளை வரிசைப்படுத்த உள்ளது பின்னர் அந்த வரிசைகள் இணைக்க ஒன்றாக, அல்லது them-- ஒன்றாக்க எனவே வரிசையில் பெயர். வகையான இல்லை ஒன்றாக்க என்று வழி இந்த ஒரு கருவி செயல் மூலம் ஆகிறது என்ன இது, மறுநிகழ்வு என்றழைக்கப்படும் நாங்கள், விரைவில் பற்றி பேசி இருக்க போகிறோம் ஆனால் நாம் உண்மையில் இன்னும் பற்றி பேசவே இல்லை. இங்கே ஒன்றிணைப்பு வகையான பின்னால் அடிப்படை யோசனை. வரிசை, இடது பாதி பிரியுங்கள் N அனுமானித்து 1 விட அதிகமாக உள்ளது. நான் சொல்லும் போது என்ன அர்த்தம் N அனுமானித்து, 1 விட அதிகமாக உள்ளது நான் நாம் ஏற்று கொள்ள முடியும் என்று என்று ஒரு வரிசை என்றால் ஒரே ஒரு உறுப்பு கொண்டுள்ளது, இது வரிசைப்படுத்தப்பட்ட. நாம் உண்மையில் தேவையில்லை அது ஏதாவது செய்ய. நாம் அதை வகைப்படுத்த அறிவிக்க முடியும். இது ஒரு ஒற்றை உறுப்பு தான். எனவே சூடோகுறியீடு, மீண்டும், வரிசை, இடது பாதி வரிசைப்படுத்துவது பின்னர் வலது பாதி வரிசை வரிசைப்படுத்த, பின்னர் ஒன்றாக இரண்டு பகுதிகளாக ஒன்றாக்க. இப்போது, ஏற்கனவே நீங்கள் இருக்க வேண்டும் நினைத்து, அது என்ன தான் the-- நீங்கள் அமுத்துவதை போல் தெரிகிறது நீங்கள் உண்மையில் எதையும் செய்யவில்லை. நீங்கள் இடது வரிசைப்படுத்த சொல்கிறீர்கள் பாதி, சரி பாதி வரிசைப்படுத்த, ஆனால் நீங்கள் சொல்ல வில்லை என்னை எப்படி நீங்கள் அதை செய்கிறீர்கள். ஆனால் நீண்ட என்று நினைவில் ஒரு வரிசை ஒரு ஒற்றை உறுப்பு ஆகும், நாம் அது வரிசைப்படுத்தப்பட்ட அறிவிக்க முடியும். நாம் என்ன தான் அவற்றை ஒன்றாக இணைக்க முடியும். மற்றும் அந்த உண்மையில் தான் ஒன்றிணைப்பு வகையான பின்னால் அடிப்படை யோசனை, என்று அது உடைந்து உள்ளது உங்கள் வரிசைகள் அளவு ஒரு உள்ளன. பிறகு அங்கு இருந்து மீண்டும். வகையான நிச்சயமாக ஒன்றாக்க ஒரு சிக்கலான படிமுறை. மேலும் அது ஒரு சிறிய விஷயம் காட்சிப்படுத்தியது சிக்கலான. எனவே வட்டம், காட்சிப்படுத்தல் என்று நான் நீங்கள் சேர்த்து பின்பற்ற உதவும் இங்கே இல்லை. நான் விஷயங்களை சொல்லவா நான் முயற்சி செய்கிறேன் மற்றும் இந்த ஒரு சிறிய இன்னும் மூலம் தொடர மெதுவாக மற்ற ஒன்றை விட வெறும் வட்டம் உங்கள் தலையில் பெற ஒன்றிணைப்பு வகையான பின்னால் கருத்துக்கள் சுற்றி. எனவே நாம் அதே வரிசை வேண்டும் மற்ற வரிசையாக்க படிமுறை வீடியோக்கள் நீங்கள் பார்த்த என்றால் them-- ஒரு ஆறு உறுப்பு வரிசை. மற்றும் இங்கே நம் சூடோகுறியீடு குறியீடு வகையான ஆகிறது இடது பாதி, சரி பாதி வரிசைப்படுத்த, ஒன்றாக இரண்டு பகுதிகளாக ஒன்றாக்க. எனவே இந்த மிகவும் இருண்ட செங்கல் நிறம் எடுத்து விடுங்கள் வரிசை மற்றும் அதை விட்டு பாதி வரிசைப்படுத்த. தற்போதைக்கு எனவே, நாம் போகிறோம் வலது பொருட்களை புறக்கணிக்க. அது தான், ஆனால் நாம் இருக்கிறோம் இன்னும் என்று படியிலும். நாம் இருக்கிறோம் இல்லை உள்ள மாதிரி வரிசை வலது பாதி. நாம் அப்படி இடது இருக்கிறோம் வரிசை பாதி. வெறும் ஆணையாக இன்னும் கொஞ்சம் இருப்பது தெளிவான, அதனால் நான் பார்க்கவும் முடியும் என்ன படி நாம் இருக்கிறோம், நான் மாற போகிறேன் ஆரஞ்சு இந்த தொகுப்பு நிறம். இப்போது, நாம் இன்னும் பற்றி பேசுகிறீர்கள் அசல் வரிசை அதே இடது பாதி. ஆனால் நான் முடியும் மூலம் என்று நம்பிக்கையுடன் இருக்கிறேன் பல்வேறு பொருட்களை நிறங்கள் பார்க்கவும் அது ஒரு சிறிய மேலும் செய்ய வேண்டும் இங்கே என்ன நடக்கிறது அழிக்க. சரி, இப்போது நாம் ஒரு மூன்று உறுப்பு வரிசை. நாம் இந்த இடது பாதி வரிசைப்படுத்துவது எப்படி இன்னும் இந்த படி இது வரிசை,? நாம் இடது வரிசைப்படுத்த முயற்சி செங்கல் நிறம் வரிசையில் பாதி இடது பாதி நான் இப்போது ஆரஞ்சு நிற. சரி, நாம் முயற்சி செய்ய முடியும் மீண்டும் இந்த செயல்முறை மீண்டும். எனவே நாம் இன்னும் இருக்கிறோம் வரிசைப்படுத்த முயற்சி மத்தியில் முழு வரிசை இடது பாதி. இடது பாதி வரிசை, நான் போகிறேன் தன்னிச்சையாக முடிவெடுக்க இடது பாதி வலது பாதி காட்டிலும் சிறியதாக இருக்கும், இந்த நடக்கிறது என்பதால் மூன்று கூறுகளைக் கொண்டுள்ளன. அதனால் நான் அந்த சொல்ல போகிறேன் இடது பாதி வரிசை இடது பாதி வெறும் உறுப்பு ஐந்து ஆகிறது. ஐந்து, ஒரு ஒற்றை உறுப்பு இருப்பது வரிசை, நாம் அது வரிசைப்படுத்த எப்படி தெரியும். அதனால் ஐந்து பிரிக்கப்பட்டுள்ளது. நாம் தான் அதை அறிவிக்க போகிறீர்கள். அது ஒரு உறுப்பு வரிசை தான். நாம் இப்போது வகைப்படுத்த இடது half-- இடது பாதி அல்லது மாறாக, நாங்கள் வகைப்படுத்த ஆரஞ்சு இடது பாதி. எனவே இப்போது, வரிசையில் இன்னும் முழுமையான ஒட்டுமொத்த அணியின் இடது பாதி, நாம் சரியான அரை வரிசைப்படுத்த வேண்டும் ஆரஞ்சு, அல்லது இந்த பொருள். நாம் எப்படி செய்ய வேண்டும்? சரி, நாம் ஒரு இரண்டு உறுப்பு வரிசை வேண்டும். எனவே நாம் இடது பாதி தீர்த்துக்கொள்ள முடியாது இரண்டு வரிசைக்கு. இரண்டு ஒரு ஒற்றை உறுப்பு ஆகும். எனவே அதை இயல்பாக பேசி தீர்க்கப்படும். நாம் சரியான அரை வரிசைப்படுத்த முடியும் வரிசை, ஒரு அந்த பகுதியை முழுவதுமாக. என்று இயல்பாக வகையான தான். இந்த இப்போது முதல் முறை நாம் ஒரு ஒன்றிணைப்பு படி அடைந்தது. நாம் என்றாலும், நிறைவு நாம் இப்போது வகையான down-- காக்கப்பட்ட மற்றும் அந்த தந்திரமான வகையான தான் மறுநிகழ்வு விஷயம், நீங்கள் உங்கள் வைக்க வேண்டும் நாம் எங்கே பற்றி தலைமை. நாம் இடது வகையான போயிருக்கிறோம் ஆரஞ்சு பகுதியை பாதிக்கும். இப்போது, நாம் வரிசையாக்க மத்தியில் இருக்கிறோம் ஆரஞ்சு பகுதியை வலது பாதி. மற்றும் அந்த பணியில், நாம் படி இருக்க இப்போது சுமார், ஒன்றாக இரண்டு பகுதிகளாக ஒன்றாக்க. நாங்கள் இரண்டு பகுதிகளாக இருக்கும் போது வரிசை, நாம் இரண்டு மற்றும் ஒரு பார்க்கிறோம். எந்த உறுப்பு சிறியதாக இருக்கும்? ஒன்று. பின்னர் எந்த உறுப்பு சிறியதாக இருக்கும்? சரி, அது இரண்டு அல்லது எதுவும் இல்லை. அதனால், இரண்டு தான். எனவே இப்போது, மீண்டும் சிருஷ்டிக்க நாம் சூழலில் எங்கே, நாம் வரிசைப்படுத்தப்பட்ட வேண்டும் ஆரஞ்சு இடது பாதி மற்றும் தோற்றம் வலது பாதி. நான் நிறங்கள் மாற்றம் தெரியும் நாம் எங்கே மீண்டும், ஆனால் தான். காரணம் நான் இந்த செய்தது இந்த செயல்முறை ஏனெனில் ஆகிறது கீழே தேடி, போகும் போகிறது. நாம் இடது வரிசைப்படுத்தப்பட்ட முன்னாள் ஆரஞ்சு பாதி முன்னாள் ஆரஞ்சு வலது பாதி. இப்போது, நாம் அந்த ஒன்றிணைக்க வேண்டும் ஒன்று மிகவும் இரண்டு பகுதிகளாக. என்று நாம் இருக்கிறோம் படி தான். எனவே நாம் அனைத்து கருத்தில் இப்போது பச்சை என்று கூறுகளை, அசல் வரிசை இடது பாதி. நாம் அந்த ஒன்றிணைக்க அதே செயல்முறை பயன்படுத்தி நாம் இரண்டு இணைத்தல் செய்தது மற்றும் ஒரு ஒரு நிமிடம் முன்பு. இடது பாதி, சிறிய இடது பாதி மீது உறுப்பு ஐந்து ஆகிறது. சிறிய உறுப்பு வலது பாதி ஒன்றாகும். அந்த எந்த சிறியதாக இருக்கும்? ஒன்று. சிறிய உறுப்பு இடது பாதி ஐந்து ஆகிறது. சிறிய உறுப்பு வலது பாதி இரண்டு. சிறிய என்ன? இரண்டு. பின்னர் இறுதியாக, ஐந்து மற்றும் எதுவும், நாங்கள் ஐந்து சொல்ல முடியும். சரி, அதனால் பெரிய படம், நாம் இரண்டாவது ஒரு இடைவெளி எடுத்து நாம் எங்கே கண்டுபிடிக்க. நாம் இருந்து தொடங்கியது என்றால் ஆரம்பத்தில், நாம் இப்போது நிறைவு ஒட்டுமொத்த வரிசை தான் இங்கே சூடோகுறியீடு குறியீடு ஒரு படி. நாம் பேசி தீர்க்கப்படும் என்று வரிசை இடது பாதி. அசல் என்று நினைவு ஆர்டர் ஐந்து, இரண்டு, ஒன்று இருந்தது. இந்த செயல்முறை மூலம் செல்வதன் மூலம் கீழே காணப்படுகிறது மற்றும் மீண்டும், பிரச்சனை உடைக்க தொடர்ந்து கீழே சிறிய மற்றும் சிறிய பகுதிகளாக, நாம் இப்போது நிறைவு சூடோகுறியீடு ஒரு படி முழு தொடக்க வரிசை. நாம் அதன் இடது பாதி பேசி தீர்க்கப்படும் என்று. எனவே இப்போது அங்கு நிறுத்தப்படலாம் அனுமதிக்க. இப்போது வலது அடுக்க வேண்டும் அசல் வரிசை பாதி. நாம் அந்த செய்ய போகிறோம் அதே பங்கேற்பு வழியாக சென்று விஷயங்களை உடைத்தல் செயல்முறை பின்னர் அவற்றை ஒன்றாக இணைக்கப்படும். எனவே இடது பாதி சிவப்பு, அல்லது இடது பாதி அசல் வலது பாதி வரிசை, நான் சொல்ல போகிறேன் மூன்று ஆகிறது. மீண்டும், நான் இங்கே சீரான இருப்பது. நீங்கள் ஒரு ஒற்றைப்படை இருந்தால் கூறுகள் எண்ணிக்கை, அது உண்மையில் என்பதை தேவையில்லை நீங்கள் இடது ஒன்று சிறிய செய்ய அல்லது சரியான ஒரு சிறிய. என்ன விஷயம் இருக்கிறது போதெல்லாம் நீங்கள் என்று நடத்தி உள்ள இந்த சிக்கல் ஏற்பட்டால் ஒரு பிணைப்பு நீங்கள் தொடர்ந்து இருக்க வேண்டும். நீங்கள் எப்போதும் வேண்டும் ஒரு இடது பக்க சிறிய செய்ய அல்லது எப்போதும் செய்ய வேண்டும் வலது பக்க சிறிய. இங்கே, நான் எப்போதும் தேர்வு இடது பக்க சிறிய செய்ய போது என் வரிசை, அல்லது என் துணை வரிசை, ஒரு புதுமையான அளவு உள்ளது. மூன்று ஒரு ஒற்றை உறுப்பு ஆகும், மற்றும் அது பிரிக்கப்பட்டுள்ளது. நாம் என்று அனுமானம் செயல்திறனற்ற எங்கள் முழு செயல்முறை முழுவதும் இதுவரை. எனவே இப்போது வலது அடுக்க வேண்டும் வலது பாதி பாதி, அல்லது சிவப்பு வலது பாதி. மீண்டும், நாம் இந்த கீழே பிரிக்க வேண்டும். இந்த ஒரு உறுப்பு வரிசை அல்ல. நாம் அது வரிசைப்படுத்தப்பட்ட அறிவிக்க முடியாது. அதனால், முதலில் நாம் போகிறோம் இடது பாதி வரிசைப்படுத்த. இடது பாதி ஒரு ஒற்றை உறுப்பு ஆகும், அது இயல்பாக வகையான தான். நாம் சரியான தீர்த்துக்கொள்ள போகிறது ஒரு உறுப்பு இருக்கும் அரை. அது இயல்பாக பேசி தீர்க்கப்படும். இப்போது, நாங்கள் ஒன்றாக அந்த இரண்டு ஒன்றாக்க முடியும். நான்கு சிறியதாக இருக்கும், மற்றும் பின்னர் ஆறு சிறியதாக இருக்கும். இந்த விஷயத்திலும், நாம் இந்த கட்டத்தில் என்ன செய்தேன்? நாம் இடது வரிசைப்படுத்தப்பட்ட வலது பாதி பாதி. அல்லது அசல் மீண்டும் சென்று இருந்தன என்று வண்ணங்கள், நாம் இடது வரிசைப்படுத்தப்பட்ட மென்மையான சிவப்பு பாதி. அது உண்மையில் ஒரு இருண்ட செங்கல் இருந்தது சிவப்பு, இப்போது அதை ஒரு மென்மையான சிவப்பு தான், அல்லது அது ஒரு மென்மையான சிவப்பு இருந்தது. பின்னர் நாம் வகைப்படுத்த மென்மையான சிவப்பு வலது பாதி. இப்போது, நன்றாக, அவர்கள் தான், மீண்டும் பச்சை இருக்கிறார்கள் நாம் ஒரு செயல்முறை மூலம் போகிறோம் என்பதால். நாம் மீண்டும் வேண்டும் இந்த மேல். எனவே இப்போது நாம் அந்த ஒன்றிணைக்க முடியும் ஒன்றாக இரண்டு பகுதிகளாக. என்று நாம் இங்கே என்ன இருக்கிறது. கருப்பு கோடு அதனால் தான் இடது பாதி வகுத்தது மற்றும் இந்த வகையான பகுதியாக வலது பாதி. நாம் சிறிய மதிப்பை ஒப்பிடுவதற்கு வரிசை இடது பக்கத்தில் அல்லது, என்னை மன்னித்துவிடுங்கள், சிறிய இடது பாதி மதிப்பு வலது மிகச்சிறிய மதிப்பு அரை மற்றும் மூன்று சிறிய என்று கண்டறிய. இப்போது ஒரு தேர்வுமுறை ஒரு பிட், சரியான? எதுவும் உண்மையில் இல்லை இடது பக்கத்தில் விட்டு. மீதமுள்ள எதுவும் இல்லை இடது பக்கத்தில், அதனால் நாம் திறமையாக முடியும் தான் நாம் அறிவிக்க முடியும் move-- அது மற்ற உண்மையில் ஆகிறது வரிசைப்படுத்தப்பட்ட மற்றும் அதை பிசுப்பு எதுவும் இல்லை, ஏனெனில், மீது எதிராக ஒப்பிட்டு வேறு. மற்றும் நாம் தெரியுமா வலது பக்க என்று வலது பக்க பிரிக்கப்பட்டுள்ளது. சரி, இப்போது மீண்டும் நிறுத்தப்படலாம் அனுமதிக்க மற்றும் நாம் கதை எங்கு கண்டுபிடிக்க. ஒட்டுமொத்த வரிசையில், நாங்கள் என்ன நிறைவேற்றப்படுகிறது? நாம் உண்மையில் சாதிக்கிறோம் இப்போது ஒரு படி இரண்டு படிகள். நாம் இடது பாதி வரிசைப்படுத்தப்பட்ட, மற்றும் நாம் சரியான அரை வரிசைப்படுத்தப்பட்ட. எனவே இப்போது, எஞ்சியிருப்பதை எங்களுக்கு உள்ளது ஒன்றாக அந்த இரண்டு பகுதிகளாக ஒன்றாக்க வேண்டும். எனவே நாம் மிக குறைந்த மதிப்பு ஒப்பிட்டு அணியின் ஒவ்வொரு அரை உறுப்பு இதையொட்டி தொடர. ஒன்று, இந்த மூன்று விட குறைவாக உள்ளது, எனவே ஒரு செல்கிறது. இரண்டு, மூன்று விட குறைவாக உள்ளது, எனவே இரண்டு செல்கிறது. மூன்று 5 விட குறைவாக உள்ளது, அதனால் மூன்று செல்கிறது. நான்கு 5 விட குறைவாக உள்ளது, அதனால் நான்கு செல்கிறது. பின்னர் ஐந்து, ஆறு விட குறைவாக உள்ளது ஆறு என்று இருந்து வருகிறது. இப்போது, எனக்கு தெரியும், என்று வழிமுறைகளை நிறைய இருந்தது. நாம் நிறைய விட்டு எங்கள் அடுத்து நினைவகம். மற்றும் அந்த சாம்பல் சதுரங்கள் என்ன. என்று ஒரு எடுத்து போன்ற அது ஒருவேளை உணர்ந்தேன் செருகும் வரிசையாக்கம் விட நீண்ட நிறைய, குமிழ் வகையான, அல்லது தேர்வு வகையான. ஆனால் உண்மையில், ஏனெனில் ஒரு இந்த நடவடிக்கைகளின் நிறைய அதே நேர நடக்கிறது இது, மீண்டும், நாம் தருகிறேன் ஒன்று உள்ளது நாம் பற்றி பேச போது பற்றி பேச ஒரு எதிர்கால மறுநிகழ்வு video-- உண்மையில் இந்த வழிமுறை தெளிவாக அடிப்படையில் எதையும் விட வேறு நாம் முன்னர் பார்த்த ஆனால் கணிசமாக உள்ளது திறமையான. அது ஏன்? நன்றாக, மிக மோசமான உள்ள வழக்கு சூழ்நிலையில், நாம் n உறுப்புகள் பிரித்து பின்னர் அவர்கள் மீண்டும் சேர்கின்றன. ஆனால் நாம் மீண்டும் இணையும் போது அவர்களுக்கு, நாம் என்ன செய்கிறோம் அடிப்படையில் இரட்டிப்பாக்க சிறிய அணிகளை அளவு. நாம் ஒரு உறுப்பு ஒரு கொத்து வேண்டும் வரிசைகள் என்று நாம் திறம்பட இரண்டு உறுப்பு அணிகளை இணைக்க. பின்னர் நாம் அந்த எடுக்க இரண்டு உறுப்பு வரிசைகள் மற்றும் அவற்றை ஒன்றாக இணைக்க அதனால் நான்கு உறுப்பு வரிசைகள், மற்றும், மற்றும் பல, மற்றும் அதனால், நாம் வரை ஒரு ஒற்றை N உறுப்பு வரிசை வேண்டும். ஆனால் எத்தனை doublings அதை n பெற வேண்டும்? மீண்டும் தொலைபேசி புத்தகத்தை எடுத்து மீண்டும் நினைக்கிறேன். நாம் எத்தனை முறை கிழிக்க வேண்டும் செய்கிறது அரை தொலைபேசி புத்தகத்தில், இன்னும் எத்தனை முறை நாம் தொலைபேசி புத்தகத்தில் கிழிக்க வேண்டும் பாதியில், என்றால் தொலைபேசி புத்தகத்தின் அளவு இரு மடங்காக? ஒரு சரியான, இல்லை? எனவே சில வகையான இல்லை இங்கே மடக்கை உறுப்பு. ஆனால் நாங்கள் இன்னும் வேண்டும் குறைந்தது n உறுப்புகள் அனைத்தும் இருக்க. , மோசமான சூழ்நிலையில் எனவே வகையான n log n, இயங்கும் ஒன்றாக்க. நாம் பார்க்க வேண்டும் n உறுப்புகள் அனைத்து, மற்றும் நாம் அவற்றை இணைக்க வேண்டும் ஒன்றாக பதிவு n நடவடிக்கைகளை செட். சிறந்த வழக்கு சூழ்நிலையில், வரிசை செய்தபின் பிரிக்கப்பட்டுள்ளது. அது மிகவும் நல்லது. ஆனால் படிமுறை அடிப்படையில் நாம் இங்கே இருக்கிறது நாம் இன்னும் பிரித்து, மீண்டும் இணையும் வேண்டும். இந்த வழக்கில் என்றாலும், மீண்டும் சேர்தலின் பயனற்ற வகையான உள்ளது. அது தேவை இல்லை. ஆனால் நாம் இன்னும் செல்ல எப்படியும் முழு செயல்முறை. அதனால் சிறந்த வழக்கில், மற்றும் மிக மோசமான நிலையில், இந்த வழிமுறை n log n, இயங்கும் நேரம். ஒன்றாக்க வகையான நிச்சயம் ஒரு பிட் trickier உள்ளது மற்ற முக்கிய வகைப்படுத்தல் வழிமுறைகளை விட நாம் CS50 பற்றி பேசினார் ஆனால் கணிசமாக அதிக சக்தி வாய்ந்த. எனவே என்றால், நீங்கள் எப்போதும் கண்டுபிடிக்க நேரத்தில் அது வேண்டும் அல்லது ஒரு வரிசைப்படுத்த அதை பயன்படுத்த பெரிய தரவு தொகுப்பு, பெறுவது மறுநிகழ்வு யோசனை சுற்றி உங்கள் தலையில் மிகவும் சக்திவாய்ந்த இருக்க போகிறது. அது செய்ய நடக்கிறது உங்கள் திட்டங்கள் உண்மையில் மிகவும் திறமையான வேறு எதையும் எதிராக ஒன்றிணைப்பு வகையான பயன்படுத்தி. நான் டக் லாயிட் இருக்கிறேன். இந்த CS50 உள்ளது.